小議Scratch在常見算法學習中的應用

代天杰　于方軍

編者按：兒童的智能是多元的，同樣是Scratch，可以在藝術和工程領域大顯身手，也可以在科學和數學領域深度探究，算法思維一直以來是程序教學的難點，使用Scratch語言來講解復雜而重要的計算機算法，降低了難度，有助于算法思維的落實和拓展應用。

Scratch讓編程變得足夠簡單，降低了編程門檻，也讓孩子們體會到了編程的樂趣，那么Scratch是不是只能做一些簡易的游戲，而不能進行深入編程知識——算法的學習呢？于是，我們嘗試利用Scratch去實現一些算法，發現Scratch真是非常強大，很多問題都可以輕松解決，教師完全可以利用Scratch教授一些算法和數據結構，引導學生利用Scratch和算法知識去創作更加優秀的作品。

為什么要學習算法？因為很多問題，前人已經提出了非常好的解決方案，如果我們不去學習算法，就會浪費大量的時間去思考，甚至很多問題我們無法想出解決方案，從而無法實現自己的想法。學習算法后，我們就可以利用這些知識快速解決問題，實現自己的想法，同時經過算法學習訓練，分析問題、解決問題的能力也會有很大的提高。

下面我們來列舉幾個Scratch算法的實例，希望能夠對大家有所幫助。

排序算法的學習

排序應該是程序中最常用的算法，如看到一個利用Scratch統計中文錄入中鍵盤字母鍵敲擊次數的小程序，就可以利用排序排出每個字母的敲擊次數順序。

那么如何利用Scratch實現排序呢？Scratch雖然不支持二維數組，但它對一維數組支持得非常好，并且融合了很多字符串的操作，所以Scratch對一維數組的操作得心應手。利用Scratch實現O（N2）的算法都非常容易，如插入、冒泡、選擇都可以，在這里我們以插入排序為例為大家介紹實現方法，為什么要選擇插入排序是因為Scratch在鏈表中提供了插入功能，讓插入排序實現起來非常容易。

插入排序就像我們打撲克時的插牌過程，其實插牌就是把自己摸到的牌，進行從小到大的一次排序過程。我們怎么插牌呢？摸到牌之后，首先要找到這張牌的位置，從最后一張開始找，找到比這張牌小的牌，然后把這張牌插在后面就可以了。

我們以對5（一共要摸幾張牌）個數排序為例，來描述問題的實現步驟，鏈表a用來存儲數據，i表示已經輸入多少個數（我們手中已經摸了幾張牌）：①清空鏈表。②設置i為1。③輸入第一個數。④將第一個數插入鏈表。⑤將后面4個數插入鏈表。將i值加1、輸入第i個數、將位置j的值設置為i-1（也就是從最后一個數開始找）、找到比輸入的數小的數位置j或者位置j為0就停止、將輸入的數插入到j后面即可。

Scratch實現遞歸

Scratch雖然不支持函數但是對過程的支持非常好，所以利用Scratch可以非常容易實現遞歸算法。我們舉最常用的遞歸例子，求N的階乘，N！=（N-1）！×N這個公式是遞歸算法的核心，如我們定義了一個過程階乘（N），那么階乘（N）就等于階乘（N-1）乘N。我們用s來表示N的階乘。如果N等于1，那么很顯然s的值就是1，如果N不等于1，那么我們可以先計算（N-1）的階乘s，然后N的階乘s等于我們已經計算出的（N-1）的階乘s乘N，實現代碼如圖1所示。

這種遞歸算法和數學中的歸納法非常相似，關鍵步驟有兩步，第一能夠求出最簡單情況下，如N等于1時的值，第二能夠找到由（N-1）到N的變化規律，我們再來看圖2。

圖2看起來非常漂亮，這是Scratch利用遞歸畫出來的，怎么能夠畫出這樣的圖片呢？通過認真觀察，我們可以發現圖片的規律為：圖片是由一個個由小到大的正方形旋轉生成。

依據這一規律我們就可以研究繪制圖片的算法，首先要研究怎么繪制一個正方形。畫正方形時，可以先沿水平方向畫一條邊，然后向右旋轉90度，再畫一條邊，再旋轉，再畫，這樣就有三條邊了，最后旋轉一次畫一條邊，正方形就畫好了；也就是說畫正方形就是重復執行4次“畫一條邊，向右旋轉90度”的操作。

我們如果要利用繪制正方形的規律來繪制圖2的圖像，就要改變每次重復的步驟：①改變畫筆顏色，這樣可以實現變色效果。②畫一條邊。③旋轉91度，這樣可以實現正方形的旋轉效果。④邊長加1，這樣可以實現正方形由小變大的效果，代碼如圖3所示。

Scratch實現回溯

回溯算法也叫試探法，它是一種系統地搜索問題的解答過程的方法。回溯算法的基本思想是：從一條路往前走，能進則進，不能進則退回來，換一條路再試。

由于Scratch目前不支持局部變量，所以比較容易實現雙分支問題也就是我們常說的01背包問題，而對于更多的分支問題只能用非遞歸算法來實現。在講回溯算法的時候，很多書都會畫一個樹狀的分形圖來描述回溯的過程，利用Scratch可以動態展示這樣一個回溯的過程（如圖4）。

怎么來畫這樣一幅圖呢？我們先來實現畫一條邊，利用Scratch的移動L步和移動0-L步就可以了，為什么還要移動0-L步呢？目的是為了回到出發點。

我們再實現畫一個“丫”，實現步驟如下：①移動L步。②畫左邊。向左旋轉30度，移動L步，移動0-L步。③畫右邊。向右邊旋轉60度，移動L步，移動0-L步。④回到起點。向左旋轉30度，移動0-L步。

我們用遞歸來實現以上步驟，為了讓分支越來越短，可以逐步減少移動步長L，代碼如圖5所示。

我們還嘗試用Scratch編寫經典的編程問題N皇后問題，限于篇幅就不在本文中給大家介紹了，感興趣的老師可以到以下網址下載。（http：//yunpan.cn/cQTZFLRQucymw，訪問密碼為7761）

Scratch作為一款圖像化編程軟件，簡約而不簡單，不僅能夠快速構建程序而且功能十分強大，教師可以利用它來教授算法和數據結構知識，讓學生了解更加深奧的編程知識，培養學生的計算思維能力。此外從信息技術實驗的角度，教師還可以引導學生比較不同算法的執行效率，以加深其對以上這些初級算法的理解程度。