在打孔卡上搜尋資料

活動名稱: 打孔卡搜尋 the punch-card searching

教學時間：10~15分鐘+20分鐘去使用魔術技巧 引起大家興趣

教學單元：

• 搜尋演算法 （Search algorithms）
• 二進位數字 （Binary Numbers）
• 分治法（將一個大問題切成小問題各個擊破）（Divide and Conquer）
• 計算性思維: 翻譯轉化不同領域之間的問題（Computational Thinking: translating problems between domains）

教學目標：顯示電腦最早是如何使用魔術般的技巧搜尋資料。

對象：11歲以上 每組1人以上

先備知識：無

課前準備：

• 製作至少24張由A4卡製成的穿孔卡
• 一枝筆
• 有關二進位法的的講義或投影片

活動設計:

• 概要:

展示早期電腦是如何找到在打孔卡上的資料，並表現他所使用的演算法跟"澳大利亞魔術師之夢"中的魔術方法相同。他的目的是以視覺化的方法表現出搜尋演算法是如何作用。在這樣做時，你可以展現二進位法的實際運用、以分治法進行搜尋和探索計算性思維是怎麼在問題之中找到解決的辦法。

• 如何進行:

準備: 利用pdf後面畫好的圖案製作一套打孔卡，想要印無邊的話，你需要在印表機中選擇尺寸為"無邊框A4"。如果印表機沒有那個功能，就使用裁紙機裁去邊緣。 最好是印在薄紙卡上， 然後切出如虛線所示的凹口/孔。 在卡片上撒上滑石粉，可以讓卡片比較不會黏在一起，進行活動的時候也會比較順利。

吸引興趣: 可以利用Teaching London Computing （ www.teachinglondoncomputing.org）提供的"澳大利亞魔術師之夢"的魔術來吸引大家的注意。表演後說明這是早期電腦找尋在穿孔卡上的資料所使用的技巧。

• 活動內容

拿起一堆打孔卡，將他們洗牌後，呈現隨機的排列。 說明你是如何藉由魔術手法（Down-Under Deal）找到卡片。你將使用相同的演算法，要做到這一點，你只需要將數字寫在使用特殊孔槽作為代碼的卡上。

為了使它運作，你需要知道一些簡單的二進位表示法。 二進位是一種數字儲存在電腦中的方法，它與魔術中使用的孔槽代碼的想法是一樣的。

跟學生解釋二進位是以不同的方式編寫數字。 這是一個特殊的代碼，我們只能使用數字0和1而不是我們常用的數字0-9。 我們使用的十進位是以十為基底（Base），二進位是以2為基底。基底告訴我們可以使用多少不同的數字 - 不同的符號（symbol） 。 在基底10中，我們一個位數使用的數字最多數到9，當用完數字後，這個位數需要先歸零，同時進位1到下一個位數。在基底10中，數字16是1個10（1在十位），然後是6個1， 我們將10和6加起來獲得數字16，同樣的987意味著9個100、8個10和7個1加在一起。

100 10 1

x 9 8 7

= 900 + 80 + 7

二進位的運算方式與剛剛是相同的方法，只是我們一個位數的數字最多只能用到1就要進位了，而不是用到9，取代個位 十位 百位，每一行所代表的是個位，二位，四位，八位（1s，2s，4s，8s）等。 我們用二進制寫下5這個數字（僅使用數字1和0）為101。它是1個四位加0個二位加1個個位。

5 在二進位中 是00101

16 8 4 2 1

x 0 0 1 0 1

= 0 + 0 + 4 + 0 + 1

同樣地， 16在二進位中是10000

16 8 4 2 1

x 1 0 0 0 0

= 16 +0 + 0 + 0 + 0

這與打孔卡有什麼關係呢？（在解釋的時候把打孔卡拿出來）我們將二進位數字的0用孔代表，1用槽代表（槽：將孔洞上面的紙再挖掉，讓它沒辦法再用東西固定）。

為了將數字5（二進位為00101）放在打孔卡上，從左邊開始，我們需要一個孔，另一個孔，然後一個槽（slot），一個孔，最後一個槽。 對於數字16，我們需要一個槽然後剩下的都是孔。 一個有5個孔的卡，我們可以讓卡片代表0~31任意一個數字。 只要有了足夠的孔，我們可以用打孔卡來代表任何的數字。

一旦我們將卡片上的數字以上述使用孔槽的二進位法表示，我們可以很容易找到任何我們想要的卡片。我們只需要用這個魔術手法（Down-under deal）的變形，應用在我們想要找的二進位數字上。具體做法如下:

0:表示丟棄下面那推

1:表示留下下面那堆

拿起堆疊的卡片將孔洞對齊排成一行，將一根鉛筆依次放置每個位置，在移動到下一個位置之前，要把所有在那個位置有槽的卡搖出來。鉛筆從最右邊（個位數）的地方開始，並通過二進位數字決定如何處理搖出的卡片，這樣就可以留下任何你想要的卡片。 使用上面的代碼：如果那個位置是二進位數字的0，那麼就丟棄下面（掉下來）的那堆，如果那個位置是1的話，那麼就保留下面那堆。

讓我們來看個例子 （透過剛剛上述我們所解釋的步驟）

找到數字16的卡片，他的二進位法表示為10000，從右開始

0: 丟掉掉下去的那堆

0: 丟掉掉下去的那堆

0: 丟掉掉下去的那堆

0: 丟掉掉下去的那堆

1: 留下下面那堆

我們重複丟掉下面的那堆卡片直到第五次我們才保留下面那堆。這個正是我們在那個魔術中做的事!

