Problem 328

整数の集合 {1, 2, ..., n} から選ばれた秘密の数を、質問により当てようとしている。数(質問)を尋ねる際は、尋ねた数に等しいコストがかかり、次の三つのいずれかの答えを得る:

n の値が与えられたとき、最適な戦略をとると、起こり得る最悪の場合に対し、総コスト(尋ねた質問の全ての和)が最小になる。例えば、

n=3 の場合、とり得る最良の方法はもちろん "2" と尋ねることである。答えによりたちどころに秘密の数が分かるだろう(総コスト=2)。

n=8 の場合、「二分探索」型の戦略を用いようとするかもしれない:最初の質問は "4" となり、もし秘密の数が 4 より大きければ、追加で1または2回の質問をする必要があるだろう。
2番目の質問を "6" としよう。秘密の数がなおも 6 より大きければ、7 と 8 を見分けるため3番目の質問を必要とするだろう。
このようにして3番目の質問は "7" となり、この最悪の場合のシナリオに対する総コストは 4+6+7=17 となる。

最初の質問として "5" を尋ねれば、n=8 に対する最悪の場合のコストを大幅に改善することができる。
もし秘密の数は 5 より大きいと告げられた場合は、2番目の質問を "7" とすれば、秘密の数が何であるか確実に分かる(総コストは 5+7=12)。
もし秘密の数は 5 より小さいと告げられた場合は、2番目の質問を "3" とすれば、もし秘密の数が 3 より小さければ3番目の質問は "1" となり、総コストは 5+3+1=9 となる。
129 なので、この戦略に対する最悪の場合のコストは 12 となる。これは先ほどの「二分探索」の戦略の結果より優れている;また他のいかなる戦略より優れているか、同コストである。
以上の通り、n=8 に対する最適な戦略を述べた。

上述のように、n に対し最適な戦略をとることで得られる最悪の場合のコストを C(n) とする。
C(1) = 0, C(2) = 1, C(3) = 2, C(8) = 12 である。
同様に、C(100) = 400, p_328_sum1.gifC(n) = 17575 である。

p_328_sum2.gifC(n) を求めよ。


トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS