« 2016年5月 | トップページ | 2016年7月 »

2016年6月18日 (土)

「マイナー・ゲーム問題」の高度じゃないコード

「高度じゃないコード」シリーズその13は「マイナー・ゲーム問題」です。

問題の内容は次の通りです。(挑戦履歴より転載させていただきました)


n 人のプレイヤーで「少数決」というゲームを行います。
ゲームは次の手順で進みます。

 各プレイヤーは、投票用紙にAまたはBの文字を記し投票します。投票は記名式です。他のプレイヤーの投票内容は分かりません。
 全員が投票し終わったら開票します。その結果、少数派になる回答をした者が勝者となります。例えばAが 3 票、Bが 4 票の場合は、Aを投票した 3 名が勝者です。AとBが同数の場合や、全員がAの場合、全員がBの場合は、全員が勝者です。
 勝者はそのまま勝ち残り次の投票に進めますが、敗者はそこで脱落します。
 以上が 1 回の「ターン」です。この要領でターンを繰り返し、勝ち残りが 1 人か 2 人になるまでゲームを続けます。

各プレイヤーはAまたはBをランダムに選んで投票します。
このとき、n 人のプレイヤーから始めてゲームが終了するまでのターンの回数の期待値を F(n) と定義しましょう。

例えば F(3) = 4/3 です。3 人の投票の仕方は計 23= 8 通りあります。このうち全員がAまたは全員がBの場合(2 通り)は 3 人ともが勝者となりますが、それ以外の場合(6 通り)は 1 名の勝者が決まりゲーム終了します。

1 回目のターンでゲームが終了する確率は 6/8 = 3/4 です。
2 回目のターンでゲームが終了する確率は (1/4)×(3/4) です(1 回目で終了せずかつ 2 回目に終了する確率)。
3 回目のターンでゲームが終了する確率は (1/4)2×(3/4) です(1, 2 回目で終了せずかつ 3 回目に終了する確率)。

したがって期待値は 1×(3/4)+2×(1/4)×(3/4)+3×(1/4)2×(3/4)+… = 4/3 となります。

同様に、F(4) = 2,F(5) = 16/15,F(7) = 1.7566137…,F(8) = 2.2028985… となることが確かめられます。

標準入力から、自然数 n(3 ≦ n ≦ 100)が与えられます。

標準出力に、F(n) を 106 倍した値の整数部分を出力するプログラムを書いてください。

4つの条件に分けて考えます。求める F(n) は次の各場合の合計になります。

1.人数が減らない場合(勝敗がつかない)
 全員が A の場合、全員が B の場合、それと、人数が偶数で半々に分かれた場合です。
 回数が 1 増えただけで、2回目以降の期待値は F(n) と等しいことになります
 [この条件の組合せ数]*(1+F(n))/(2n)

2.上記まで以外で、少ない方を選んだ人が1人(勝敗がつく)
 [この条件の組合せ数]*(1+F(1))/(2n) ※ただし F(1)=0

3.上記まで以外で、少ない方を選んだ人が2人(勝敗がつく)
 [この条件の組合せ数]*(1+F(2))/(2n) ※ただし F(2)=0

4.上記まで以外で、少ない方を選んだ人がt人(t≧3)(勝敗がつかない)
 [この条件の組合せ数]*(1+F(t))/(2n)

ここで、1番の[組合せ数]を j、2番以降の分子の合計を k とすると

F(n)=j*(1+F(n))/(2n)+k/(2n)

(2n)*F(n)=j*(1+F(n))+k

(2n-j)*F(n)=j+k

F(n)=(j+k)/(2n-j)

ということで、後はこの式を使って、必要な F(n) を順次計算していきます。(メモ化利用)

続きを読む "「マイナー・ゲーム問題」の高度じゃないコード"

| | コメント (0) | トラックバック (0)

« 2016年5月 | トップページ | 2016年7月 »