《枚舉法與算法的優(yōu)化》教學(xué)設(shè)計

宋巍巍 任靜 曹恒來

● 學(xué)習(xí)內(nèi)容分析

作為一種常用算法，枚舉法在生活中比較常見，如在一串鑰匙中找到正確的一把開門，最直接的辦法就是一把一把地去試，直到試出正確的一把。在計算機科學(xué)中，使用枚舉法解決問題則是利用計算機運算速度快的特點，一一列舉問題的所有可能答案，逐個驗證，把符合條件的答案保留下來，它是對現(xiàn)實生活中解決問題方法的一種“直譯”，因此比較直觀、易于理解。但是枚舉法需要對所有可能的答案一一列舉，如果枚舉的范圍很大，運算量將會很大，所耗的時間就比較多，那么，如何改進(jìn)算法，提高解決問題的效率就成了本節(jié)課的難點。

2018版的蘇科版八年級信息技術(shù)教材，將《算法實例》移至了《程序設(shè)計語言》之前，僅通過流程圖來描述和實現(xiàn)算法。在實際的教學(xué)過程中，筆者仍然把這部分內(nèi)容移至《程序中的循環(huán)》之后，讓學(xué)生用Visual Basic語言來描述算法，經(jīng)歷用計算機編程解決問題的過程，以幫助他們較為深刻地體驗和理解算法。

● 學(xué)習(xí)者分析

本課的學(xué)習(xí)對象是八年級下學(xué)期的學(xué)生，與七年級學(xué)生相比，他們的邏輯思維能力有了較大的提高，能運用數(shù)學(xué)公式構(gòu)建出解決問題的模型。在前面的學(xué)習(xí)中學(xué)生已經(jīng)掌握了算法的三種基本控制結(jié)構(gòu)，并能夠在Visual Basic環(huán)境中編寫程序解決生活中的一些簡單問題，但對算法和算法效率的認(rèn)識還不夠，很少能意識到算法對程序的重要性。在學(xué)習(xí)風(fēng)格上，八年級的學(xué)生喜歡動手實踐，迫切希望能在計算機中驗證解決問題的算法。

● 學(xué)習(xí)目標(biāo)

①了解枚舉法的概念，知道枚舉法的優(yōu)缺點，了解常用的枚舉法優(yōu)化策略，如縮小枚舉范圍、減少循環(huán)層數(shù)等。②通過解決多個個例問題歸納出枚舉法的一般模式。③感受問題解決方案的多樣性，在解決問題的過程中，能有意識地尋求優(yōu)化的解決方案，形成高效解決問題的習(xí)慣。

● 教學(xué)過程

1.創(chuàng)設(shè)情境，引入枚舉法

速算24點：從1～9中任選四個數(shù)字（數(shù)字可以有重復(fù)），快速計算這四個數(shù)字的和是否剛好是24。

（1）你能否一個不落地找出所有的數(shù)字組合？（將4個數(shù)字分別從1到9逐個嘗試）

（2）請打開“試算24點”程序找出幾組和為24的數(shù)字，感受一下手動逐個嘗試方式的速度。（比較慢）

（3）這種逐個嘗試工作可以由計算機自動完成，運行如上頁圖1所示程序，觀察運行結(jié)果。

小結(jié)：這種一一列舉問題的所有可能答案并進(jìn)行檢驗，找出符合要求的答案的方法就是枚舉法。

設(shè)計意圖：學(xué)生比較熟悉算24點游戲，為方便后面學(xué)生模仿程序，這里將游戲簡化為只做加法運算。通過口頭試算將學(xué)生引向枚舉法的思想，再通過程序手動試算24點，使學(xué)生對一一列舉有更直觀的體驗，在此基礎(chǔ)上再給出枚舉法的范例代碼并運行程序，幫助學(xué)生形成對枚舉法的初步認(rèn)識，并感受利用計算機高速運算解決問題的優(yōu)越性。

2.模仿嘗試，體驗枚舉法

活動1：模仿上例，分別完善程序，用枚舉法解決3個問題。

（1）所謂“水仙花數(shù)”是指一個三位數(shù)，其各位數(shù)字立方和等于該數(shù)本身，如153=13+53+33。求所有的水仙花數(shù)（如圖2）。

（2）一張單據(jù)上有一個五位數(shù)的編碼（如圖3），但一位粗心的會計將千位數(shù)和百位數(shù)弄模糊了，只記得這個五位數(shù)是57或67的倍數(shù)，求單據(jù)上所有可能的號碼（如圖4）。

