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

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

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

● 存在的問題和困難

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

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

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

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

● 遵循原則

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

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

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

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

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

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

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

● 實(shí)施策略

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

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

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

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

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

● 案例解析

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

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

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

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

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

圖1

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

2.簡(jiǎn)單遞歸實(shí)現(xiàn)算法

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

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

圖2

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

圖3

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

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

圖4

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

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

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

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

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

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

圖5

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

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

圖6

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

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

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

圖7

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

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