Python編程與算法教學(xué)的策略及指導(dǎo)原則

于曉雅 北京教育學(xué)院人工智能和創(chuàng)客教育研究中心

樊磊 首都師范大學(xué)教育學(xué)院

自信息技術(shù)新課標(biāo)以Python語言作為核心編程語言推薦以來，Python編程與算法教學(xué)成為落實新課標(biāo)課程目標(biāo)的基礎(chǔ)。如何在中小學(xué)Python編程與算法教學(xué)中，落實課標(biāo)精神，圍繞“算法以及基于算法的問題求解”這一核心問題，依據(jù)基礎(chǔ)教育階段學(xué)生特點把握適當(dāng)深度和廣度，通過算法學(xué)習(xí)和實踐，為深入體會并應(yīng)用計算思維（信息技術(shù)的思想、方法和手段）解決問題提供堅實基礎(chǔ)，實現(xiàn)“運用計算思維解決問題”能力培養(yǎng)的課程目標(biāo)，是廣大信息技術(shù)學(xué)科教師共同關(guān)注的話題和主要研究點。

● 存在的問題和困難

作為普通高中信息技術(shù)新課標(biāo)的重要內(nèi)容，中小學(xué)Python編程與算法在教學(xué)中目前存在如下問題和困難：

第一，教學(xué)內(nèi)容選擇的困難。高校中計算機及其相關(guān)專業(yè)關(guān)于算法的教學(xué)已經(jīng)形成非常完備的體系，但由于中小學(xué)生與大學(xué)生在年齡和認(rèn)知上存在差異,學(xué)科基礎(chǔ)也不同，所以基礎(chǔ)教育階段的算法及問題求解教學(xué)，不能是高校教學(xué)內(nèi)容的簡單簡化，也不能只將其作為大學(xué)算法課程的前序準(zhǔn)備而不涉獵本質(zhì)問題。上述狀況使得中小學(xué)算法教學(xué)內(nèi)容在深度和廣度方面普遍呈“高不成、低不就”的窘態(tài)。

第二，教學(xué)實踐層次的困難。首先，作為計算機科學(xué)的重要分支，算法與數(shù)學(xué)、數(shù)據(jù)結(jié)構(gòu)、編程語言特性密切關(guān)聯(lián)，已經(jīng)成為一個的完備的知識體系，單純講算法本身很難實施。其次，Python語言封裝了很多基礎(chǔ)算法的實現(xiàn)，而且涉及交錯復(fù)雜的概念（如數(shù)據(jù)類型、抽象數(shù)據(jù)類型），究竟是講算法的底層方面還是講高階應(yīng)用難以取舍。再次，如何處理算法的直覺描述（非形式化描述）、流程圖、偽代碼（半形式化描述）和編程實現(xiàn)（形式化描述）之間的關(guān)系，也是教學(xué)實踐的難點。

第三，案例選擇的困難。中小學(xué)階段的算法教學(xué)是為編程教學(xué)服務(wù)的，所以必須服從編程教學(xué)的總目標(biāo)：運用計算思維解決問題。但限于中小學(xué)生的認(rèn)知水平和知識深度，教學(xué)案例的求解流程和問題深度很難把握，所以選擇適當(dāng)?shù)陌咐蔀閷嵤㏄ython編程與算法教學(xué)的關(guān)鍵。

● 遵循原則

第一，算法應(yīng)該源自學(xué)生熟悉的應(yīng)用情境。

第二，在算法的選擇上，要把握好高階算法和低階算法之間的平衡。

第三，算法的目標(biāo)、直觀思想以及逐步導(dǎo)致形式化描述的演化過程是高中（包括小學(xué)、初中）算法教學(xué)的重要部分，教學(xué)中應(yīng)避免直接提出一般化、形式化的算法描述。

第四，算法中所涉及的核心思想、形式化或半形式化表示、算法推導(dǎo)的數(shù)學(xué)及背景知識應(yīng)在學(xué)生的知識范圍內(nèi)，或略微超過學(xué)生的知識范圍。

第五，算法的編程實現(xiàn)上，原則上不涉及較復(fù)雜或較具技巧性編程，較復(fù)雜算法可不做實際的編程實現(xiàn)或只做Python-like偽代碼實現(xiàn)，但算法作為教學(xué)案例，必須先講清楚其背后的關(guān)鍵思想。

第六，高階算法所解決的問題應(yīng)具有典型性、時代性、選擇性、普適性和適用性，并且對學(xué)生的后續(xù)學(xué)習(xí)或其他學(xué)科的學(xué)習(xí)有啟示作用。