（3）有些數(shù)可以被它自己各位數(shù)字之和整除，如18，1+8=9，18可以被9整除，找出具有此特性的所有三位數(shù)（如下頁圖5）。

設(shè)計意圖：模仿嘗試是學(xué)習(xí)編程解決問題的一種有效方法。活動1中讓學(xué)生模仿求24點的程序解決三個問題。為學(xué)生搭建三個半成品的程序支架，分別補充程序中的列舉部分和檢驗部分，使其將注意力集中到枚舉法的關(guān)鍵之處，一方面降低了學(xué)習(xí)的難度，另一方面通過對多個個例的模仿，為下面歸納出枚舉法的模式做準(zhǔn)備。

3.歸納提升，認(rèn)識枚舉法

觀察：以上在運用枚舉法解決問題時，它們都有一個共同的特點，程序主要由兩大部分組成的，分別是哪兩大部分？（列舉和檢驗）枚舉法解決問題的基本形式如下頁圖6所示。

小結(jié)：運用枚舉法解決問題的一般模式是列舉→檢驗。

設(shè)計意圖：通過上面的模仿學(xué)習(xí)，學(xué)生對枚舉法已經(jīng)有了初步的感性的認(rèn)識，這個環(huán)節(jié)通過觀察模仿的代碼，適時地歸納出枚舉法解決問題的一般模式，讓學(xué)生對枚舉法有更深刻的理解，也為后面將該方法遷移到解決同類問題做準(zhǔn)備。

4.問題解決，運用枚舉法

活動2：運用枚舉法解“百雞問題”。中國古代算書《張丘建算經(jīng)》中有著名的“百雞問題”：公雞每只5文錢，母雞每只3文錢，而3只小雞1文錢。用100文錢買100只雞，問：這100只雞中，公雞、母雞、小雞各有多少只？

（1）分析問題。

列舉：設(shè)公雞的只數(shù)為gj，列舉的范圍是1～100;設(shè)母雞的只數(shù)為mj，列舉的范圍是1～100;設(shè)小雞的只數(shù)為xj，列舉的范圍是1～100。

檢驗條件：公雞、母雞、小雞只數(shù)和是100且三種雞的價錢和是100。

（2）根據(jù)分析完善代碼，運行如圖7所示程序并檢查結(jié)果是否正確。

設(shè)計意圖：在上面幾個環(huán)節(jié)的學(xué)習(xí)中，學(xué)生已經(jīng)基本了解枚舉法的思想，建構(gòu)起了枚舉法的一般模式。方法的習(xí)得是為了解決生活中的實際問題，在分析“百雞問題”過程中，有意識地引導(dǎo)學(xué)生思考列舉的范圍和檢驗的方法，這樣能使學(xué)生在構(gòu)建代碼時自然想到可直接把范例代碼拿來修改和使用。

5.改進(jìn)算法，優(yōu)化枚舉法

活動3：優(yōu)化百雞問題算法。

（1）計算活動2中程序枚舉的次數(shù)（1000000），有辦法減少枚舉的次數(shù)，以提高程序的效率嗎？

小結(jié)：枚舉法的優(yōu)點是簡單直觀，缺點是效率不高。

（2）重新考察枚舉的范圍。

分析：總共有100文錢，公雞每只5文錢，則最多可買多少只？（20）其枚舉范圍可縮小到1～20;母雞每只3文錢，則最多可買多少只？（33）其枚舉范圍可縮小到1～33;要求買100只雞，而3只小雞1文錢，小雞最多可買多少只？（100）枚舉的范圍是1～100。

修改并運行程序，看能否得到和原始算法一樣的結(jié)果。試計算程序中枚舉的次數(shù)（66000），看看算法的效率有沒有提高。

小結(jié)：縮小枚舉范圍是優(yōu)化枚舉算法的一種策略。

（3）減少循環(huán)層數(shù)。

分析：因公雞、母雞、小雞的只數(shù)和是100，在枚舉公雞和母雞的只數(shù)后，小雞的只數(shù)xj可怎么表示？（100-gj-mj）不需要再對小雞枚舉，所以第三層循環(huán)可舍去。

再次修改并運行程序，看能否得到和原始算法一樣的結(jié)果。并再次計算枚舉的次數(shù)（660），看看算法的效率有沒有再次提高。

