1から100の数当てゲーム
友だちが、1から100の数を一つ決めました。あなたは、それを当てます。答えるたびに、「もっと大きい」か「もっと小さい」と言われます。
1から順に言うと、最悪で100回かかります。でも、うまい言い方を使えば、7回で必ず当てられます。
今日のキーワード
| ことば | いみ | れい |
|---|---|---|
| 二分探索 | 並んだデータのまん中を見て、探す範囲を半分にしていく方法です。 | 数当てゲームの必勝法 |
| 範囲 | まだ答えがあるかもしれない、番号の幅です。 | 1番目から100番目 |
| まん中 | 範囲の、ちょうど真ん中の番号です。 | 1から100なら、50 |
| 並んでいる | 小さい順に、きちんと並んでいる状態です。二分探索の前提です。 | [1, 3, 5, 7] |
| 半分にする | まん中より前、またはあとを、探す範囲から外すことです。 | 範囲が100から50になる |
学生が入力するセルは、このプレビューでは空白です。
まん中を答える
1から100なら、まず、50と答えます。「もっと大きい」と言われたら、答えは51から100です。
一回で、答えの候補が半分になりました。次は、そのまん中の75と答えます。これを、くり返します。
小さな確認: 範囲の変わり方
やってみよう
小さな確認: 範囲の変わり方
3問挑戦してみましょう。回答はここで採点され、その後は保存されません。点数を残したい場合や、続きから再開したい場合はログインしてください。ログインして点数を保存
答えはここで採点され、保存されません。アカウントがあれば、結果が残ります。
例: 答えが 37 のとき
| 回 | 範囲 | 答える数 | 言われること |
|---|---|---|---|
| 1回目 | 1から100 | 50 | もっと小さい |
| 2回目 | 1から49 | 25 | もっと大きい |
| 3回目 | 26から49 | 37 | 当たり |
学生が入力するセルは、このプレビューでは空白です。
やってみよう: 数当てゲーム
secret = 37
low = 1
high = 100
count = 0
while True:
guess = (low + high) // 2
count = count + 1
print(count, "回目:", guess)
if guess == secret:
break
if guess < secret:
low = guess + 1
else:
high = guess - 1
print(count, "回で当たりました")
// を思い出そう
ヒント
(low + high) // 2 の // は、割って、小数を切り捨てる計算です。番号は整数でなければならないので、// を使います。7 // 2 は 3 です。
リストでも同じ
数当てのまん中を、リストの「番号」に置きかえるだけです。リストが、小さい順に並んでいれば、まん中の値を見て、前か後ろの半分を捨てられます。
並んでいないリストでは、使えません。そのときは、前の授業の順番に探す方法を使います。
やってみよう: リストを半分ずつ探す
items = [1, 3, 5, 7, 9, 11, 13]
target = 11
low = 0
high = len(items) - 1
while low <= high:
mid = (low + high) // 2
print(mid, "番目を見ます:", items[mid])
if items[mid] == target:
print("見つかりました")
break
if items[mid] < target:
low = mid + 1
else:
high = mid - 1