排序打孔卡

活動名稱: 排序打孔卡 the punch-card sorting

教學時間: 10-15分鐘以上(主要取決於解釋時間的多寡)

教學單元:

• 排序演算法 (Sort algorithms)
• 二進位的基數排序法 (Binary Radix Sorting )
• 分治法 (Divide and Conquer)
• 計算機思維:定程式思考 (Computational Thinking: algorithmic thinking )
• 二進位的實際用途 (Practical uses of binary )

教學目標: 展示電腦早期是如何將儲存在打孔卡上的資料排序

對象: 11歲-成人 每組1人以上

課前準備:

• 一套由A4紙製成的打孔卡
• 一枝筆
• 有關二進位數字的講義或說明 (see linked slides at www.teachinglondoncomputing.org)

活動設計:

• 如何進行:

準備: 藉由附在後面幾頁的圖案製作一套打孔卡，想要印無邊的話，可以在印表機中選擇"無邊框A4"，如果你的印表機沒有這個功能，就用裁紙機才去邊邊。最好是將圖案印在薄紙上。然後沿著紙上的點點裁出孔。撒上滑石粉可以避免紙黏在一起，讓活動進行得更順利(這個演算法會因為紙黏在一起而發生錯誤)

• 活動內容:

拿起一疊打孔卡，並將他們洗個牌，這樣就能讓他們隨機的排列。說明你可以運用一點計算的魔術立刻將他們以順序排列好拿回來。

將筆放置在最右邊(標誌1)那個孔，然後小心地搖出所有快掉下來(鬆鬆)的卡片，確保每張卡片都有掉下來沒有卡住，搖完後將所有卡片收集起來，再來我們將重複剛剛的動作，只是現在筆是放在右邊數來第二個(標誌2)孔，搖出卡片並將搖出的卡片重新放回原來的那疊卡片中，然後重複剛剛的步驟，只是將筆放在下一個孔。讓學生說明這是怎麼發生的？ 這是魔法嗎？

二進位法:

為了瞭解這個活動你必須要知道二進位法，實際上，二進位相當的實用。二進位法是一個代表數字很有用的方式，它可以替代我們所使用的十進位法，但二進位法你只能使用0和1兩個數字，而不是像十進位可以用0~9。在十進位中，當你數到9之後要進位到下面一個位數，而二進位當你數到1之後就要進位到下面一位，在之後的位數也是使用同樣的概念：數到10之後到11，然後就要進位變成100 你可以數:0、1、10、11、100、101、110、111....

在打孔卡上的二進位

我們利用打孔卡上的孔洞來代表二進位數字

• 一個孔代表0
• 一個槽(下面圖片中將孔洞上面再沿虛線剪掉 )代表1

以5為例，他的二進位法表示為00101，所以它的孔槽圖案在卡上就會呈現(左到右) 孔-孔-槽-孔-槽 或是說0-0-1-0-1

二進位基數排序法

我們接下來要做的事情就是被叫做二進位基數排序法的排序演算法，讓我們看一個它作用的例子。假設你必須將卡片從0數到7依序排列:

3、5、6、1、2、0、4、7

用二進位表示的話:

011 101 110 001 010 000 100 111

3 5 6 1 2 0 4 7

如果我們以最右邊那個位置有沒有1將這些數字分成兩堆(也就是將奇數跟偶數分開)

011 101 001 111 和 110 010 000 100

3 5 1 7 6 2 0 4

再來我們將那些最右邊位置有1的數字排到後面去 保持原本數字的相對位置， 就會變成下面的結果

110 010 000 100 011 101 001 111

6 2 0 4 3 5 1 7

再來往比第一位數大的那一位數(從右邊數來第二位)比較，將小的往前擺 大的往後擺 可以得到下面新的組合

000 100 101 001 110 010 011 111

0 4 5 1 6 2 3 7

接下來，我們再往比第二位數大的那位數比較，再將大的放在小的後面，

最後得到的結果會是:

000 001 010 011 100 101 110 111

0 1 2 3 4 5 6 7

我們只花三個步驟就將他們排序好了!!!

這個演算法有兩個很快的原因，首先，比較是同時進行的，所以在一次的操作中(藉由筆和重力的幫助)，卡片將在檢查位數時分成兩堆，很多的動作在每一步進行著，這也就顯示了平行演算法強大的功能。

它的效率也相當好，這個演算法正是用分治法的形式解決問題，每個步驟都將問題減半，它留下一個本質上一樣但卻是比原本一半大的新問題。一個排序的問題仍然存在著，但是重點是留下更少的位數需要被排序

對這個演算法來說，一副牌在每次都被分成一半，分類的準則取決於一個位數中是否有1或0， 每一次的操作都會進行排序直到二進位數字的下一個位數，經過一次在第一個位數的操作後，卡片將會被儲存成(0，1)的順序，經過第二個位數的操作後， 會被儲存成(00、01、10、11 )以此類推...

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

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

• 學生的二進位數字:

為了向同學展示二進位數字，找一排同學當作數字，可以讓學生拿著數字1或0的卡片，以及讓每個位置都代表一個位數(1、2、4、8....)，也可以讓學生站著代表1， 坐著(綣曲成球狀)代表0。可以參考CS Unplugged binary number activity(www.csunplugged.org)的想法去介紹二進位法。

• 搜尋打孔卡:

刺激班上同學想出一個相似的演算法，不同的是這個演算法藉由丟掉片得到你想要的卡片，(所得到的算法是下面那些活動的基礎 見 下文)

• 進一步閱讀:

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