Problem 328
の編集
http://odz.sakura.ne.jp/projecteuler/index.php?Problem+328
[
トップ
] [
編集
|
差分
|
バックアップ
|
添付
|
リロード
] [
新規
|
一覧
|
検索
|
最終更新
|
ヘルプ
]
-- 雛形とするページ --
(no template pages)
*[[Problem 328:http://projecteuler.net/problem=328]] 「最低コスト探索」 [#e5d6ad48] 整数の集合 {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=''&color(red){17};'' となる. 最初の質問として "''5''" を尋ねれば, n=8 に対する最悪の場合のコストを大幅に改善することができる. ~ もし秘密の数は 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};'' となる. これは先ほどの「二分探索」の戦略の結果より優れている;また他のいかなる戦略より優れているか, 同コストである. ~ 以上の通り, 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,nolink);C(n) = 17575 である. &ref(http://projecteuler.net/project/images/p_328_sum2.gif,nolink);C(n) を求めよ.
タイムスタンプを変更しない
*[[Problem 328:http://projecteuler.net/problem=328]] 「最低コスト探索」 [#e5d6ad48] 整数の集合 {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=''&color(red){17};'' となる. 最初の質問として "''5''" を尋ねれば, n=8 に対する最悪の場合のコストを大幅に改善することができる. ~ もし秘密の数は 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};'' となる. これは先ほどの「二分探索」の戦略の結果より優れている;また他のいかなる戦略より優れているか, 同コストである. ~ 以上の通り, 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,nolink);C(n) = 17575 である. &ref(http://projecteuler.net/project/images/p_328_sum2.gif,nolink);C(n) を求めよ.
テキスト整形のルールを表示する