第七，在時間和條件都允許的情況下，應(yīng)對解決同一類問題的、基于不同策略所實現(xiàn)的算法做性能比對，并挑選出較優(yōu)算法。

● 實施策略

1.明晰Python編程知識進階，合理設(shè)計教學(xué)方法

在Python編程與算法教學(xué)中，要始終貫徹“需求導(dǎo)向、問題解決、做中學(xué)”的定位，明確學(xué)會使用函數(shù)比掌握編程技巧更重要。在設(shè)計編程案例時，要掌握輸入/輸出函數(shù)，能夠靈活運用非數(shù)值數(shù)據(jù)類型，包括字符串、列表和字典；要了解Python語言異常靈活的循環(huán)及控制結(jié)構(gòu)；鼓勵教師將Python當(dāng)作實現(xiàn)版的“偽代碼”來使用，即使確實需要用偽代碼，也建議使用Python-like風(fēng)格；如果要使用Python的高級特性，編程案例應(yīng)盡量依托Python語言特點，并以算法實現(xiàn)的需求適當(dāng)漸次地引入。但筆者建議，非必要盡量不使用Python的高級特性。

2.熟悉算法策略，找準(zhǔn)對應(yīng)求解問題

算法策略是指在算法設(shè)計中所使用的問題求解的策略，是計算思維最直接、最具體的體現(xiàn)形式。算法策略的視角比實現(xiàn)算法時的具體編程實現(xiàn)方法在站位上要更高。

在中小學(xué)編程教育中，在算法教學(xué)里，常見的算法策略和它們用于處理的任務(wù)主要有：迭代（也稱為循環(huán)）——用于處理重復(fù)性的任務(wù)；遞歸——用于完成迭代的一種高效方法；蠻力法——在沒有更好的辦法而且計算資源（時間和空間）允許的前提下，可以嘗試采用的求解問題的方法；回溯——用于測試不可行的選擇，目的在于盡可能排除這類選擇。

● 案例解析

算法以及基于算法的問題求解是計算機科學(xué)的最重要的組成部分，也是信息技術(shù)新課程最基本、最核心的內(nèi)容，算法教學(xué)中教學(xué)案例的選擇是最重要的關(guān)鍵點。下面，筆者以斐波那契數(shù)列的問題解決路徑為例，解析在上述原則和策略的指導(dǎo)下，如何實施Python編程和算法教學(xué)。

1.構(gòu)建問題場景

斐波那契數(shù)列從0和1開始，之后的斐波那契數(shù)列系數(shù)就由之前的兩數(shù)相加。高中數(shù)學(xué)必修五在講解數(shù)列前n項和的課后資料中提到了斐波那契數(shù)列，作為數(shù)學(xué)知識生活化、發(fā)展學(xué)生抽象思維能力的拓展。

斐波那契數(shù)列（Fibonacci sequence）因為相鄰兩項的比無限趨近于黃金比等性質(zhì)，又稱黃金分割數(shù)列。它是意大利數(shù)學(xué)家萊昂納多·斐波那契（Leonardoda Fibonacci）以兔子繁殖為例子而引入，故又稱為“兔子數(shù)列”。假設(shè)一對剛出生的小兔子一個月后能長成大兔子，再過一個月便能生下一對小兔子，此后每個月生一對小兔子。如果不發(fā)生死亡，一年內(nèi)逐月的小兔子對數(shù)是一組非常特殊的數(shù)字：1，1，2，3，5，8，13，21，34，55，89，144，……不難發(fā)現(xiàn)，從第三個數(shù)起，每個數(shù)都是前兩個數(shù)之和，這個數(shù)列稱為斐波那契數(shù)列。

在現(xiàn)代物理、準(zhǔn)晶體結(jié)構(gòu)、化學(xué)等領(lǐng)域，斐波那契數(shù)列都有直接的應(yīng)用，斐波那契數(shù)列的通項公式表示如圖1所示的公式（1）。

圖1

在算法教學(xué)中，斐波那契數(shù)列是最簡單的遞歸定義函數(shù)，因此非常適合用來說明實現(xiàn)基本遞歸算法的方法。

2.簡單遞歸實現(xiàn)算法

斐波那契數(shù)列的Python實現(xiàn)所需基本知識包括：使用if語句實現(xiàn)簡單迭代/循環(huán)、自定義函數(shù)、函數(shù)的遞歸定義。

