トーナメント表をつくる

 投稿者：山中和義  投稿日：2014年 2月24日(月)10時03分56秒
  (n+1)チームがトーナメント形式で対戦するとき、試合数は、n試合ある。
トーナメント表の形は、Cn（カタラン数）通りある。

参考サイト
　　私の備忘録
　　　数学・・・代数学分野


aとbの対戦を、(ab)と表す。

格子状経路の最短経路の場合の数と等しい。

n=2のとき
　　Ｂ
　　│*
Ａ─・
  b

　a b *     (ab)

　┌┴┐
　a   b


n=3のとき
　　　　　Ｂ
　　　　　│*
　　　・─・
　　　│　│*
　Ａ─・─・
　  b   c

　a b * c *     ((ab)c)
　a b c * *     (a(bc))


　  ┌┴─┐
　┌┴┐  │
　a   b   c


　┌┴─┐
　│  ┌┴┐
　a   b   c


n=4のとき
　　　　　　　Ｂ
　　　　　　　│*
　　　　　・─・
　　　　　│　│*
　　　・─・─・
　　　│　│　│*
　Ａ─・─・─・
　  b   c   d

　a b * c * d *     (((ab)c)d)
　a b * c d * *     ((ab)(cd))
　a b c * * d *     ((a(bc))d)
　a b c * d * *     (a((bc)d))
　a b c d * * *     (a(b(cd)))



!トーナメント表をつくる
LET N=4 !チーム数
LET W$=REPEAT$(" ",N+(N-1))
LET W$(1:1)="A"
CALL try(2,N,0,0,W$)
LET M=N-1
PRINT COMB(2*M,M+1)/M; "通り"
END

EXTERNAL SUB try(P,N,X,Y,W$) !バックトラック法で検索する
IF X=N-1 AND Y=N-1 THEN !終点なら
!!!PRINT W$ !debug
   CALL PrintOut(N,W$)
   !CALL PrintOut2(N,W$)
ELSE
   IF Y+1<=X THEN !縦方向
      LET W$(P:P)="*"
      CALL try(P+1,N,X,Y+1,W$)
   END IF
   IF X+1<N THEN !横方向
      LET W$(P:P)=CHR$((X+1)+ORD("A")) !B,C,D,…
      CALL try(P+1,N,X+1,Y,W$)
   END IF
END IF
END SUB

EXTERNAL SUB PrintOut(N,S$) !トーナメント表の形状を表示する（逆ポーランド記法）
DIM STK$(N) !stack
LET Q=0
FOR i=1 TO LEN(S$) !スクリプト文を解釈実行する
   LET T$=S$(i:i)
   SELECT CASE T$
   CASE "*" !pop
      LET X$=STK$(Q-1) !(x,y)
      LET Y$=STK$(Q)
      LET Q=Q-1 !(-2)+(1)=(-1)より
      LET STK$(Q)="("&X$&Y$&")"
   CASE IS>="A",IS<="Z" !push
      LET Q=Q+1
      LET STK$(Q)=T$
   CASE ELSE
      PRINT "論理エラーです。"; T$; i
      STOP
   END SELECT
NEXT i
PRINT STK$(1)
END SUB

EXTERNAL SUB PrintOut2(N,S$) !トーナメント表の形状を表示する
OPTION CHARACTER BYTE !バイト単位
DEF SPC(X)=(X-1)*4+1 !表示位置
DIM STK(N) !stack
LET W$=REPEAT$(" ",SPC(N)+1) !1行分の文字列（バッファ）
FOR i=1 TO LEN(S$) !スクリプト文を解釈実行する
   LET T$=S$(i:i)
   SELECT CASE T$
   CASE "*" !pop
      LET X=STK(P-1) !z=(xy)
      IF X<0 THEN
         LET X=-X
         LET K=SPC(X)+1
         LET W$(K:K)=CHR$(X+ORD("A")-1) !1,2,3,…をA,B,C,…へ
      END IF
      LET Y=STK(P)
      IF Y<0 THEN
         LET Y=-Y
         LET K=SPC(Y)+1
         LET W$(K:K)=CHR$(Y+ORD("A")-1)
      END IF
      LET Z=(X+Y)/2
      LET P=P-1 !(-2)+(+1)より
      LET STK(P)=Z

      PRINT W$
      LET W$=REPEAT$(" ",SPC(N)+1)

      LET W$(SPC(X):SPC(X)+1)="└" !対戦
      LET W$(SPC(Z):SPC(Z)+1)="┬"
      LET W$(SPC(Y):SPC(Y)+1)="┘"

      FOR J=1 TO P-1 !ブロック
         LET K=STK(J)
         IF K>0 THEN LET W$(SPC(K):SPC(K)+1)="│"
      NEXT J
   CASE IS>="A",IS<="Z" !push
      LET P=P+1
      LET STK(P)=-(ORD(T$)-ORD("A")+1) !A,B,C,…を-1,-2,-3,…へ
   CASE ELSE
      PRINT "論理エラーです。"; T$; i
      STOP
   END SELECT
