挖掘題目內(nèi)涵，注重算法教學(xué)中的發(fā)散性思維培養(yǎng)

說在前面

本文根據(jù)筆者課堂教學(xué)實錄整理加工而成。原本只打算花幾分鐘簡單點評一下作業(yè)，由于不小心多問了幾個問題，引發(fā)了學(xué)生興趣，結(jié)果一發(fā)不可收拾，在一個題目上“耗”了整整一節(jié)課的時間，學(xué)生還意猶未盡，表示課后還要花更多的時間來研究這個問題。

可見給學(xué)生足夠思考時間、鼓勵學(xué)生發(fā)散思維時，學(xué)生會發(fā)現(xiàn)很多教師“看不到”的東西；若教師不囿于課前計劃、保持課堂的開放性、因勢利導(dǎo)，往往可能形成“無心插柳柳成蔭”的效果。

本節(jié)課的前置內(nèi)容是“枚舉算法”，筆者原計劃上新課“算法程序?qū)崿F(xiàn)的綜合應(yīng)用”。因為上節(jié)課的課后練習(xí)中有一道題目錯誤率較高，所以筆者打算先花幾分鐘講一下作業(yè)。

題目如下：

有如下Python程序段:

s = 0for i in range(1, 20):    j = 2    flag = True    while j <= 4 and flag:        if i % j == 0:            flag = False        j += 1    if flag:        s = s + iprint(s)

執(zhí)行程序后，變量s的值是           

此題考查枚舉算法思想和二重循環(huán)的應(yīng)用，題目涉及變量較多，分析起來頭緒紛雜，容易出錯。

關(guān)于二重循環(huán)的處理辦法，我要求學(xué)生主要注意兩點：一是設(shè)計表格，跟蹤變量變化情況；二是觀察變量變化規(guī)律，總結(jié)程序功能，預(yù)測程序運行結(jié)果。

我先讓學(xué)生使用表格法跟蹤程序運行，看看能否找到規(guī)律；同時把代碼發(fā)給學(xué)生，允許他們通過上機調(diào)試程序來尋找規(guī)律。

我們可以設(shè)計如下表格，跟蹤變量值的變化情況：

簡單跟蹤幾輪循環(huán)，可以發(fā)現(xiàn)內(nèi)層循環(huán)變量j的取值范圍是[2,4]，變量flag用來判斷i是否能被j整除，若j不是i的因數(shù)，則將i累加到s中。

由此可知程序的功能是計算s = 1 + 5 + 7 + 11 + 13 + 17 + 19，故答案為73。

也有學(xué)生在代碼s = s + i之前加了一條輸出語句print(i)，看看都有哪些i值被篩選出來了，由此也觀察出了i值的規(guī)律：都是不能被2和3整除的整數(shù)。

找到答案以后，我做了簡單總結(jié)：程序的功能是篩選出[1,19]范圍內(nèi)不能被2和3整除的整數(shù)，并累加到變量s中，這是枚舉算法的典型應(yīng)用。

然后，我又問了一連串問題：為什么這么簡單的結(jié)論我們很多同學(xué)一開始都沒有看出來？題目的難點究竟在哪里？你能否對程序進行改進，寫出簡明易懂的代碼？

同學(xué)們紛紛表示主要是對二重循環(huán)不熟悉，思路不夠清晰；一看到大段代碼和多個變量就慌了神，沒有耐心去跟蹤程序、記錄變量的變化情況。

明確了程序功能以后，編寫代碼的難度就大大降低了。幾位平時表現(xiàn)比較出色的同學(xué)很快給出了他們的代碼。其中一個如下：

s = 0for i in range(1, 20):    if i % 2 == 0 or i % 3 == 0 or i % 4 == 0:        continue    s += iprint(s)

程序運行結(jié)果完全正確，同學(xué)們都表示贊賞。

然后有人提出條件表達式可以寫得更簡單些，因為i % 4 == 0是多余的。也有人表示可以去除continue語句，只要在條件表達式前面加個not就行了，代碼如下：

s = 0for i in range(1, 20):    if not (i % 2 == 0 or i % 3 == 0):        s += iprint(s)

還有人表示在條件表達式前面加not不太習(xí)慣，可以把not (i % 2 == 0 or i % 3 == 0)改成i % 2 != 0 and i % 3 != 0。贏得了一片贊賞聲。

