*[[Problem 328:http://projecteuler.net/index.php?section=problems&id=328]] [#e5d6ad48]

整数の集合 {1, 2, ..., n} から選ばれた秘密の数を、質問により当てようとしている。数(質問)を尋ねる際は、%%%尋ねた数に等しいコスト%%%がかかり、次の三つのいずれかの答えを得る:
- 「秘密の数はあなたの推測した数より小さいです」
- 「そう、まさにその数です!」
- 「秘密の数はあなたの推測した数より大きいです」

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

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

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

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

上述のように、n に対し最適な戦略をとることで得られる最悪の場合のコストを C(n) とする。~
C(1) = 0, C(2) = 1, C(3) = 2, C(8) = 12 である。~
同様に、C(100) = 400, &ref(http://projecteuler.net/project/images/p_328_sum1.gif);C(n) = 17575 である。

&ref(http://projecteuler.net/project/images/p_328_sum2.gif);C(n) を求めよ。


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