2022年6月10日 星期五

[micro:bit, maker] 小彼特一筆畫完

 小彼特一筆畫完

Line：ted2016.kpvs
Email：Lct4246@gmail.com
FB：http://gg.gg/TedLeeFB/
Blog：http://gg.gg/TedLeeBlog/

June 10, 2022
88x31.png[1]



馬上實作，拿在手上感受

我：你可以自己畫出一筆點亮所有 LED 燈嗎？
孩：可以，馬上用筆畫出兩種。
我：那能畫出所有可能點亮的方法嗎？
孩：A…（搔頭狀），沒辦法。
我：我也沒辦法，可能性有很多，而且我畫完四個也累了。但是，電腦不怕累，可以一直工作。我可以把任務交給它，讓他發揮專長。接著從口袋拿出小彼特展示給他看。頓時，小孩的眼睛閃閃發光，問說這怎麼辦到的？
─── 小彼特的超級優點就是：馬上實作，拿在手上感受。

問題說明

從小彼特的中心點出發，找出任一條可連接 25 顆 LED 的畫法，但已畫過的點不能再重複經過（圖 1 為四種可能的畫法）。讀者們可以使用圖 2 的學習單動手畫畫看，也可以相互比一比，看看誰能畫出最多種不同的走法。

圖 1：從中心點出發的四種畫法

圖 2：一筆畫完學習單

問題分析

首先，我們以圖 3 座標軸的第一象限來定位小彼特板子上的這 25 顆 LED。圖 4 為一筆畫完的走法分析，其中，圖 4 左黃色座標格表示圖 4 右選擇的走法。

圖 3：小彼特 25 顆 LED 定位座標軸

圖 4：走法分析

麥客友（ Escher Hsieh）的解方

我們在這篇 FB 分享文章（https://reurl.cc/QLkDa2）提到使用小彼特來實作的概念後，麥客友 Escher 立刻以遞迴（recursion）的程式設計技巧實作（implement）出這個問題的解法（https://reurl.cc/anDmvD）。
程式的想法很簡單：
邊往前畫邊灑下麵包屑作記號（遞迴），走不通就沿著麵包屑返迴（backtrack）再重新找路。其中，下一步的選擇順序（order） 如圖 5 中 1~4 的逆時鐘（counter clockwise）方向所示，即調整對應的 x 或 y 座標。

圖 5：尋路順序 

Ted Lee 的解析

首先，以圖 6 的方式定義了五個一維陣列 list0~4[] 代表小彼特板載 25 顆 LED 的狀態：

1 表示尚未走過；
0 表示已走過。

圖 6：陳列的初始狀態

另外，程式中定義了以下四個副程式來處理深度優先（Depth-First Search，DFS） [2] 的尋路方式：
  1. setLED()：設定 LED  (x, y) 是否被畫到（記錄變數 value = 0）。
  2. findPath()：遞迴找路副程式，這是這隻程式的菁華所在。它的設計邏輯是：
    往上下左右四個方向去甞試畫畫看。
    如果可以將 25 顆 LED 畫盡，那就是找到了一種畫法。
    否則，代表此路不通，退回前若干步後再換一條沒走過的路重試。
  3. shwoPath()：顯示找出的一筆畫完路徑（path）。
  4. getLED()：取得 LED (x, y) 的值（有畫到 (x, y)， value = 0；否則，value = 1）。
其中，它們之間的呼叫關係（call sequence）整理於圖 7 所示。

圖 7：副程式之間呼叫關係

最後，我們將 Escher 的程式碼再整理加註於此（https://reurl.cc/9GY3lx）供讀者細細詳參。

MakeCode 中的程式碼追蹤（code trace）技巧


上小節所整理的敘述除向原作者請益的結論之外，我們是用 MakeCode 裡的小瓢蟲（debugger）進入單步執行（single-step execution）的除錯模式（debug mode）來一步步模擬與追蹤程式的執行過程──這個程式「 閱讀」技巧目非常、超級重要，精熟它必定有助於讀懂他人程式碼的思考邏輯（圖 8）。其中，讀者可以比較一下由積木程 JavaScript 進入除錯模式的差異性。後者才有中斷點（breakpoints）可以插入觀察。

圖 8：MakeCode 的除錯模式

還可以怎麼玩

可能有讀者會和筆者一樣，小時候有玩過一筆畫一個圖案（https://reurl.cc/YvoNX4）或寫一個字（https://reurl.cc/NAm91p）。一筆畫問題在資訊科學（Computer Science，CS）領域有一個古典的研究叫尤拉路徑（Eulerian path）（https://reurl.cc/anDm9Q），而資訊科學家（computer scientists）也就從此開展出一串圖論（Graph Theory）問題的新研究領域，有興趣的讀者可以從此處再繼續深入研究之。

延伸思考

麥客友的參考作品給了我們一個思考的方向。讀者們，我們是否還能夠再進一步改良（improve）它呢？
  1. 從 (2, 2) 出發，共有幾種不同畫法？
  2. 隨機選出發點 (x, y)，x, y = 0~4？
  3. 為什麼程式找到路後不會停？能讓它停下來嗎？
  4. 能隨機找路嗎？

註：教學情境的營造──有溫度的畢典
疫情肆虐讓許多學校都只能辦遠距畢典。xx 的孩子們，你們的身體內都流淌著遠征探索的血液，xx 特使團將出動 SNG（Satellite News Gathering）車到每位畢業生家裡現場採訪，請規畫一條不重複而且能串連每個家庭的完美路線。
張貼者： 於
標籤： , , ,

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)