2014-モンスター-解説

  • 正解は「6」です。
    • 黄色の部屋は127個あります。
    • 真ん中の64番目の部屋をクリックすると,モンスターのいる部屋を63個に絞れます。
    • 続けて,63個の真ん中の部屋をクリックして31個に絞り,もう一度クリックして15個に絞る,という作業を続けていくと,6回のクリックでモンスターを1個の部屋に閉じ込められます。
      127→63→31→15→7→3→1
  • 解説
    • この問題では大量のデータの中から目的のデータを探す「二分探索」を扱っています。
    • 二分探索を使うと,並びの真ん中を見て目的のデータがどちら側にあるかを調べることで、目的のデータを効率よく探すことが可能です。
    • この例では,端から1個ずつクリックして調べていくと全部の部屋を調べるのに127回かかってしまいますが,半分ずつ調べていくことにより6回で探すことができました。
  • 出題国: この問題はフランスで作成されました。

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

最新の更新 RSS  Valid XHTML 1.0 Transitional