|
|
問題
「2人3脚」ならぬ「30人31脚」を考えます。
女の子が続いて並ぶと体力的に不利なので、女の子は隣り合わないようにします。
（男の子は何人並んでもよいものとします）
30人を一列に並べるとき、その並び方が何通りあるかを求めてください。
（男女の並び方だけを考えるものとして、誰がどの位置ということは考えないものとします。
説明
例えば、4人（4人5脚）の場合は以下の8通りがあります。
男男男男
男男男女
男男女男
男女男男
女男男男
男女男女
女男男女
女男女男
（終わり）
類題 大相撲本場所
15日間連敗しない勝ち負けの起こり方は何通りあるでしょうか。ただし、連敗とは2連敗をさします。
答え
・場合の数
考察
左側から並べていき、k人の並びを考える。最初の1人を特定すれば、
男と(k-1)人の並び
女と男と(k-2)人の並び
と考えられる。
これより、漸化式F(n)=F(n-1)+F(n-2)を得る。
（終わり）
DECLARE EXTERNAL FUNCTION CALC.F
LET N=30
PRINT F(N);"通り"
END
MODULE CALC !F(n)=F(n-1)+F(n-2)、F(0)=1、F(1)=2
SHARE NUMERIC D(0 TO 50)
MAT D=ZER
PUBLIC FUNCTION F
EXTERNAL FUNCTION F(N)
IF D(N)>0 THEN !計算済みなら
LET T=D(N)
ELSE
IF N=0 THEN
LET T=1 !φの1通り
ELSEIF N=1 THEN
LET T=2 !0,1の2通り
ELSE
LET T=F(N-1)+F(N-2) !0**,10*
END IF
END IF
LET F=T
LET D(N)=T
END FUNCTION
END MODULE
考察
4人5脚を考える。
女が0人、男が4人の場合
男男男男 の1通り
女が1人、男が3人の場合
○男○男○男○ と並べて、女は4個の○から1つを選ぶ。 C(4,1)=4通り
女が2人、男が3人の場合
○男○男○ と並べて、女は3個の○から2つを選ぶ。 C(3,2)=3通り
女が3人以上は題意を満たさない。
以上より、1+4+3=8通り
（終わり）
LET N=30
LET S=1 !女が0人
FOR K=1 TO (N+1)/2 !女がk人
LET S=S+COMB(N-K+1,K) !男を(n-k)人並べて、その間に並べる
NEXT K
PRINT S;"通り"
END
・並びの列挙
LET N=30
PUBLIC NUMERIC C !場合の数
LET C=0
DIM A(0 TO N) !※0番目は番兵
MAT A=ZER
CALL try(1,N,A)
PRINT C;"通り"
END
EXTERNAL SUB try(P,N,A()) !シミュレーション
IF P>N THEN
LET C=C+1
!!PRINT "No.";C !並びを表示する
!!MAT PRINT A;
ELSE
LET A(P)=0 !男
CALL try(P+1,N,A)
IF A(P-1)=0 THEN !1つ前が男なら
LET A(P)=1 !女
CALL try(P+1,N,A)
END IF
END IF
END SUB
|
|