小結(jié)：減少循環(huán)層數(shù)能有效地減少枚舉的次數(shù)。

設(shè)計意圖：算法的優(yōu)化是本課的難點。通過計算原始算法的枚舉次數(shù)，學(xué)生會發(fā)現(xiàn)次數(shù)較多，自然會想到減少枚舉的次數(shù)來優(yōu)化算法。在分析的過程中搭建問題支架，重新考察三種雞的枚舉范圍和三種雞是否都要枚舉，分別得出縮小枚舉范圍和減少循環(huán)層數(shù)兩種常見的優(yōu)化策略。使學(xué)生經(jīng)歷再思考再實踐的過程，自覺形成通過技術(shù)方法高效解決問題的習(xí)慣。

6.思維導(dǎo)圖，知識梳理（如圖8）

設(shè)計意圖：用思維導(dǎo)圖梳理本課的知識點使學(xué)生在頭腦中形成清晰的知識結(jié)構(gòu)。

● 教學(xué)反思

本課采用案例模仿的教學(xué)方法，分別從感知、體驗、歸納和運用四個層次引領(lǐng)學(xué)生由淺入深地認(rèn)識了枚舉法。在“速算24點”小游戲中，通過口算、手算讓學(xué)生初步體驗了一一列舉并檢驗的思想。但對如何用程序設(shè)計語言實現(xiàn)枚舉法依然不知曉。為了讓學(xué)生對枚舉法有更加直觀的認(rèn)識，直接給出范例程序讓學(xué)生讀一讀，看一看運行結(jié)果，形成對枚舉法的初步印象?；顒?則是對范例模仿的過程，選取三個可用枚舉法解決的典型問題，給出半成品程序，采用局部探究的方法，把關(guān)注的焦點集中在范例的“列舉”和“檢驗”部分。在引導(dǎo)學(xué)生模仿范例解決三個個例問題之后，歸納出枚舉法解決問題的一般模式，從而實現(xiàn)從“個”到“類”的提升。

枚舉法需要對問題所有可能的解一一列舉，枚舉法的這一特點，導(dǎo)致其效率低下。因而，優(yōu)化和提升算法，提高程序的效率就成了本課的難點。常見的優(yōu)化策略有縮小枚舉范圍、減少循環(huán)層數(shù)、減少判斷每種情況的時間等。考慮到學(xué)生初學(xué)枚舉算法，這里選擇減少枚舉范圍和減少循環(huán)層數(shù)兩種比較好理解的優(yōu)化策略，通過計算和比較循環(huán)的次數(shù)，讓學(xué)生真切地感受算法優(yōu)化對程序效率的提升。

點 ?評

“算法與程序設(shè)計”是江蘇省初中信息技術(shù)課程中的獨立模塊，在教科書中雖然只有一章，但卻占了全書的三分之一的篇幅，因而它對培養(yǎng)學(xué)生邏輯思維和創(chuàng)新能力的作用是不言而喻的。恰恰算法與程序設(shè)計也是中學(xué)信息技術(shù)學(xué)習(xí)的難點。教師感到難教，學(xué)生感到難學(xué)，其中一個重要的原因，是還沒有找到行之有效的程序設(shè)計教學(xué)方法。傳統(tǒng)的程序設(shè)計教學(xué)以程序設(shè)計語言的語句為教學(xué)單元，重視其語法描述和語義解釋，而忽視了在具體語境中整體功用的表達(dá)，使得學(xué)生不能針對具體應(yīng)用而編寫出能夠有效解決問題的代碼。

仔細(xì)考察枚舉、遞歸等常見的算法不難發(fā)現(xiàn)，它們都有相對固定的解決問題的框架，這其實就是程序設(shè)計領(lǐng)域“模式”的思想，“模式”是在前人經(jīng)驗中總結(jié)出的解決問題的一般方案。本課就是基于模式的程序設(shè)計教學(xué)方法的有益嘗試，教者通過活動1中逐步遞進(jìn)的三個范例，幫助學(xué)生建構(gòu)起枚舉法解決問題的模式——列舉和檢驗。這樣學(xué)生就擁有了一組用枚舉法解決問題的代碼集合，當(dāng)再遇到同類問題時，學(xué)生只需參考這個問題的代碼模式，就能快速地構(gòu)建出解決這個問題的高質(zhì)量代碼。因而，在解決“百雞問題”這個問題時，學(xué)生自然會想到運用模式而不是再從語句和語法的層面去構(gòu)建算法。