Problem 406 の編集

*[[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桁になるよう四捨五入して答えよ.

タイムスタンプを変更しない