二十個問題

活動名稱：二十個問題 THE 20 QUESTIONS ACTIVITY

教學時間：約15分鐘

教學單元：

• 計算思維(computational thinking)
• 線性搜尋(linear search)
• 二元搜尋法(binary search)
• 分治法(divide and conquer)
• 比較算法(comparing algorithms)

教學目標：藉由搜尋演算法來介紹基本的分治法，也說明我們要如何對演算法進行效率分析。

對象：11歲、2~數百人以上

先備知識：使用線性搜尋的搜尋知識

活動設計：

• 概要

以玩「20個問題」遊戲的方式，顯示出他們從小學起就已經知道高效搜尋關鍵以及分治法的基礎。

• 如何進行

吸引注意力的技巧：

以下有好幾個吸引學生注意力的方法。我們可以使用有介紹過線性搜尋的“Locked-in”活動，它主要在說如何幫助一個完全癱瘓的人進行溝通〈可在後面看到Locked-in及Searching To Speak resource in Further Reading活動〉。

下面介紹一個簡單快速可以吸引注意的另一種說法：指出世上有數十億個網頁，但電腦可以在幾秒鐘內找到東西。它是否做線性搜尋依次檢查每個網頁？電腦實際上還沒快到可以做到這一點，搜尋演算法必須比線性搜尋更聰明！這個活動就是開始探索它如何做到的。

還有一個方法，可以使用電腦來進行。讓每個學生選擇一個名人，並使用搜尋引擎搜尋他，然後回報電腦多快就完成搜尋了。

準備：

在課堂中與學生複習線性搜尋的功用，設置一個從百萬中搜尋一件事的問題，若學生了解陣列的概念，可舉例像是從百萬個人名的陣列當中找到其中一個人名。若他們不懂陣列概念，那也沒關係，可舉一些簡單例子，如：你如何在雜亂無章的書架上找到一本書，或你如何在一大堆考卷中找到某個人的考卷。“Locked-in”活動也可以拿來舉例。

• 活動內容

與學生玩「20個問題」的遊戲，你需要想一個名人，並讓學生問一些問題來猜你想的這個人是誰，但你只能回答是或否。在玩的時候，記得鼓勵班上來思考它們在問什麼樣的問題，以及怎麼樣才能說是一個好問題。

舉個遊戲例子

「他是女生嗎？」 不是

「他還活著嗎？」 不是

「他是電影明星嗎？」 不是

「他來自英國嗎？」 不是

「他來自美國嗎？」 不是

「他來自亞洲嗎？」 是的

「他來自印度嗎？」 是的

「他是政客嗎？」 是的

「答案是甘地嗎？」 是的

指出他們沒有問 "是Adele嗎?"、"是Usian Bolt嗎" 這樣的問題，並進一步問他們為什麼沒問？

可以問他們認為哪個問題放在第一個問是最好的，他們有問到這個問題嗎？為什麼好？他們通常都會把是男性或女性當第一個或很前面的問題，鼓勵他們去思考這個問題特別的地方在哪？那這個問題好在哪裡呢？

這是因為無論答案是什麼，它都能排除一半的可能性。如果你一開始問「是愛黛兒嗎？」假如你是對的，那很恭喜你，你排除了所有錯誤答案，但如果你是錯的（通常是這樣），你就只能排除一個人。你要用這種問題來猜對答案的話，必須要有中樂透的運氣。所以問這「20個問題」的秘訣是提出排除一半可能性的問題。

如果你提出一系列如：「是閃電波特嗎？」這樣的問題，就相當於在做線性搜尋。這樣做的時候其實就是在腦中列出所有可能的名字並依次檢查。

能排除一半可能性的問題有多好呢？你可以做個簡單的效率分析：假設你一開始有一百萬個可能的名人，使用這樣的問題將人數減半，100萬，50萬，25萬，12.5萬，64000人﹝讓數字好看﹞，32000人，16000人，8000人，4000人，2000人，1000人，十個問題下來，發現可能的名人只剩1000個了。繼續問下去，你會發現過了20個問題之後，就只剩1個可能的名人了。

