陣型繪畫或克隆問題

陣型模式的繪畫或克隆題，也是重大考試中經(jīng)常出現(xiàn)的主題，如下圖：

都是近年來出現(xiàn)在藍(lán)橋杯或等考題中的題型。

這些陣型圖包括：正方形，等腰三角形，倒三角形，菱形等造型。有的需要通過克?。ɑ驁D章）角色來形成，有的是通過畫筆來畫出。

對于這類題，我們解決思路是：

1、決定起始位置（通常是左上角的坐標(biāo)）；

2、找出圖形的規(guī)律（包括圖形的形狀、行縮進(jìn)、行間距、列間距等變量）。

我們以下圖為例，來給出三角形的陣型圖：

其中，小黃球是一個角色。

為便于編寫程序，我們可以定義以下變量：

能過雙重循環(huán)來實現(xiàn)整個過程，外層循環(huán)控制行數(shù)（Y軸方向），內(nèi)層循環(huán)控制列數(shù)（X軸方向，每行的元素個數(shù)）。

每完成一行后，調(diào)整行道位置即可，示例代碼如下：

這類題本身難度不大，往往結(jié)合其他問題來構(gòu)成一個整體，但因為涉及到到的變量的應(yīng)用、雙重循環(huán)等，所以，也是考試中經(jīng)常出現(xiàn)的題型。如：

第15屆藍(lán)橋青少省賽Scratch初級組第3題：畫西瓜

第15屆藍(lán)橋青少省賽Scratch中級組第5題：妖怪矩陣

第14屆藍(lán)橋杯Scratch圖形化編程國賽中級組第6題：太空大戰(zhàn)

子串匹配問題

例（第15屆藍(lán)橋青少省賽Scratch中級組第6題：截取遞增數(shù)）：

給你一個不含 0的九位數(shù)，請找出從這個九位數(shù)中能截取出的所有遞增數(shù)。例如：115367482能夠截取出的遞增數(shù)有：15、36、 67、367、48。注意：只能截取若干個連續(xù)的數(shù)。

所謂遞增數(shù)，即，如果一個大于9的正整數(shù)各個數(shù)位上的數(shù)，從左到右是逐漸變大的，那么就稱這個數(shù)為遞增數(shù)。例如：124、248 是遞增數(shù)。

相似的問題，還包括：

截取遞減數(shù)： 從左到右嚴(yán)格遞減

波峰數(shù)（或波谷數(shù)）：即一個數(shù)的中間數(shù)字同時大于（波峰）或小于（波谷）左右相鄰數(shù)字，如：

波峰數(shù)：142（4是峰），253（5是峰）

波谷數(shù)：354（5是谷），131（3是谷）

回文子串（對稱數(shù)）：即一個子串正讀反讀相同；

奇偶交替數(shù)等。

這些題的特點是：要求從一個長串?dāng)?shù)字中截取連續(xù)的子串，并篩選滿足特定條件（如遞增、遞減、回文等）的子序列。

通常，這類題的解法是：

1、枚舉法（窮舉法）

也就是枚舉出長序列中所有的子串，找出符合要求的子串，其一般步驟為（以上面的截取遞增數(shù)為例）：

a. 遍歷所有可能的連續(xù)子串

從九位數(shù)中截取長度為2到9的所有連續(xù)子串（因為遞增數(shù)必須>9，最小長度為2）。

示例：數(shù)字115367482

長度為2的子串：11, 15, 53, 36, 67, 74, 48, 82

長度為3的子串：115, 153, 536, 367, 674, 748, 482

...（直到長度為9的整個數(shù)）。

b. 檢查子串是否為遞增數(shù)（ 從左到右依次比較相鄰數(shù)字）

c. 輸出符合條件的子串（保存到列表中）

在編程時，我們可以設(shè)置內(nèi)外兩重循環(huán)，如：

外層循環(huán)i：遍歷子串長度（1到8），內(nèi)層循環(huán)j：遍歷起始位置（i+1,9）。

截取子串后，可通過一個子過程（自定義積木）判斷子串是否遞增，若滿足條件，加入遞增數(shù)列表，示例如下（非完整代碼）：

2、 滑動窗口法

如圖：

我們可以定義兩個指針變量（left ,righ），分 別標(biāo)記子串的左右邊界，遍歷數(shù)字時，動態(tài)擴(kuò)展窗口，僅檢查連續(xù)遞增的序列，如果不再遞增，則更新變量的值，判斷下一個起始位置，如：

初始時，left=1, right=2，若數(shù)字[right] > 數(shù)字[right-1]，則right右移，擴(kuò)展窗口。

否則，記錄當(dāng)前窗口的遞增子串，并重置left，right變量。

此方法的核心思想，就是一邊遍歷時一邊判斷，避免無效截取，所以，方法也更做優(yōu)。

