Problem 406 「推測ゲーム」

質問することで整数の集合 {1, 2, ..., n} より選ばれた秘密の数字を見つけ出したい. 質問する数字それぞれに対し, 以下の3つの回答から一つを得る.

与えられた値 n, a, b において, 最適戦略とは最悪のケースの総コストを最小化することである.

例えば, もし n = 5, a = 2, b = 3 の場合, そして最初の質問として ( 秘密の数字が ) "2" であるかどうかを聞いてみる.

もし 2 が秘密の数字より大きければ ( コストは b=3 ), 秘密の数字は "1" であることがわかる. ( 総コストは 3 )
もし 2 が秘密の数字より小さければ ( コストは a=2 ), 次の質問は "4" となる.
もし 4 が秘密の数字より大きければ ( コストは b=3 ), 秘密の数字は "3" であることがわかる. ( 総コストは 2+3=5 )
もし 4 が秘密の数字より小さければ ( コストは a=2 ), 秘密の数字は "5" であることがわかる. ( 総コストは 2+2=4 )
このようにして, この戦略における最悪のケースのコストは 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...

フィボナッチ数 Fk を定義しよう: Fk = Fk-1 + Fk-2, 初期条件は F1 = F2 = 1.

Σ&sub{1≤k≤30};C(10&sup{12};, √k, √F&sub{k};) を求め, 回答を小数点以下8桁になるよう四捨五入して答えよ.


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2012-12-17 (月) 00:39:45