討論到這里就告一段落了，通過此題我們復(fù)習(xí)了枚舉算法的思考方法和程序框架，并對條件表達式的寫法有了進一步認識。

在成功引導(dǎo)學(xué)生展開討論和改進代碼以后，我不禁有些沾沾自喜，心想這節(jié)課開局不錯，可以順利地進入下一步了。

突然有一個聲音響起：“我覺得原題的代碼也很好。使用二重循環(huán)是為了方便表示更多的可能性，當(dāng)j的取值范圍比較大時，使用條件表達式反而更麻煩。例如當(dāng)j的取值范圍是[1,10]時，條件表達式要寫做i % 2 != 0 and i % 3 != 0 and i % 5 != 0 and i % 7 != 0。這樣還不如使用二重循環(huán)來得方便?！?/span>

大家都愣了一下，然后群起鼓掌！

然后又有一個聲音響起：“使用二重循環(huán)是很好，但是j的值不應(yīng)該遞增，這樣會出現(xiàn)重復(fù)判斷，例如若i不能被2整除，則肯定也不能被2的倍數(shù)整除，就沒必要再重復(fù)判斷了。我發(fā)現(xiàn)j只需要取質(zhì)數(shù)，我們把這些質(zhì)數(shù)存儲到列表中，再遍歷列表就行了”。

例如我們可以擴大j的取值范圍，編寫這樣一段代碼：

s = 0a = [2, 3, 5, 7]for i in range(1, 20):    flag = True    for j in a:        if i % j == 0:            flag = False            break    if flag:        s += iprint(s)

同學(xué)們紛紛表示這段代碼不錯，但涉及變量有點多，理解起來還是有一定困難。

然后有人說他可以把變量flag去掉。因為flag的作用是記錄內(nèi)層循環(huán)中是否執(zhí)行了break語句，這個功能可以由Python自身的for…else語法來實現(xiàn)。代碼如下：

s = 0a = [2, 3, 5, 7]for i in range(1, 20):    for j in a:        if i % j == 0:            break    else:        s += iprint(s)

代碼少了2行，看上去果然簡明了一些。大家都非常滿意，討論的聲音漸漸平息下來。

同學(xué)們滿意了，我卻高興不起來，因為時間已經(jīng)過去快20分鐘了，這節(jié)課的教學(xué)任務(wù)肯定完不成了，總不能新課上到一半就結(jié)束吧。我該怎樣混過剩下的20分鐘呢？

我隨意翻了翻作業(yè)本，看看能不能再拿幾道題目出來講一講。

看到題目旁邊紅筆寫著的s = 1 + 5 + 7 + 11 + 13 + 17 + 19，我突然靈光閃現(xiàn)——質(zhì)數(shù)！被篩選出來的i除了1以外全部都是質(zhì)數(shù)。又想起剛才學(xué)生說的可以把質(zhì)數(shù)存儲到列表中——那我們就可以改造這段代碼，用它來生成質(zhì)數(shù)表。

我心中頓時有了主張。

我先問了同學(xué)們一個問題：在剛才的程序中，存儲在列表a中的元素有什么特征？

學(xué)生回答：它們都是質(zhì)數(shù)。

教師繼續(xù)發(fā)問：這些質(zhì)數(shù)是人工設(shè)置的還是程序自動生成的？

學(xué)生回答：人工設(shè)置的。

這時候我才拋出真正的問題：能否讓程序自動生成一個質(zhì)數(shù)列表？提示，觀察被篩選出來的i值的特征。

有個學(xué)生很聰明，他很快領(lǐng)會了我的意圖：難道是利用已有的質(zhì)數(shù)來篩選新的質(zhì)數(shù)？

沒錯，每個合數(shù)都可以寫成幾個質(zhì)數(shù)相乘的形式，其中每個質(zhì)數(shù)都是這個合數(shù)的因數(shù)，把一個合數(shù)用質(zhì)因數(shù)相乘的形式表示出來，叫做分解質(zhì)因數(shù)。例如6=2*3，60=2*2*3*5。根據(jù)分解質(zhì)因數(shù)的原理，我們可以利用小質(zhì)數(shù)篩選出更大的質(zhì)數(shù)：先初始化質(zhì)數(shù)表中只有一個質(zhì)數(shù)2，然后把篩選出來的質(zhì)數(shù)添加到質(zhì)數(shù)表中；再利用新的質(zhì)數(shù)表篩選出更大的質(zhì)數(shù)，如此循環(huán)往復(fù)，就可以獲得所需的質(zhì)數(shù)表了。

