小議Scratch在常見算法學(xué)習(xí)中的應(yīng)用

代天杰　于方軍

編者按：兒童的智能是多元的，同樣是Scratch，可以在藝術(shù)和工程領(lǐng)域大顯身手，也可以在科學(xué)和數(shù)學(xué)領(lǐng)域深度探究，算法思維一直以來(lái)是程序教學(xué)的難點(diǎn)，使用Scratch語(yǔ)言來(lái)講解復(fù)雜而重要的計(jì)算機(jī)算法，降低了難度，有助于算法思維的落實(shí)和拓展應(yīng)用。

Scratch讓編程變得足夠簡(jiǎn)單，降低了編程門檻，也讓孩子們體會(huì)到了編程的樂趣，那么Scratch是不是只能做一些簡(jiǎn)易的游戲，而不能進(jìn)行深入編程知識(shí)——算法的學(xué)習(xí)呢？于是，我們嘗試?yán)肧cratch去實(shí)現(xiàn)一些算法，發(fā)現(xiàn)Scratch真是非常強(qiáng)大，很多問題都可以輕松解決，教師完全可以利用Scratch教授一些算法和數(shù)據(jù)結(jié)構(gòu)，引導(dǎo)學(xué)生利用Scratch和算法知識(shí)去創(chuàng)作更加優(yōu)秀的作品。

為什么要學(xué)習(xí)算法？因?yàn)楹芏鄦栴}，前人已經(jīng)提出了非常好的解決方案，如果我們不去學(xué)習(xí)算法，就會(huì)浪費(fèi)大量的時(shí)間去思考，甚至很多問題我們無(wú)法想出解決方案，從而無(wú)法實(shí)現(xiàn)自己的想法。學(xué)習(xí)算法后，我們就可以利用這些知識(shí)快速解決問題，實(shí)現(xiàn)自己的想法，同時(shí)經(jīng)過算法學(xué)習(xí)訓(xùn)練，分析問題、解決問題的能力也會(huì)有很大的提高。

下面我們來(lái)列舉幾個(gè)Scratch算法的實(shí)例，希望能夠?qū)Υ蠹矣兴鶐椭?/p>

排序算法的學(xué)習(xí)

排序應(yīng)該是程序中最常用的算法，如看到一個(gè)利用Scratch統(tǒng)計(jì)中文錄入中鍵盤字母鍵敲擊次數(shù)的小程序，就可以利用排序排出每個(gè)字母的敲擊次數(shù)順序。

那么如何利用Scratch實(shí)現(xiàn)排序呢？Scratch雖然不支持二維數(shù)組，但它對(duì)一維數(shù)組支持得非常好，并且融合了很多字符串的操作，所以Scratch對(duì)一維數(shù)組的操作得心應(yīng)手。利用Scratch實(shí)現(xiàn)O（N2）的算法都非常容易，如插入、冒泡、選擇都可以，在這里我們以插入排序?yàn)槔秊榇蠹医榻B實(shí)現(xiàn)方法，為什么要選擇插入排序是因?yàn)镾cratch在鏈表中提供了插入功能，讓插入排序?qū)崿F(xiàn)起來(lái)非常容易。

插入排序就像我們打撲克時(shí)的插牌過程，其實(shí)插牌就是把自己摸到的牌，進(jìn)行從小到大的一次排序過程。我們?cè)趺床迮颇兀棵脚浦螅紫纫业竭@張牌的位置，從最后一張開始找，找到比這張牌小的牌，然后把這張牌插在后面就可以了。

我們以對(duì)5（一共要摸幾張牌）個(gè)數(shù)排序?yàn)槔瑏?lái)描述問題的實(shí)現(xiàn)步驟，鏈表a用來(lái)存儲(chǔ)數(shù)據(jù)，i表示已經(jīng)輸入多少個(gè)數(shù)（我們手中已經(jīng)摸了幾張牌）：①清空鏈表。②設(shè)置i為1。③輸入第一個(gè)數(shù)。④將第一個(gè)數(shù)插入鏈表。⑤將后面4個(gè)數(shù)插入鏈表。將i值加1、輸入第i個(gè)數(shù)、將位置j的值設(shè)置為i-1（也就是從最后一個(gè)數(shù)開始找）、找到比輸入的數(shù)小的數(shù)位置j或者位置j為0就停止、將輸入的數(shù)插入到j(luò)后面即可。

Scratch實(shí)現(xiàn)遞歸

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

這種遞歸算法和數(shù)學(xué)中的歸納法非常相似，關(guān)鍵步驟有兩步，第一能夠求出最簡(jiǎn)單情況下，如N等于1時(shí)的值，第二能夠找到由（N-1）到N的變化規(guī)律，我們?cè)賮?lái)看圖2。

圖2看起來(lái)非常漂亮，這是Scratch利用遞歸畫出來(lái)的，怎么能夠畫出這樣的圖片呢？通過認(rèn)真觀察，我們可以發(fā)現(xiàn)圖片的規(guī)律為：圖片是由一個(gè)個(gè)由小到大的正方形旋轉(zhuǎn)生成。

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

我們?nèi)绻美L制正方形的規(guī)律來(lái)繪制圖2的圖像，就要改變每次重復(fù)的步驟：①改變畫筆顏色，這樣可以實(shí)現(xiàn)變色效果。②畫一條邊。③旋轉(zhuǎn)91度，這樣可以實(shí)現(xiàn)正方形的旋轉(zhuǎn)效果。④邊長(zhǎng)加1，這樣可以實(shí)現(xiàn)正方形由小變大的效果，代碼如圖3所示。

Scratch實(shí)現(xiàn)回溯

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

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

怎么來(lái)畫這樣一幅圖呢？我們先來(lái)實(shí)現(xiàn)畫一條邊，利用Scratch的移動(dòng)L步和移動(dòng)0-L步就可以了，為什么還要移動(dòng)0-L步呢？目的是為了回到出發(fā)點(diǎn)。

我們?cè)賹?shí)現(xiàn)畫一個(gè)“丫”，實(shí)現(xiàn)步驟如下：①移動(dòng)L步。②畫左邊。向左旋轉(zhuǎn)30度，移動(dòng)L步，移動(dòng)0-L步。③畫右邊。向右邊旋轉(zhuǎn)60度，移動(dòng)L步，移動(dòng)0-L步。④回到起點(diǎn)。向左旋轉(zhuǎn)30度，移動(dòng)0-L步。

我們用遞歸來(lái)實(shí)現(xiàn)以上步驟，為了讓分支越來(lái)越短，可以逐步減少移動(dòng)步長(zhǎng)L，代碼如圖5所示。

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

Scratch作為一款圖像化編程軟件，簡(jiǎn)約而不簡(jiǎn)單，不僅能夠快速構(gòu)建程序而且功能十分強(qiáng)大，教師可以利用它來(lái)教授算法和數(shù)據(jù)結(jié)構(gòu)知識(shí)，讓學(xué)生了解更加深?yuàn)W的編程知識(shí)，培養(yǎng)學(xué)生的計(jì)算思維能力。此外從信息技術(shù)實(shí)驗(yàn)的角度，教師還可以引導(dǎo)學(xué)生比較不同算法的執(zhí)行效率，以加深其對(duì)以上這些初級(jí)算法的理解程度。