讓我們再看一個例子， 找到5這張卡片，他的二進位法表示為00101 從右開始:

1: 留下掉下去的那堆

0: 丟掉掉下去的那堆

1: 留下掉下去的那堆

0: 丟掉掉下去的那堆

0: 丟掉掉下去那堆

我們可以留下5這張卡片，藉由拼出二進位的數字，我們可以透過這個方法找到任何你想要找到的卡片!

這可以讓我們用很視覺化的方式來示範搜尋演算法。 我們有很多不同面向的解釋，但是我們現在要進行更深入的探討。

若只是想簡單的說明為甚麼它的演算法跟魔術一樣，只要示範它們在第一回合都移除同樣的卡片，並注意每個回合都以相似的方法將第奇數個卡片移除。

如果你想要有更深入的了解，以下的內容有更多的解釋。

想想看當你搖掉卡片會發生甚麼事。 這個和使用Down-under deal 手法的魔術發生的事情是相同的。以第一回合被丟棄的卡片為例:搖出所有在第一個位置有槽的卡片，第一個位置也就是在二進位法中的個位數（2的零次方） 。 數字1,3,5,7等等都在這個位置會有一個槽（一個 1） ，所有的奇數都有這個特性。 這是因為我們個位數在計數時00，01，10，11是兩個一循環。最後一個位置是0，1，0，1.....。 這與基底10沒有什麼不同基底10的話，我們有更多的數字，所以計數0，1，... 9，0，1，... 9以此類推。用另一種方式想想看，當你將每個位數的數字加起來（如5 = 4 + 0 + 1），最後一個位數（個位）是決定是否為奇數的關鍵，因為其他位數代表的都是偶數!

取完奇數數字卡片後，我們進行到打孔卡的下一個孔洞，（即二進位法的下一個位數），搖出所有含有由2這個數字組合成的數字，舉6為例，6的二進位表示為:110，因為6=4+2+0。此時我們的孔洞位數是2的1次方，所以會掉落的數字是2、3、6、7、10、11....所有2的1次方有孔洞的數字，但我們奇數數字已經在第一回合都搖掉了，所以實際上會移除的數字是2、6、10.... 。這樣會和使用（down-under deal）方法在第二回合移除的卡片結果相同，使用down-under deal方法在第一回合也會先將奇數的卡片丟掉，丟掉的方法是每隔一張卡片就移除。再一次以二進位的計數系統想想，第二位數會從零開始數，0、1、0、1、0、1，跟個位數相同，只是第二位數只有在第一位數從1數到零的時候才會發生變化，這可以看成下面的結果:

0 0 0

0 0 1

______

0 1 0

0 1 1

_______

1 0 0

1 0 1

________

1 1 0

1 1 1

這個和我們每回合移除卡片時發生的事情相同， 我們實際上將剩下的卡片每隔一張的移除。和那個魔術不同的是打孔卡是有洗牌的，第幾張卡片不能由它的位置，而是要由他的孔洞來判斷。另一個不同的是打孔卡可以一次就將所有的卡片移除，然而使用魔術手法（down-under deal）的方法要很無聊地在每回合一張一張將卡片移走。所以使用打孔卡版本會非常快速。如果你想要的話，魔術和打孔卡版本可以用來說明循序搜尋法和平行演算法的不同。

這個演算法可以用分治法快速的找到卡片，在每一個回合我們移去剩下卡片中的一半，我們要如何在剩下的卡片裡面繼續搜尋呢？我們要再做一次同樣的事情，只是從二進位數字中不同的位數。將其與我們依次檢查每張卡片的演算法（也就是線性搜尋法）進行比較。分治法更快速、精準，因為它將問題的範圍縮小成一半。

基本上，我們已經說明魔術和數學的搜尋方法實際上是運用相同的演算法，一個問題的解決辦法（使用魔術效果娛樂觀眾）同時也是其他問題的解決辦法（從一堆卡片中找出要的卡片）。這就是運算思維很重要的一個特性：他能在不同問題領域之間轉換。某個知道這個魔術的人可以使用它作為基本解決搜尋問題的方法。同樣地，一個知道搜尋演算法的魔術師可以以此為出發發明其他魔術。實際上，有很多魔術技巧都是源自演算法的！

我們可以用搜尋演算法的想法來發明新的、應用運算思維的魔術。我們已經看到，藉由丟掉或留下搖出來的卡片，我們可以找到任何卡片。我們可以根據這個觀察結果來發展一個不同的版本，我們可以預測每張卡片原本放置的位置，而不是僅僅只能預測放在第16個的卡片，運算思維可以帶領我們創造一個新的魔術。

• 變化與延伸
  • 製作一套打孔卡:

讓班級製作一套屬於自己的打孔卡，然後讓他們知道每個槽在卡片上代表的意義。在後面有提供空白的打孔卡。

• 把學生當作二進位數字:

為了展示二進位數字，找一排學生當作數字，可以讓學生拿著數字1和數字0的卡片，以及讓每個位置代表一個位數（1、2、4、8等等），另一種替代方法，可以讓學生站著代表1，坐著（或捲曲身體像球一樣）代表0。可以參考CS Unplugged binary number activity（www.csunplugged.org）的想法去介紹二進位法。

• 打孔卡的排序（更具挑戰性）

告訴班上的同學可以利用同一種魔術手法（down-under style deals），在一副卡片中藉由移動打孔卡，來保證那副卡片會以數字的順序儲存‵‵。讓他們挑戰看看！

• 進一步閱讀:

計算機科學的魔術:

有很多關於計算機科學的技巧可以從這個網站取得 (http://www.cs4fn.org/magic/) ，裡面包含許多免費的魔術書籍。