陣型繪畫或克隆問題

陣型模式的繪畫或克隆題，也是重大考試中經常出現的主題，如下圖：

都是近年來出現在藍橋杯或等考題中的題型。

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

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

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

2、找出圖形的規律（包括圖形的形狀、行縮進、行間距、列間距等變量）。

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

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

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

能過雙重循環來實現整個過程，外層循環控制行數（Y軸方向），內層循環控制列數（X軸方向，每行的元素個數）。

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

這類題本身難度不大，往往結合其他問題來構成一個整體，但因為涉及到到的變量的應用、雙重循環等，所以，也是考試中經常出現的題型。如：

第15屆藍橋青少省賽Scratch初級組第3題：畫西瓜

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

第14屆藍橋杯Scratch圖形化編程國賽中級組第6題：太空大戰

子串匹配問題

例（第15屆藍橋青少省賽Scratch中級組第6題：截取遞增數）：

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

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

相似的問題，還包括：

截取遞減數： 從左到右嚴格遞減

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

波峰數：142（4是峰），253（5是峰）

波谷數：354（5是谷），131（3是谷）

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

奇偶交替數等。

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

通常，這類題的解法是：

1、枚舉法（窮舉法）

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

a. 遍歷所有可能的連續子串

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

示例：數字115367482

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

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

...（直到長度為9的整個數）。

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

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

在編程時，我們可以設置內外兩重循環，如：

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

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

2、 滑動窗口法

如圖：

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

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

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

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

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

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

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

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

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

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

除掉所有有重復字母的子串。

同樣是一個遍歷 所有可能的子串的問題。其本思路就是： 遍歷從當前起始位置開始的所有子串：使用一個內層循環，從每個起始位置開始，作為子串的開始位置，遍歷每個字符直到字符串的結尾

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

遞歸

去年的遞歸是道畫圖題：

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

即：遞歸實現謝爾賓斯基地毯。

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

那么，除了上面的題型外，可以關注遞歸的一些其他應用：

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

n!=(n-1)！× n

示例代碼如下：

2、 斐波那契數列的遞歸生成

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

其遞歸表達式為：

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

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

原文可看：

3、遞歸畫樹

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

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

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

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

排序。

對于學習計算機編程的同學來說，排序是最基本的入門算法，也是常考的題型。個人認為，小高組的同學掌握二種排序算法還是必要的。

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

選擇排序的核心思想是從未排序序列中找出最小（或最大）元素，存放到排序序列的起始位置，然后再從剩余未排序元素中繼續尋找最小（或最大）元素，然后放到已排序序列的末尾。重復此過程，直到所有元素均排序完畢。

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

以下是選擇排序代碼：

畫筆

1、【Scratch藝術畫筆】畫正多邊形

2、【Scratch藝術畫筆】畫圓、圓弧和扇形

3、【Scratch藝術畫筆】畫五角星

4、【Scratch藝術畫筆】正多邊形的旋轉

5、【Scratch藝術畫筆】畫實體正多邊形

6、【Scratch藝術畫筆】轉動的圖形一（大風車）

7、【Scratch藝術畫筆】轉動的圖形二（太極陰陽圖）

8、【Scratch藝術畫筆】轉動的圖形三（內旋多邊形）

9、【Scratch藝術畫筆】轉動的圖形四（外旋多邊形）

10、【Scratch藝術畫筆】轉動的圖形五（整體旋轉）