NEXT i
PRINT W$ !決勝戦
PRINT
END SUB

 		 

Re: トーナメント表をつくる

 投稿者：GAI  投稿日：2014年 2月26日(水)19時26分43秒
  > No.3328[元記事へ]

山中和義さんへのお返事です。

> !トーナメント表をつくる

表がいろいろパターンが生まれるのが面白く、６人でのパターンを出力して（４２通り）
ノートに整理して思ったのが、このトーナメント表をプログラムで組むことが如何に凄いことかということです。（特にPrintOut2）
縦との線が繋がっているし、横幅がそれぞれで異なるし、勝ち上がるラインの線の長さも異なっているしで、全体としてトーナメントの形状がとれていなくてはいけないしと・・・
これをアルゴリズムで組み上げることは私には神業に感じられます。
プログラムの主要な部分を読んでも、いろいろな技が組み合わされている感じで、ちょうどアナログテレビの裏側をのぞいた気分です。
これを効率よく組み上げられる技に感動します。
 		 

Re: トーナメント表をつくる

 投稿者：山中和義  投稿日：2014年 2月27日(木)10時26分18秒
  > No.3328[元記事へ]

問題
4つの自然数1,2,5,8をすべて使って、四則演算（加減乗除）と括弧による
1桁どうしの計算式の結果が、0から51までの数を表すようにしてください。
例
0=1+2+5-8、1=8-1*2-5、2=1+5-8/2、3=(1-2)×5+8 など

類題
4つの自然数1,2,4,10をすべて使って、0から50までの数を表す。

参考サイト
　　私の備忘録
　　　数学・・・代数学分野
　　クイズ＆パズル
　　　数の創出
　　　最長不倒の４数を探せ！　http://www004.upp.so-net.ne.jp/s_honma/relax/number23.html

考察
　　　　　　　　Ｂ
　　　　　　　　│+,-,*,/
　　　　　　・─・
　　　　　　│　│+,-,*,/
　　　　・─・─・
　　　　│　│　│+,-,*,/
　　Ａ─・─・─・
　a   b   c   d
　a   b   d   c
　a   c   b   d
　　　　：
　d   c   b   a
として、逆ポーランド表記（後置表記）の式を生成する。
これは、中置表記での四則演算（加減乗除）と括弧による式を表すことができる。

式の形状は、
　a b + c + d +     (((a+b)+c)+d)
　a b + c d + +     ((a+b)+(c+d))
　a b c + + d +     ((a+(b+c))+d)
　a b c + d + +     (a+((b+c)+d))
　a b c d + + +     (a+(b+(c+d)))
となる。

よって、4!×5×4^3 通りを検証する。
（終り）



OPTION ARITHMETIC RATIONAL !分数の計算

PUBLIC NUMERIC D(4)
DATA 1,2,5,8
!DATA 1,2,4,10
MAT READ D

PUBLIC NUMERIC F(0 TO 7000) !0～n
MAT F=ZER

LET N=4 !チーム数
DIM A(N+(N-1))
LET A(1)=1 !A
CALL try(2,0,0, N,A)
END

EXTERNAL SUB try(P,X,Y, N,A()) !バックトラック法で検索する
OPTION ARITHMETIC RATIONAL !分数の計算
IF X=N-1 AND Y=N-1 THEN !終点なら
!!!MAT PRINT A; !debug
   CALL check(N,A)
