01-6. 勇者之旅
Computer Science activities with a sense of fun: night’s Tour V1.1, 14 Dec 2014
Created by Paul Curzon, Queen Mary University of London for Teaching London Computing: http://teachinglondoncomputing.org
Adapted from an idea by Maciej Syslo.& Anna Beata Kwiatkowska, Nicolaus Copernicus University
本教材以創用CC 3.0 姓名標示-非商業性-相同方式分享釋出(creative commons 3.0 BY-NC-SA) https://creativecommons.org/licenses/by-nc-sa/3.0/deed.zh_TW
遊戲說明:
1. 每個人需要一份移動規則表、一張空白迷宮方格圖以及一張已經畫好的圖形迷宮圖、一個「勇者卡片」、兩張路線記錄表(一張空白及一張路線說明)以及一支筆。
2. 跟旅遊嚮導活動一樣,先在一般圖形上設計勇者的探索路線。用紅筆標示想走的路線,起點的編號為1,最終必須造訪過所有12個房間,然後回到迷宮的起點。
3. 接下來,使用空白的迷宮方格,以及發下去的移動規則表,起點設在方格編號1的位置。勇者移動時必須按照移動規則表來進行,最後的目標一樣是要讓勇者踏遍所有的12個房間,再回到起點。
4. 任意與同學交換你設計出來的造訪步驟,必須讓別人也能按照你的設計完成目標,這才是一份有效的設計。
5. 思考一下,你覺得圖形的表示法比較容易協助你解決問題,還是迷宮方格比較容易?其實,如果把最後的終點一樣設成要回到編號1的房間,無論是旅遊嚮導或是勇者之旅,其實兩者是差不多的問題(這個動作稱為一般化generalise)。
6. 試著按照拿到的移動規則表,用「圖形」的方式設計出探索路線圖。每個房間設定成一個節點,就算房間原本是放置在隔壁的,按照規則重畫之後它將不見得還是會放在隔壁。路線連接之後的結果可能是任意形狀與大小,每個人的設計可能不見得一樣。
7. 舉個例子,按照移動規則表,1號房間之後的移動選擇可能是9號房間,而到達9號房間之後可以擇退回1號或是前進3號房間,如此即可完成一張圖形。但是進行第一步驟時,1號房間可能選擇走到7號,如此接下來繪製的圖形將會完全不同。
8. 等圖形完成之後,再試著完成路線設計表,看看有沒有變得比較簡單了。
1. 移動規則表
2. 空白迷宮圖
3. 圖形迷宮圖
4. 空白記錄表
![](https://www.google.com/images/icons/product/drive-32.png)
參考解法:
運算思維:
除了在旅遊嚮導活動中學到的思維之外,在這裡我們學到了模式匹配(pattern matching)的概念。在重新繪製勇者移動的圖形之後,我們會發現其實它跟上一個活動的城市圖形是一模一樣的,只是把景點的名稱替換成阿拉伯數字的編號罷了。
另外,應用在規劃路線的方式,就是一直往尚未走過的房間前進,稱為深先搜尋(depth-first search)。而另一種策略稱為廣度優先搜尋(breadth-first search),像是先將所有從1號房間通往9號房間的可能路線先畫出來,接著畫出所有通往6號房間的路線。這兩者都是圖形遍歷演算法(graph traversal algorithms)的一種。