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. 中央のデータが検索対象より大きければ,探索対象を中央のデータより大きいデータに絞ります.

powered by Quick Homepage Maker 5.0
based on PukiWiki 1.4.7 License is GPL. QHM

最新の更新 RSS  Valid XHTML 1.0 Transitional