|
|
リーグ戦（ラウンドロビン方式、総当たり）の勝敗結果（勝敗表）は何通りありますか。
ただし、
引き分けはないとします。
チームによって区別することはしません。
例
N=2のとき
A B
A － ○ 1-0
B × － 0-1
A B
A － × 0-1
B ○ － 1-0
なので、
1チームが1勝0敗、1チームが0勝1敗。
の1通り。
N=3のとき
A B C
A － × × 0-2
B ○ － × 1-1
C ○ ○ － 2-0
A B C
A － ○ × 1-1
B × － × 0-2
C ○ ○ － 2-0
A B C
A － × ○ 1-1
B ○ － × 1-1
C × ○ － 1-1
A B C
A － ○ ○ 2-0
B × － × 0-2
C × ○ － 1-1
A B C
A － × × 0-2
B ○ － ○ 2-0
C ○ × － 1-1
A B C
A － ○ × 1-1
B × － ○ 1-1
C ○ × － 1-1
A B C
A － × ○ 1-1
B ○ － ○ 2-0
C × × － 0-2
A B C
A － ○ ○ 2-0
B × － ○ 1-1
C × × － 0-2
なので、
1チームが2勝0敗、1チームが1勝1敗、1チームが0勝2敗。
3チームが1勝1敗。
の2通り。
LET N=6 !チーム数 ※2以上 N=11は困難
PUBLIC NUMERIC D(1500, 0 TO 9) !勝敗のパターン（履歴）
PUBLIC NUMERIC C
LET C=0
DIM M(N,N)!リーグ戦の勝敗結果
CALL try(1,N,M)
PRINT C; "通り"
END
!勝敗表（右上半分）
! 1 2 3 … k … n
! ＿＿＿＿＿＿＿＿＿
! － ＼ 1番目のチーム
! － 左詰1 ＼ 0 2番目のチーム
! － ＼ 3番目のチーム
! ＼ ＼ ：
! － ＿＿＿＼ k番目のチーム
! － ：
! ＼ 0,1
! － n番目のチーム
!
!計算量 O( k^k * 2^COMB(k,2) )、k=[n/2]
EXTERNAL SUB try(P,N,M(,)) !バックトラック法で検索する
LET K=INT(N/2) !1の並びを左詰めにする（チームを区別しないので）
IF P<=K THEN !1～(半分) 番目のチームなら
FOR W=0 TO K !0勝,1勝,2勝,…
FOR J=1 TO W !1行目を埋める
LET M(P,P+J)=1 !右上半分
LET M(P+J,P)=0 !左下半分
NEXT J
FOR J=W+1 TO N-P !n敗,(n-1)敗,(n-2)敗,…
LET M(P,P+J)=0
LET M(P+J,P)=1
NEXT J
IF P=N-1 THEN !すべての行が埋まったなら
CALL check(N,M)
ELSE
CALL try(P+1,N,M) !次の行へ
END IF
NEXT W
ELSE
FOR W=0 TO 2^(N-P)-1 !p行目を埋める
LET T=W
FOR J=1 TO N-P
LET B=MOD(T,2)
LET M(P,P+J)=B !右上半分
LET M(P+J,P)=1-B !左下半分
LET T=INT(T/2)
NEXT J
IF P=N-1 THEN !すべての行が埋まったなら
CALL check(N,M)
ELSE
CALL try(P+1,N,M) !次の行へ
END IF
NEXT W
END IF
END SUB
EXTERNAL SUB check(N,M(,)) !既出のパターンと同じかどうか確認する
DIM F(0 TO N-1) !勝敗のパターン
MAT F=ZER
FOR i=1 TO N !i番目のチームの勝ち数
LET S=0
FOR J=1 TO N
LET S=S+M(i,J)
NEXT J
LET F(S)=F(S)+1
NEXT i
!!!MAT PRINT F; !0勝,1勝,2勝,…,(n-1)勝のチーム数
FOR i=1 TO C !既出のパターンと同じかどうか確認する
FOR J=0 TO N-1
IF D(i,J)<>F(J) THEN EXIT FOR
NEXT J
IF J>N-1 THEN EXIT FOR !同じパターンなら
NEXT i
IF i>C THEN !新規の場合、登録する
LET C=C+1
FOR J=0 TO N-1 !copy it
LET D(C,J)=F(J)
NEXT J
PRINT "No."; STR$(C) !結果を表示する
MAT PRINT F;
MAT PRINT M;
END IF
END SUB
|
|