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. 中央のデータが検索対象より大きければ，探索対象を中央のデータより大きいデータに絞ります．
注があるものを除き, このサイトの内容物は
