« ^ »数当てゲーム所要時間: 約 3分 ## 数当てゲーム --- バーテンダー「100万円を賭けて勝負をしよう」 --- バーテンダー曰く - 最初にバーテンダーは1から1,000,000<br />までの数字を1つ選ぶ - あなたは数字を1つ答える - バーテンダーの選んだ数字を的中すれば<br /> あなたの勝ち --- バーテンダー曰く - 賭けの間、バーテンダーが選んだ数字は変らない - 数字を答えるチャンスは20回 - 答えた数字がバーテンダーの選んだ数字と比べて<br /> - 同じであれば「正解」と言う<br /> - 大きければ「大きすぎ」と言う<br /> - 小さければ「小さすぎ」と言う<br /> --- # あなたは<br />この賭けに<br />勝つことが<br />できるか? --- ## ケース1 >>> | 解答回数 | 解答 | バーテンダー | つまり | |:-:|:-:|:-:|:-:| | 1回目 | 500,000 | 大きすぎ!! | もっと小さい | | 2回目 | 250,000 | 大きすぎ!! | もっと小さい | | 3回目 | 125,000 | 大きすぎ!! | もっと小さい | | 4回目 | 62,500 | 大きすぎ!! | もっと小さい | | 5回目 | 31,250 | 大きすぎ!! | もっと小さい | >>> | 解答回数 | 解答 | バーテンダー | つまり | |:-:|:-:|:-:|:-:| | 6回目 | 15,625 | 大きすぎ!! | もっと小さい | | 7回目 | 7,812 | 大きすぎ!! | もっと小さい | | 8回目 | 3,906 | 大きすぎ!! | もっと小さい | | 9回目 | 1,953 | 大きすぎ!! | もっと小さい | | 10回目 | 976 | 大きすぎ!! | もっと小さい | >>> | 解答回数 | 解答 | バーテンダー | つまり | |:-:|:-:|:-:|:-:| | 11回目 | 488 | 大きすぎ!! | もっと小さい | | 12回目 | 244 | 大きすぎ!! | もっと小さい | | 13回目 | 122 | 大きすぎ!! | もっと小さい | | 14回目 | 61 | 大きすぎ!! | もっと小さい | | 15回目 | 30 | 大きすぎ!! | もっと小さい | >>> | 解答回数 | 解答 | バーテンダー | つまり | |:-:|:-:|:-:|:-:| | 16回目 | 15 | 大きすぎ!! | もっと小さい | | 17回目 | 7 | 大きすぎ!! | もっと小さい | | 18回目 | 3 | 大きすぎ!! | もっと小さい | | 19回目 | 2 | 大きすぎ!! | もっと小さい | | 20回目 | 1 | 正解!! | 勝ち | --- ## ケース2 >>> | 解答回数 | 解答 | バーテンダー | つまり | |:-:|:-:|:-:|:-:| | 1回目 | 500,000 | 大きすぎ!! | もっと小さい | | 2回目 | 250,000 | 大きすぎ!! | もっと小さい | | 3回目 | 125,000 | 大きすぎ!! | もっと小さい | | 4回目 | 62,500 | 大きすぎ!! | もっと小さい | | 5回目 | 31,250 | 大きすぎ!! | もっと小さい | >>> | 解答回数 | 解答 | バーテンダー | つまり | |:-:|:-:|:-:|:-:| | 6回目 | 15,625 | 大きすぎ!! | もっと小さい | | 7回目 | 7,812 | 大きすぎ!! | もっと小さい | | 8回目 | 3,906 | 大きすぎ!! | もっと小さい | | 9回目 | 1,953 | 大きすぎ!! | もっと小さい | | 10回目 | 976 | 大きすぎ!! | もっと小さい | >>> | 解答回数 | 解答 | バーテンダー | つまり | |:-:|:-:|:-:|:-:| | 11回目 | 488 | 大きすぎ!! | もっと小さい | | 12回目 | 244 | 大きすぎ!! | もっと小さい | | 13回目 | 122 | 大きすぎ!! | もっと小さい | | 14回目 | 61 | 大きすぎ!! | もっと小さい | | 15回目 | 30 | 大きすぎ!! | もっと小さい | >>> | 解答回数 | 解答 | バーテンダー | つまり | |:-:|:-:|:-:|:-:| | 16回目 | 15 | 大きすぎ!! | もっと小さい | | 17回目 | 7 | 小さすぎ!! | もっと大きい | | 18回目 | 11 | 大きすぎ!! | もっと小さい | | 19回目 | 9 | 大きすぎ!! | もっと小さい | | 20回目 | 8 | 正解!! | 勝ち | --- # 必ず勝てる --- この問題のサイズであれば<br /> 20回でかならず正解に辿りつく --- 1 + log2(1000000) --- O(log n) --- # 対数時間 O(log n) --- ## 特徴 - 1回の試行回数で問題のサイズが半分になる - 急速に解に収束する - 効率が良い --- 問題を解く時、プログラミングする時は<br /> 計算量も考えてみよう --- ## まとめ - 数当てゲームを通して計算量を確認した - 対数時間の計算量オーダーの特徴を確認した --- ### 参考/引用 - アルゴリズムクイックリファレンス (O'Reilly Japan) --- Thank you