01-8. 交換式謎題
Computer Science activities with a sense of fun: The Swap Puzzle V1.0, 17 February 2014
Created by Paul Curzon, Queen Mary University of London with support from the Mayor of London for Teaching London Computing: http://teachinglondoncomputing.org
本教材以創用CC 3.0 姓名標示-非商業性-相同方式分享釋出(creative commons 3.0 BY-NC-SA) https://creativecommons.org/licenses/by-nc-sa/3.0/deed.zh_TW
透過小組的合作，發展出一套最合適的演算法，運用它就能比別的小組更快地解決這個謎題。
這個活動的主要目的，在於說明我們總是可以發展出一套指令來解決一個問題，其他人只要拿到這份指令，就算他並不了解其中的原理，只要照著執行，同樣地也能解決同樣的問題。它也告訴我們演算法也是有優有劣的，只要能夠更快速地解決問題，我們就認為它是一套比較好的演算法。
在這個單元可以學習到:
- 演算法
- 運算思維
- 測試
- 效能
活動說明:
1. 小組的工作目標：在規定的時間內寫出一套解決問題的演算法（越快越好），而且這套演算法必須實際可行。
2. 我們需要：遊戲盤（Level 1~3，每個小組一份），顏色卡（一份之中有紅色3張、藍色3張，每組一份），規則說明以及演算法記錄表，方塊編號表示卡，倒數計時器，以及7張椅子。
3. 每個小組3到5人。
4. 遊戲目標：遊戲盤兩端各自有藍色格子與紅色格子（中間有唯一的一格空白格子），但是上面放置的卻分別是紅色卡片與藍色卡片。我要們透過一連串的指令移動卡片，想辦法讓格子與卡片的顏色相符。
5. 移動卡片的方式只允許：
(1) Move: 移動一張卡片到相鄰的空白格子處。
(2) Jump: 拿取一張卡片跳躍一格至空白格子內。
6. 遊戲盤有三個不同的難度
Level 1: 三個格子，紅色、空白及藍色格子各一，紅色及藍色卡片各一，限時30秒。
Level 2: 五個格子，紅色、藍色格子各二，空白格子一格，紅色及藍色卡片各二，限時1分鐘。
Level 3: 七個格子，紅色、藍色格子各三，空白格子一格，紅色及藍色卡片各三，限時2分鐘。
7. 演算法記錄表的指令書寫格式為（這是一般程式語言的語法邏輯）：
目標TO：要將方格紙放到哪一個格子
指令COMMAND：移動方格紙的方式(移動或是跳躍)
來源FROM：這張方格紙來自於哪一個格子
1-5演算法記錄表.doc(註：這種步驟的寫法與一般程式的語法很類似：get 方格編號x from 方格編號y)
8. Level 1為示範盤，由老師講解遊戲規則並示範如何進行，Level 2與3則是由學生進行。
9. 如何驗證演算法：
(1) 按照遊戲盤的難度，放置相對應的椅子，在椅子前方放置方格的編號以顏色的標記。
(2) 發展演算法的小組負責提供人員，拿著顏色卡按照藍色坐紅色格子、紅色坐藍色格子的方式就座。
(3) 隨意指令另一個小組，拿著就座組別所發展的演算法逐一令成員執行指令，檢視最後的結果是否正確達成目標。
10. 多做一次嘗試，這次試著更快速地寫完演算法，或是用更少的步驟達成目標。
運算思維:
前面的活動，我們已經嘗試過設計了不同的演算法，只要按照設計好的指令執行，無論下次是由誰來做，同樣的問題都該被順利解決。對於電腦科學來說，發展演算法時必須先經過實際的驗證，確認不會出錯之後，透過程式語言的指令來包裝這套演算法，下次要解決同樣的問題，只要按下執行鍵或是輸入執行的命令就好了。
另一個關於發展演算法所必須注意的事就是「效率」了。所謂有效率的演算法，可能是在解決問題時花費更少的時間，或是耗費更少的資源。同樣想要解決一件事，可以用很複雜、很慢的方式來處理，或是僅僅使用少少的步驟就將事情給完成，應該沒有人想要用電腦撰寫出一套很慢的程式吧？或是說應該沒有人想要選擇同樣功能、卻是執行得很慢的程式。
衡量一套演算法的效率，主要是看看它解決問題時所需要的步驟數量，而並非執行每一個步驟所執行的時間。隨著難度的上升，想要發展出有效率的的演算法，就必須更注重每一個步驟的細節，要思考的層面當然就更多。
為什麼在活動中，要將一個小組發展的演算法，交給另一組來實際執行看看？因為在發展演算法時常會陷入一個盲點，很難發現其中的問題，所以必須經過詳細的測試，才能確認演算法的運作是正確無誤的。
1-5演算法記錄表(參考解法).doc