除了對數(shù)字子串的判斷外， 我們同樣遇到對字符串的判斷，如：

例： 查找所有不重復(fù)的子串（第15屆藍(lán)橋杯Scratch選拔賽第2次STEMA測評5第題：不重復(fù)的子串）

題目是：字符串為abbcd，所有子串有：a、ab、abb、abbc、abbcd、b、bb、bbc、bbcd、 bc、 bcd、c、cd、d

其中，子母不重復(fù)的子串有：a、ab、b、bc、bcd、c、cd、d

過程類似，找出不重復(fù)的子串包括二個過程：

通過枚舉找出所有的子串；

除掉所有有重復(fù)字母的子串。

同樣是一個遍歷 所有可能的子串的問題。其本思路就是： 遍歷從當(dāng)前起始位置開始的所有子串：使用一個內(nèi)層循環(huán)，從每個起始位置開始，作為子串的開始位置，遍歷每個字符直到字符串的結(jié)尾

同學(xué)們可以通過多寫程序，來驗證代碼，以掌握此類問題的一般解法。

遞歸

去年的遞歸是道畫圖題：

即： 編寫出可以畫出各級別的科赫雪花的代碼。 是道難度不小的應(yīng)用遞歸思路的編程題。

7月5日，第1次復(fù)賽，同樣出一道遞歸的繪圖題，如圖：

即：遞歸實現(xiàn)謝爾賓斯基地毯。

遞歸思路，通常包含兩個部分：終止條件和遞歸調(diào)用。終止條件，即存在不再調(diào)用自身的條件，用于防止無限遞歸；遞歸調(diào)用則是函數(shù)調(diào)用自身，以逐步解決問題。

那么，除了上面的題型外，可以關(guān)注遞歸的一些其他應(yīng)用：

1、 用遞歸的思路來解決階乘問題，可以進(jìn)行如下定義：

n!=(n-1)！× n

示例代碼如下：

2、 斐波那契數(shù)列的遞歸生成

斐波那契數(shù)列的前兩項是1，從第三項開始，每項的值都是前兩項之和，如：1，1，2，3，5，8，13，21，34，55，89，144......

其遞歸表達(dá)式為：

F(n) = F(n-1) + F(n-2) (n≥3)

其中初始值 F(1)=1，F(xiàn)(2)=1

原文可看：

3、遞歸畫樹

如上圖，繪制一棵圣誕樹：

我們將圣誕樹簡化一下（如下圖），即：每一個棵樹的樹枝其實也是一棵圣誕樹，然后，樹枝的樹枝仍是一棵圣誕樹……

同樣的思路， 還有二叉樹， 二叉樹是只有二個樹枝的樹，同時，每個樹枝又是一顆二叉樹。

注意，樹型遞歸是個很好題材（考試）！

排序。

對于學(xué)習(xí)計算機(jī)編程的同學(xué)來說，排序是最基本的入門算法，也是?？嫉念}型。個人認(rèn)為，小高組的同學(xué)掌握二種排序算法還是必要的。

建議熟練掌握選擇排序與冒泡排序兩個排序算法。選擇排序從前往后依次有序，冒泡排序從后往前依次有序。

選擇排序的核心思想是從未排序序列中找出最?。ɑ蜃畲螅┰?，存放到排序序列的起始位置，然后再從剩余未排序元素中繼續(xù)尋找最?。ɑ蜃畲螅┰?，然后放到已排序序列的末尾。重復(fù)此過程，直到所有元素均排序完畢。

冒泡排序通過重復(fù)地遍歷要排序的列表，比較相鄰的兩個元素，如果順序錯誤就交換它們的位置。每一輪遍歷會將當(dāng)前未排序部分的最大元素“冒泡”到正確的位置。

以下是選擇排序代碼：

畫筆

1、【Scratch藝術(shù)畫筆】畫正多邊形

2、【Scratch藝術(shù)畫筆】畫圓、圓弧和扇形

3、【Scratch藝術(shù)畫筆】畫五角星

4、【Scratch藝術(shù)畫筆】正多邊形的旋轉(zhuǎn)

5、【Scratch藝術(shù)畫筆】畫實體正多邊形

6、【Scratch藝術(shù)畫筆】轉(zhuǎn)動的圖形一（大風(fēng)車）

7、【Scratch藝術(shù)畫筆】轉(zhuǎn)動的圖形二（太極陰陽圖）

8、【Scratch藝術(shù)畫筆】轉(zhuǎn)動的圖形三（內(nèi)旋多邊形）

9、【Scratch藝術(shù)畫筆】轉(zhuǎn)動的圖形四（外旋多邊形）

10、【Scratch藝術(shù)畫筆】轉(zhuǎn)動的圖形五（整體旋轉(zhuǎn)）