2016-犯人を探せ-解説
- 考案国: ベルギー
- 正解
- 「20回以下の質問で犯人を当ててみせます.」
- 説明
- 部屋に入った順番で、見学者に1から2000の番号を付けます。
- ビ太郎は最初に1000番の見学者にダイヤモンドの色を聞きます。青と答えた場合は1001から2000に犯人がいます。緑と答えた場合は1から1000に犯人がいます(犯人は「自分が入ったときはすでに緑色の偽物でした」と答えるでしょうから、1000番の見学者も犯人かもしれません)。どちらの場合であっても、犯人の候補者を半分に減らすことができました。
- ビ太郎は2回目に、候補者の1000人の真ん中の見学者(500番か1500番)に質問をして、同様に250人の候補者に減らします。
- 同様に、3回目の質問で125人に、4回目の質問で63人に、5回目で32人、6回目で16人、7回目で8人、8回目で4人、9回目で2人に絞ります。
- 10回目の質問で、前の候補者が緑と答えたらその人が犯人です。青と答えたら次の人が犯人です。
- 解説
- データ集合の中から特定のデータを探索・検索するのは,情報科学において基本的で重要な問題です.
- 二分探索は,整列されているデータ集合に対する効率の良い検索アルゴリズムです:
1. 整列されているデータ集合全体を探索範囲とします.
2. 探索範囲がなくなる(か,探索対象が見つかる)まで,次を繰返します.
2-1. 探索範囲の中央のデータが探索対象かどうか調べます.
2-2-1. 中央のデータが検索対象なら,探索を終了します.
2-2-2. 中央のデータが検索対象より小さければ,探索対象を中央のデータより大きいデータに絞ります.
2-2-3. 中央のデータが検索対象より大きければ,探索対象を中央のデータより大きいデータに絞ります.