有了算法思想的指導(dǎo)，我讓學(xué)生分組討論，改造原有程序代碼，實現(xiàn)生成[2,50]范圍內(nèi)質(zhì)數(shù)列表的功能。

程序有一定難度，幾乎所有的學(xué)生都遇到了困難。在我的點撥之下，總算有一個小組完成了任務(wù)。代碼如下：

a = [2]for i in range(3, 51):    for j in a:        if i % j == 0:            break    else:        a.append(i)print(a)

我請學(xué)生上臺演示程序并介紹了算法原理，同學(xué)們給予了熱烈的掌聲。

我大聲地表揚了該學(xué)生及其學(xué)習(xí)小組，對他們的程序給予了高度評價，認為他們發(fā)現(xiàn)了一種構(gòu)造質(zhì)數(shù)表的新方法——后來才發(fā)現(xiàn)其實這就是經(jīng)典的歐拉篩法。

我要求所有學(xué)生都做好筆記，并為代碼添加注釋。由于有了之前的鋪墊，大多數(shù)學(xué)生都理解了算法原理和每一行代碼的含義，甚至有學(xué)生發(fā)現(xiàn)可以初始化a為空列表，只要修改i的取值范圍為[2,50]，程序也能得到正確的結(jié)果。

學(xué)生們都很興奮，意猶未盡。我一看距離下課還有不到10分鐘，心想再繼續(xù)講解新的內(nèi)容意思不大，還不如在質(zhì)數(shù)問題上深挖一下。我告訴學(xué)生歷史上最著名的構(gòu)造質(zhì)數(shù)表的方法是篩法求質(zhì)數(shù)，并開放外網(wǎng)讓學(xué)生上網(wǎng)查詢關(guān)于篩法求質(zhì)數(shù)的資料，要求他們理解算法思想后編寫代碼實現(xiàn)程序功能。

為了規(guī)范學(xué)生的編程行為，并體現(xiàn)模塊化編程思想，我要求學(xué)生把程序功能抽象成一個自定義函數(shù)，并提供了函數(shù)頭注釋如下：

函數(shù)功能：質(zhì)數(shù)又稱素數(shù)，指在大于1的自然數(shù)中，除了1和此整數(shù)自身外，沒法被其他自然數(shù)整除的數(shù)。根據(jù)輸入的正整數(shù)n，返回最大值不大于n的質(zhì)數(shù)表。

函數(shù)名：prime_list(n: int) -> list

參數(shù)表：n -- 一個規(guī)定了質(zhì)數(shù)范圍的正整數(shù)。

返回值：一個列表，存儲了所有不大于n的質(zhì)數(shù)。

示例：輸入n=10，返回[2,3,5,7]。

雖然學(xué)生對質(zhì)數(shù)有一定了解，也做過相關(guān)題目，但由于本題題目過于開放，學(xué)生不太適應(yīng)。再加上時間不夠充裕，大多數(shù)學(xué)生只來得及閱讀相關(guān)資料和理解算法原理，沒時間編寫代碼上機調(diào)試程序了，只好把問題帶回去，留待課后思考。

當(dāng)然，也有個別學(xué)生水平比較高，找到了合適的資料，快速理解算法并編寫程序進行了調(diào)試。該學(xué)生使用的是經(jīng)典的埃拉托色尼篩選法，簡稱埃氏篩法。它利用素數(shù)p只有1和p這兩個約數(shù)，并且一個數(shù)的約數(shù)一定不大于自身的特征，對素數(shù)進行篩選。

篩選過程：把正整數(shù)從小到大順序排列，1不是素數(shù)，首先把它篩掉；剩下的數(shù)中選擇最小的數(shù)2是素數(shù)，然后去掉它的倍數(shù)；剩下的數(shù)中選擇最小的數(shù)3是素數(shù)，然后去掉它的倍數(shù)；剩下的數(shù)中選擇最小的數(shù)5是素數(shù)，然后去掉它的倍數(shù)；依次類推，直到序列為空時結(jié)束。

參考代碼如下：

