*[[Problem 406:http://projecteuler.net/problem=406]] 「推測ゲーム」 [#me42e4b4]
質問することで整数の集合 {1, 2, ..., '''n'''} より選ばれた秘密の数字を見つけ出したい. 質問する数字それぞれに対し, 以下の3つの回答から一つを得る.
-「あなたの推測は秘密の数字より小さいです.」 ( '''a''' のコストがかかる )
-「あなたの推測は秘密の数字より大きいです.」 ( '''b''' のコストがかかる )
-「はい, 正解です.」 ( ゲーム終了 )
与えられた値 '''n''', '''a''', '''b''' において, ''最適戦略''とは%%%最悪のケースの%%%総コストを最小化することである.
例えば, もし '''n''' = 5, '''a''' = 2, '''b''' = 3 の場合, そして最初の質問として ( 秘密の数字が ) "''2''" であるかどうかを聞いてみる.
もし 2 が秘密の数字より大きければ ( コストは '''b'''=3 ), 秘密の数字は "''1''" であることがわかる. ( 総コストは &color(blue){''3''}; )~
もし 2 が秘密の数字より小さければ ( コストは '''a'''=2 ), 次の質問は "''4''" となる.~
もし 4 が秘密の数字より大きければ ( コストは '''b'''=3 ), 秘密の数字は "''3''" であることがわかる. ( 総コストは 2+3=&color(blue){''5''}; )~
もし 4 が秘密の数字より小さければ ( コストは '''a'''=2 ), 秘密の数字は "''5''" であることがわかる. ( 総コストは 2+2=&color(blue){''4''}; )~
このようにして, この戦略における最悪のケースのコストは &color(red){''5''}; となる. またこれが最も低い最悪ケースのコストであることを示すことができる. つまり, これが与えられた値 '''n''', '''a''', '''b''' における最適戦略である.
与えられた値 '''n''', '''a''', '''b''' において最適戦略における最悪ケースのコストを C('''n''', '''a''', '''b''') としよう.
以下に例を示す:~
C(5, 2, 3) = 5~
C(500, √2, √3) = 13.22073197...~
C(20000, 5, 7) = 82~
C(2000000, √5, √7) = 49.63755955...
フィボナッチ数 F&tex{_{k}}; を定義しよう: F&tex{_{k}}; = F&tex{_{k-1}}; + F&tex{_{k-2}};, 初期条件は F&tex{_{1}}; = F&tex{_{2}}; = 1.
Σ&sub{1≤'''k'''≤30};C(10&sup{12};, √'''k''', √F&sub{'''k'''};) を求め, 回答を小数点以下8桁になるよう四捨五入して答えよ.
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
