数当てゲーム

## 数当てゲーム

---

バーテンダー「100万円を賭けて勝負をしよう」

---

バーテンダー曰く

- 最初にバーテンダーは1から1,000,000 までの数字を1つ選ぶ
- あなたは数字を1つ答える
- バーテンダーの選んだ数字を的中すれば 
 あなたの勝ち

---

バーテンダー曰く

- 賭けの間、バーテンダーが選んだ数字は変らない
- 数字を答えるチャンスは20回
- 答えた数字がバーテンダーの選んだ数字と比べて 
 - 同じであれば「正解」と言う 
 - 大きければ「大きすぎ」と言う 
 - 小さければ「小さすぎ」と言う

---

# あなたは この賭けに 勝つことが できるか?

---

## ケース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

>>>

| 解答回数 | 解答 | バーテンダー | つまり |
|:-:|:-:|:-:|:-:|
| 16回目  |     15 | 大きすぎ!! | もっと小さい |
| 17回目  |      7 | 小さすぎ!! | もっと大きい |
| 18回目  |     11 | 大きすぎ!! | もっと小さい |
| 19回目  |      9 | 大きすぎ!! | もっと小さい |
| 20回目  |      8 | 正解!!     | 勝ち         |

---

# 必ず勝てる

---

この問題のサイズであれば 
20回でかならず正解に辿りつく

---

1 + log2(1000000)

---

O(log n)

---

# 対数時間

O(log n)

---

## 特徴

- 1回の試行回数で問題のサイズが半分になる
- 急速に解に収束する
- 効率が良い

---

問題を解く時、プログラミングする時は 
計算量も考えてみよう

---

## まとめ

- 数当てゲームを通して計算量を確認した
- 対数時間の計算量オーダーの特徴を確認した

---

### 参考/引用

- アルゴリズムクイックリファレンス (O'Reilly Japan)

---

Thank you