斐波那契數(shù)列本身就是用遞歸形式定義的，Python是函數(shù)式編程語言，支持函數(shù)的遞歸定義，即函數(shù)體的內(nèi)部包含對函數(shù)本身的調(diào)用。因此，公式（1）可以轉(zhuǎn)換為一個合法定義的Python函數(shù)，并嘗試讓學(xué)生輸出一些可很快通過人工驗證的值（不要太大）（如圖2）。

圖2

可以注意到，在計算最后一個值時是需要一點時間的。在上述的遞歸調(diào)用中，很多中間值要重復(fù)計算。如圖3所示，在計算fib_1（4）時，fib_1（2）就重復(fù)計算了2次。顯然，n的值越大，在計算fib_1（n）的過程中，需要重復(fù)計算fib_1（k）（k＜n）的次數(shù)就越多。

圖3

3.動態(tài)規(guī)劃優(yōu)化遞歸算法

為了優(yōu)化斐波那契數(shù)列的遞歸實現(xiàn)，一個最簡單的方法就是在每次計算中，將前面已經(jīng)計算過的值“記憶”下來，不再重復(fù)計算。這種在計算過程中使用記憶的機制可以有效避免重復(fù)及浪費資源，是所謂動態(tài)規(guī)劃方法的一個最簡單的例子，動態(tài)規(guī)劃就是指資源的動態(tài)再分配。動態(tài)規(guī)劃實現(xiàn)需要涉及如下Python知識：Python字典、Python的Dict內(nèi)建對象（一種特殊的Python字典）、對迭代器使用if語句。圖4所示代碼是一個帶有記憶的版本。

圖4

作為對比，計算fib_2（20）會產(chǎn)生fib_2（）的39次自調(diào)用；而若使用fib_1（），則計算fib_1（20）會產(chǎn)生21891次調(diào)用。

在Python中，任意對象只要定義了某種＿next＿（）方法，就是一個迭代器。因此，Python中的容器類數(shù)據(jù)類型，如列表、元組、字典、集合、字符串等，都可以用于創(chuàng)建迭代器。有了迭代器的概念，迭代的概念就比較容易理解了：迭代就是從迭代器中依次抽取元素的過程。

4.裝飾器優(yōu)化遞歸算法

Python有一個內(nèi)建的“裝飾器”（decorator），可用于自動記憶任何函數(shù)。通過使用這個裝飾器，計算斐波那契數(shù)列的函數(shù)可以更加簡化。

以下實現(xiàn)使用Python的高級特性——Python裝飾器語句。簡單地講，裝飾器就是在不改變原來函數(shù)代碼的情況下，給其增加一些附加功能，如上面記憶函數(shù)中間值的功能。

下頁圖5代碼實現(xiàn)的函數(shù)fib_3（）與fib_1（）幾乎完全相同，但使用了裝飾器@functools.1ru_cache（），其中maxsize屬性用來指示在函數(shù)的最近調(diào)用中應(yīng)該緩沖多少次，設(shè)置maxsize=None表示對次數(shù)不做限制。

圖5

5.使用元組拆包優(yōu)化遞歸算法

元組拆包就是將元組中的元素分別賦給變量。利用Python的元組拆包技巧可給出斐波那契函數(shù)的一個性能更高的實現(xiàn)（如圖6）。

圖6

在本例中，語句“l(fā)ast，next=next，last+next”實現(xiàn)將last的值更新為next的值，而將next的值更新為“l(fā)ast+next”的值，就是一個元組拆包。使用拆包技巧，計算fib_4（）只需循環(huán)n-1次！

6.斐波那契數(shù)列生成器-循環(huán)結(jié)構(gòu)

到目前為止，所寫的函數(shù)只能產(chǎn)生特定位置上的斐波那契數(shù)的值，如果要一次性將到某個值為止的整個斐波那契數(shù)列都輸出，可以使用一個簡單循環(huán)（如圖7）。

圖7

7.尋找更多優(yōu)化策略

教師可以引導(dǎo)學(xué)生繼續(xù)進行拓展練習(xí)，如探索斐波那契數(shù)列利用矩陣非遞歸化優(yōu)化,也可以探索斐波那契數(shù)列與黃金分割的關(guān)系，或者使用動態(tài)規(guī)劃優(yōu)化函數(shù)fib_up_to（）等，提升學(xué)生學(xué)習(xí)興趣，培養(yǎng)精益求精探索的創(chuàng)新精神。