書庫サーチ

本の背はカバーでかくれていて、めくるごとに 1 手!二分探索、入れる場所さがし、最初のミスさがし、山のてっぺん、階段探索で、できるだけ少ない手で本を見つけよう。

あそぶ

コンピューターの「探索アルゴリズム」を知るパズルゲームです。フクロウの司書の書庫では、本は番号順にならんでいますが、背はカバーでかくれていて、1 冊めくって番号を見るごとに 1 手かかります。はしから 1 冊ずつ見るのが線形探索で、31 冊なら最悪 31 回。まん中をめくって、さがす番号より大きければ前半、小さければ後半。1 回ごとに半分を消せるので、31 冊でも最大 5 回ですみます。これが二分探索です。

この書庫は「いたずら好き」。かくれた答えはめくったときに決まり、いつも大きいほうの半分にかくれるので、手数はほんとうの最悪の場合になります。毎回のこりを同じ大きさの 2 つに分けたときだけ星 3 つ。消えた本は自動で灰色になり、上の欄にはめくるたびにのこった可能性の数(31、15、7、3、1)が記録されます。結果カードでは、半分ずつへっていくようすを棒グラフで表し、1 冊ずつ見た場合の最悪の回数とくらべます。

全 5 章 30 ステージで、章ごとに代表的な探索を 1 つずつ:ならんだ本だな(二分探索)、新しい本はどこ?(入れる場所)、どこから印刷ミス?(プログラマーが使う git bisect と同じ考え方)、いちばん高い本(山の形の列で頂上さがし。となりの本と高さをくらべます)、カード目録の引き出し(横にもたてにも順にならんだ表を、右上から階段のようにさがす)。さらに無限のランダム問題があります。問題は毎回プログラムで作られ、星 3 つの基準はアルゴリズムの最悪の手数です。

あそびかた

  1. 「さがしはじめる」でまだクリアしていないステージから、または「ステージ」から章を選びます。新しい章にはじめて入ると「司書のメモ」が小さな図でその章のさがし方を説明します。タイトル画面の「司書のメモ」でいつでも読み返せます。
  2. 上の欄には、さがすもの(たとえば「653 番の本をさがそう」)とそのステージのルールが書いてあります。本をタップしてめくると、フクロウがその本からわかったことと、のこりの可能性の数を教えてくれます。答えになりえない本は灰色のしまもようになり、タップしても手数はふえません。本の下の小さい数字は位置(何冊目か)、めくったあとのまん中の大きい数字が番号です。
  3. 章ごとの目標:第 1 章はさがす本をめくる。第 2 章は左が小さく右が大きいすき間を見つける(同じ本は見つけなくてよい)。第 3 章は最初の印刷ミスの本(その前の本はだいじょうぶ)を見つける。第 4 章は両どなりより高い本を、となり合う 2 冊をめくってくらべながら見つける。第 5 章は横にもたてにも小さい順にならんだ目録から、その数を見つける。
  4. めくった回数が星 3 の基準以内なら星 3 つ、1~2 回多いと 2 つ、それより多いと 1 つ。電球を押すといちばんよい本が光りますが、そのステージは最大で星 2 つです。失敗はなく、制限時間もありません。左下のボタンで新しい問題にやり直せます。1 つの章で 3 ステージクリアすると次の章が開きます。

そうさ方法

保護者の方へ

最終更新:

こちらもおすすめ