程式的想法很簡單:
邊往前畫邊灑下麵包屑作記號(遞迴),走不通就沿著麵包屑返迴(backtrack)再重新找路。其中,下一步的選擇順序(order) 如圖 5 中 1~4 的逆時鐘(counter clockwise)方向所示,即調整對應的 x 或 y 座標。
圖 5:尋路順序
Ted Lee 的解析
首先,以圖 6 的方式定義了五個一維陣列 list0~4[] 代表小彼特板載 25 顆 LED 的狀態:
1 表示尚未走過;
0 表示已走過。
另外,程式中定義了以下四個副程式來處理深度優先(Depth-First Search,DFS) [2] 的尋路方式:
- setLED():設定 LED (x, y) 是否被畫到(記錄變數 value = 0)。
- findPath():遞迴找路副程式,這是這隻程式的菁華所在。它的設計邏輯是:
往上下左右四個方向去甞試畫畫看。
如果可以將 25 顆 LED 畫盡,那就是找到了一種畫法。
否則,代表此路不通,退回前若干步後再換一條沒走過的路重試。 - shwoPath():顯示找出的一筆畫完路徑(path)。
- getLED():取得 LED (x, y) 的值(有畫到 (x, y), value = 0;否則,value = 1)。
其中,它們之間的呼叫關係(call sequence)整理於圖 7 所示。
圖 7:副程式之間呼叫關係
MakeCode 中的程式碼追蹤(code trace)技巧
上小節所整理的敘述除向原作者請益的結論之外,我們是用 MakeCode 裡的小瓢蟲(debugger)
進入
單步執行(single-step execution)的
除錯模式(debug mode)來一步步模擬與追蹤程式的執行過程──這個程式「 閱讀」技巧目非常、超級重要,精熟它必定有助於讀懂他人程式碼的思考邏輯(圖 8)。其中,讀者可以比較一下由積木程 JavaScript 進入除錯模式的差異性。後者才有中斷點(breakpoints)可以插入觀察。
圖 8:MakeCode 的除錯模式
還可以怎麼玩
延伸思考
麥客友的參考作品給了我們一個思考的方向。讀者們,我們是否還能夠再進一步改良(improve)它呢?
- 從 (2, 2) 出發,共有幾種不同畫法?
- 隨機選出發點 (x, y),x, y = 0~4?
- 為什麼程式找到路後不會停?能讓它停下來嗎?
- 能隨機找路嗎?
註:教學情境的營造──有溫度的畢典
疫情肆虐讓許多學校都只能辦遠距畢典。xx 的孩子們,你們的身體內都流淌著遠征探索的血液,xx 特使團將出動 SNG(Satellite News Gathering)車到每位畢業生家裡現場採訪,請規畫一條不重複而且能串連每個家庭的完美路線。