書庫搜尋術

書背被封套蓋住了,每翻一本算一步!用二分搜尋、找插入位置、找第一本印錯的、找山頂、階梯搜尋,以最少的步數找到書。

開始玩

一款認識電腦「搜尋演算法」的解謎遊戲。貓頭鷹館員的書庫裡,書已經照編號排好了,但書背都被封套蓋住,每翻開一本看編號就算一步。從頭一本一本翻叫做線性搜尋,31 本最壞要翻 31 次;翻中間那本,比要找的大就在前半、比較小就在後半,每次排除一半,31 本最多只要 5 次,這就是二分搜尋。

這座書庫很「調皮」:隱藏的答案會在你翻開時才決定,而且總是躲在比較大的那一半,所以步數就是真正的最壞情況。只有每次都把剩下的範圍切成一樣大的兩半,才拿得到 3 顆星。畫面上被排除的書會自動變暗,任務欄記下每一步之後還剩幾個可能(31、15、7、3、1),結算卡用長條圖畫出這個對半縮小的過程,並和一本一本翻的最壞步數比較。

共 5 章 30 關,每章一種經典搜尋:排好的書架(二分搜尋)、新書插哪裡(插入位置)、從哪一本開始印錯(像程式設計師用的 git bisect)、找出最高的書(山形數列找峰值,要和旁邊那本比高低)、卡片目錄櫃(每列每行都排好序的表格,從右上角開始的階梯搜尋)。另有無限題的隨機挑戰。題目每次由程式產生,3 星門檻是演算法的最壞步數。

怎麼玩

  1. 按「開始搜尋」從還沒過的關卡玩起,或從「選關」挑章節。每章第一次進入會出現「館員筆記」,用小圖說明這章的搜尋方法;標題畫面的「館員筆記」可以隨時重看。
  2. 上方任務欄寫著要找什麼(例如「找出編號 653 的書」)和這一關的規則。點一本書把它翻開,貓頭鷹會說明這一本告訴了你什麼、還剩幾個可能。不可能是答案的書會變暗並畫上斜線,點它不會扣步數。書上的小數字是位置(第幾本),翻開後中間的大數字才是編號。
  3. 各章的目標:第 1 章翻到要找的那本;第 2 章找出新書左邊比它小、右邊比它大的空位(不用翻到一樣的書);第 3 章找出第一本印錯的(它前一本是正常的);第 4 章找出比兩邊都高的那本,要翻相鄰的兩本比高低;第 5 章在每列每行都由小到大的目錄櫃裡找出那個數字。
  4. 翻的次數在 3 星門檻以內得 3 顆星,多 1~2 次 2 顆,更多 1 顆。按燈泡會讓最好的那本閃爍,但這一關最多 2 顆星。不會失敗,也沒有時間限制;左下角可以換一題重來。一章過 3 關就會打開下一章。

操作方式

給家長

最後更新:

你可能也喜歡