這說明了透過分治法來尋找東西﹝如這題的找名人﹞，可以大量提高我們的搜尋速度。如果使用線性搜尋﹝一次找一個﹞，那我們平均需要50萬個問題才能在100萬個裡面我們要找的東西。而用分治法就非常快速，只要每次都能完美的排除一半，我們只需20個問題就能從100萬個中找到我們要的東西了，顯然這個演算法快得多。

總結：

搜尋東西的時候，第一個想到的方法就是一個一個找，因為這是一個簡單的演算法，但缺點是非常的慢。分治法相較起來就快多了，它先解決一半的問題，使問題變小，然後再重複上面的步驟，這樣做著做著，非常快速的就會得到答案啦。

二元搜尋法是一種使用分治法的搜尋演算法，它假定你的資料是有順序的。它不會逐一檢查你的資料，而是直接到資料最中間，檢查你要的東西是更大或更小。因為我們的資料是照順序排列，你可以確定哪一邊是我們要的。接著一直重複上面的步驟，到剩下一個資料，再檢查是不是我們要的東西。這就像是我們在玩「20個問題」時用的分治法，每次排除一半的可能性。

從這裡我們可以學到一些運算思維：我們學到了一個解決問題的演算法﹝分治法﹞，它大大的加速了我們的任務，而且可以廣泛的運用在很多情況中。我們也看到了一種分析演算法的方法，使我們能夠比較那些處理相同問題卻以不同方式完成的演算法。這個方法教我們可以不用實際進行計時來衡量效率，而是可以用抽象的概念估算。最後，在我們遇到問題時，我們會自然而然的聯想到「20個問題」的遊戲或像是利用陣列，提供了我們解決搜尋問題的方法。

• 變化與延伸
  • Locked-in：

「20個問題」活動很適合接在"Locked-in"活動之後，可以用來引入線性搜尋作為一個解決方法來辨識一個只能眨眼的癱瘓病人在想哪個英文字母，看了它的效率之後，平均每13個問題能辨識出一個字母，指出任何計算機科學家都知道最糟只需要5個問題就能解決，可以先將此問題轉換到「20個問題」的遊戲，完成「20個問題」的遊戲後再回來看這題，有辦法利用分治法解決嗎？有的話，那是什麼樣的問題呢？答案是將字母數量減半，你可以先問「是M以前的字母嗎？」，這個說明了可以將一個問題的解決方案解決不同的問題，可從「Computational Thinking: Searching To Speak」這本書中看到這個故事。

• 實際演出二元搜尋小活動：

你可以讓學生們實際演出二元搜尋，發給每個學生一張寫著數字的卡片，並照順序排列。一位同學進行搜尋，一位同學出題，搜尋的同學到中間並詢問答案是比較大還是比較小，然後不符合的那一側同學坐下。搜尋的同學繼續到剩餘的人的最中間，重覆詢問，直到只剩一人站立為止。

• 搜尋電話簿：

為了使搜尋資料更具體，發電話簿或其他大書的目錄，並要求學生查找不同的名稱，讓學生想要用什麼方式進行查找，線性搜尋或是分治法，他們會去電話簿排序最中間的人尋找嗎？或者他們有更有效率的方法呢？如果是的話，可以請他們分享一下是如何辦到的，讓他們思考什麼時候需要切換到線性搜尋尋找東西，也讓他們思考電話簿中名稱的先後排序，還有什麼其他列表也是相同的概念？這些列表用來做什麼的？

• CS Unplugged：二元搜尋活動

另一個後續活動是CS Unplugged (www.csunplugged.org)的二元搜尋活動，介紹了分治法的一般思路，並給出一個直接的方式讓學生將他們的理解直接運用於問題上。

• 說明和虛擬碼：

讓學生們用自己的話來描述用於玩「20個問題」使用的演算法。也可以要求學習過虛擬碼的學生編寫以虛擬碼描述的演算法。

• 程式：

對於會編寫程式的高階學生，可以讓他們實做出不同的演算法，例如搜尋一個按照字母順序排列的的陣列。設計出會用分治法原理問問題的程式，並同時在螢幕上顯示出剩下的可能性。這樣的系統只要能連結到適當的輸入系統就真的可以讓癱瘓的人使用了！