ELSE
   IF Y+1<=X THEN !縦方向
      LET A(P)=-(Y+1) !*
      CALL try(P+1,X,Y+1, N,A)
   END IF
   IF X+1<N THEN !横方向
      LET A(P)=(X+1)+1 !B,C,D,…
      CALL try(P+1,X+1,Y, N,A)
   END IF
END IF
END SUB

EXTERNAL SUB check(N,P()) !数、演算子の並びを考える
OPTION ARITHMETIC RATIONAL !分数の計算
DIM A(N),B(N-1)
FOR h=0 TO FACT(N)-1 !a,b,c,…,d の順列
   CALL Num2PermFactorial(h, A,N)

   FOR J=0 TO 4^(N-1)-1 !+,-,*,/ の重複順列
      LET T=J !4進法
      FOR i=1 TO N-1 !+,-,*,/ を -1,-2,-3,-4 へ
         LET B(i)=-(MOD(T,4)+1)
         LET T=INT(T/4)
      NEXT i

      CALL Calc(N,P,A,B) !計算する
   NEXT J

NEXT h
END SUB

EXTERNAL SUB Calc(N,P(),A(),B()) !逆ポーランド記法の式を計算する
OPTION ARITHMETIC RATIONAL !分数の計算
DIM STK(N),EXP$(N) !stack
LET Q=0
FOR i=1 TO N+(N-1) !スクリプト文を解釈実行する
   SELECT CASE P(i)
   CASE IS<0 !*　pop
      LET X=STK(Q-1) !(xy)
      LET Y=STK(Q)
      LET X$=EXP$(Q-1) !x○y
      LET Y$=EXP$(Q)

      LET Q=Q-1 !(-2)+(1)=(-1)より
      LET T=-P(i)
      IF B(T)=-1 THEN !加算
         LET STK(Q)=X+Y
         LET EXP$(Q)="(" & X$ & "+" & Y$ & ")"
      ELSEIF B(T)=-2 THEN !減算
         LET STK(Q)=X-Y
         LET EXP$(Q)="(" & X$ & "-" & Y$ & ")"
      ELSEIF B(T)=-3 THEN !乗算
         LET STK(Q)=X*Y
         LET EXP$(Q)=X$ & "×" & Y$
      ELSEIF B(T)=-4 THEN !除算
         IF Y=0 THEN EXIT SUB !0で割る
         LET STK(Q)=X/Y
         LET EXP$(Q)=X$ & "÷" & Y$
      ELSE
         PRINT "論理エラーです。"; T$; i
         STOP
      END IF
   CASE IS>0 !A,B,…,Z　push
      LET T=D(A(P(i)))
      LET Q=Q+1
      LET STK(Q)=T
      IF T<0 THEN !負の値
         LET EXP$(Q)="(" & STR$(T) & ")"
      ELSE !非負の値
         LET EXP$(Q)=STR$(T)
      END IF
   CASE ELSE
      PRINT "論理エラーです。"; T$; i
      STOP
   END SELECT
NEXT i
!!!PRINT STK(1) !debug

LET T=STK(1) !結果を表示する
IF T>=0 AND T=INT(T) AND F(T)=0 THEN !非負整数、1番目
   LET F(T)=1
   PRINT T; "= "; EXP$(1)
END IF
END SUB



!COMB.LIB 抜粋

EXTERNAL SUB Num2PermFactorial(h, A(),N) !番号から順列パターンを生成する　※辞書式順序
OPTION ARITHMETIC RATIONAL !分数の計算
LET v=h !非負の10進数整数を階乗進数へ
FOR j=N TO 1 STEP -1 !下の桁から順に
   LET w=N-j+1
   LET t=INT(v/w)
   LET A(j)=v-t*w +1 !階乗進数の各桁の値＋１　A[1..N]=(N-1)! … 3! 2! 1! 0!
   LET v=t
NEXT j
FOR j=N-1 TO 1 STEP -1 !順列パターンへ
   FOR k=j+1 TO N
      IF A(k)>=A(j) THEN LET A(k)=A(k)+1
   NEXT k
NEXT j
END SUB

 		 

戻る