|
|
> No.3626[元記事へ]
GAIさんへのお返事です。
> トランプで１～１３のカードをシャッフルして
> テーブルに上から一枚ずつカードを左から右に並べていく。
> 次のカードが並んだカードの右端にあるカードの数字より少なければこのカードは横には
> 並べず捨てる。
> ただし、１(エースカード）は特別な役目を持ち
> 右端がどんなカードでも捨てずに横に並べて置けて、次のカードはどんなものでも場から
> 捨て去る。ただしこの次のカードからは上記の通常のルールで進行していく。
13!では、一日仕事ですね。
LET N=13
DIM A(N) !並び
PUBLIC NUMERIC F(100) !各数字の残った回数
MAT F=ZER(N)
CALL try(1, N,A)
MAT PRINT F;
END
EXTERNAL SUB try(K, N,A()) !全順列を生成する（辞書順ではない）
IF K>N THEN
!!!MAT PRINT A; !答え
CALL game(A,N)
ELSE
DIM B(N)
LET B(K)=K !kをk番目に挿入する
FOR i=1 TO K-1 !a[1],a[2],…,a[k-1],k ※a[1..k-1]
LET B(i)=A(i)
NEXT i
CALL try(K+1, N,B) !次へ
FOR P=K-1 TO 1 STEP -1 !kをp番目に挿入する
LET T=B(P) !swap it
LET B(P)=B(P+1)
LET B(P+1)=T
CALL try(K+1, N,B) !次へ
NEXT P
END IF
END SUB
EXTERNAL SUB game(A(),N) !ゲームを行う
LET R=0 !右端
LET i=1
DO WHILE i<=N !i枚目
LET T=A(i)
IF T=1 THEN !1の場合
LET F(T)=F(T)+1 !カウントする
LET R=1
LET i=i+1 !a[i+1]を捨てる
ELSE
IF R>T THEN !捨てる
ELSE !並べる
LET F(T)=F(T)+1 !カウントする
LET R=T
END IF
END IF
LET i=i+1
LOOP
END SUB
> トランプで１～１３のカードをシャッフルして
> テーブルに上から一枚ずつカードを左から右に並べていく。
> 次のカードが並んだカードの右端にあるカードの数字より少なければこのカードは横には
> 並べず捨てる。
1からnまでの数字を並べるとき、
数字kが残る場合の数
k=1のとき、
1番目に配置した場合、1○…○の並びで、(n-1)!
2番目以上に配置した場合、1より前に1より大きな数字が少なくとも1つあるので、1は残らない。
k=2のとき、
1番目に配置した場合、2○…○の並びで、(n-1)!
2番目に配置した場合、12○…○の並びで、1×(n-2)!
3番目以上に配置した場合、2より前に2より大きな数字が少なくとも1つあるので、2は残らない。
よって、(n-1)!+(n-2)!={(n-1)+1}×(n-2)!=n×(n-2)!
k=3のとき、
1番目に配置した場合、3○…○の並びで、(n-1)!
2番目に配置した場合、13○…○、23○…○の並びで、2×(n-2)!
3番目に配置した場合、123○…○、213○…○の並びで、2!×(n-3)!
4番目以上に配置した場合、3より前に3より大きな数字が少なくとも1つあるので、3は残らない。
よって、(n-1)!+2×(n-2)!+2!×(n-3)!={(n-1)(n-2)+2(n-2)+2!}×(n-3)!=n(n-1)×(n-3)!
k=4のとき、（一般的な記述にすると）
1番目に配置した場合、(1,2,3から0個)4(残りの数字)の並びで、P(3,0)×(n-1)!
2番目に配置した場合、(1,2,3から1個)4(残りの数字)の並びで、P(3,1)×(n-2)!
3番目に配置した場合、(1,2,3から2個)4(残りの数字)の並びで、P(3,2)×(n-3)!
4番目に配置した場合、(1,2,3から3個)4(残りの数字)の並びで、P(3,3)×(n-4)!
5番目以上に配置した場合、4より前に4より大きな数字が少なくとも1つあるので、4は残らない。
よって、n(n-1)(n-2)×(n-4)!=n!/(n-3)
k=5のとき、
：
：
一般的に、n!/(n+1-k)個残る。（予想）
LET N=4
FOR K=1 TO N
LET S=0
FOR M=1 TO K !数字kをm番目に配置した場合
LET S=S+PERM(K-1,M-1)*FACT(N-M)
NEXT M
PRINT K; S; FACT(N)/(N+1-K)
NEXT K
END
シミュレーションの場合、以下の部分を差し替えてください。
EXTERNAL SUB game(A(),N) !ゲームを行う
LET R=0 !右端
LET i=1
DO WHILE i<=N !i枚目
LET T=A(i)
IF R>T THEN !捨てる
ELSE !並べる
LET F(T)=F(T)+1 !カウントする
LET R=T
END IF
LET i=i+1
LOOP
END SUB
|
|