def prime_list(n: int) -> list:    lib = [True] * (n+1)    a = []    for i in range(2, n+1):        if lib[i]:#若i未被篩出，說明它是素數(shù)，將其添加到列表a中，并篩出i的倍數(shù)            a.append(i)             for j in range(i**2, n+1, i):#篩出i的倍數(shù)                lib[j] = False    return a

埃氏篩法雖然簡明易懂，效率也很高，但是它有一個缺陷：對于一個合數(shù)，有可能被篩多次。例如 30=2*15=3*10=5*6……那么如何確保每個合數(shù)只被篩選一次呢？

我們只要用它的最小質(zhì)因子來篩選即可，這便是歐拉篩法。歐拉篩法在埃氏篩法的基礎(chǔ)上，讓每個合數(shù)只被它的最小質(zhì)因子篩選一次，以達到不重復(fù)的目的。參考代碼如下：

def prime_list2(n: int) -> list:    lib = [True] * (n+1)    a = []    for i in range(2, n+1):        if lib[i]:#若i未被篩出，說明它是素數(shù)            a.append(i)        for j in a: #將當(dāng)前素數(shù)表中素數(shù)j的i倍篩出。            if i*j <= n:                lib[i*j] = False                if i % j == 0:#為保證每個合數(shù)只被它的最小質(zhì)因子篩選一次，當(dāng)i是j的倍數(shù)時跳出循環(huán)                    break            else: #i*j大于n則不再處理                break    return a

仔細閱讀歐拉篩法的代碼及注釋，我們發(fā)現(xiàn)課堂上學(xué)生給出的代碼其實就是歐拉篩法的另一種實現(xiàn)方式，它不需要設(shè)置列表lib，直接根據(jù)列表a中的元素篩選出滿足條件的i，大大節(jié)省了空間，代碼也更為簡明。參考代碼如下：

def prime_list3(n: int) -> list:    a = []    for i in range(2, n+1):        for j in a: #遍歷已有素數(shù)表，利用最小質(zhì)因子排除合數(shù)            if i % j == 0: #若i為合數(shù)，跳出循環(huán)                break        else: #未執(zhí)行break語句，說明i是素數(shù)            a.append(i)    return a

二重循環(huán)程序運行過程較為復(fù)雜，跟蹤代碼難度高，是編程初學(xué)者的一個攔路虎。當(dāng)涉及變量較多時，學(xué)生容易產(chǎn)生畏難情緒，往往輕易放棄思考。

筆者在做題時會習(xí)慣性地思考如何改進代碼，使其更簡明易懂，以降低思維難度和節(jié)省閱讀時間。在備課時，筆者考慮了簡化代碼的幾種方法，也取得了預(yù)期的效果。但筆者急于消除原題代碼中的內(nèi)層循環(huán)和多余變量，忽略了二重循環(huán)的優(yōu)點，沒有做進一步挖掘。

幸好有學(xué)生發(fā)現(xiàn)了這個問題，又幸好筆者的課堂風(fēng)格比較開放和民主，沒有強行把教學(xué)進程拉到既定軌道，允許學(xué)生做了進一步討論，發(fā)現(xiàn)了一些有趣的東西。更幸運的是筆者對質(zhì)數(shù)相關(guān)算法比較熟悉，竟然在電光火石之間看到了該段代碼蘊含的重要功能——生成質(zhì)數(shù)表。

能夠引導(dǎo)學(xué)生發(fā)現(xiàn)這段美妙的代碼，有很大的運氣成分，同時與教師的經(jīng)驗和教學(xué)風(fēng)格分不開。我希望自己能夠繼續(xù)保持這種靈活開放的教學(xué)風(fēng)格，在做好充分準(zhǔn)備的前提下，給學(xué)生足夠的思考時間、鼓勵學(xué)生發(fā)散思維、因勢利導(dǎo)，爭取在課堂中能夠遇到更多“精彩一刻”，擷取更多“意外收獲”。

需要本文word文檔、源代碼和課后練習(xí)答案的，可以加入“Python算法之旅”知識星球參與討論和下載文件，“Python算法之旅”知識星球匯集了數(shù)量眾多的同好，更多有趣的話題在這里討論，更多有用的資料在這里分享。

我們專注Python算法，感興趣就一起來！

相關(guān)優(yōu)秀文章：

閱讀代碼和寫更好的代碼

最有效的學(xué)習(xí)方式

Python算法之旅文章分類