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

宋巍巍 任靜 曹恒來(lái)

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

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

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

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

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

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

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

● 教學(xué)過(guò)程

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

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

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

（2）請(qǐng)打開(kāi)“試算24點(diǎn)”程序找出幾組和為24的數(shù)字，感受一下手動(dòng)逐個(gè)嘗試方式的速度。（比較慢）

（3）這種逐個(gè)嘗試工作可以由計(jì)算機(jī)自動(dòng)完成，運(yùn)行如上頁(yè)圖1所示程序，觀察運(yùn)行結(jié)果。

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

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

2.模仿嘗試，體驗(yàn)枚舉法

活動(dòng)1：模仿上例，分別完善程序，用枚舉法解決3個(gè)問(wèn)題。

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

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

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

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

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

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

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

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

4.問(wèn)題解決，運(yùn)用枚舉法

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

（1）分析問(wèn)題。

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

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

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

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

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

活動(dòng)3：優(yōu)化百雞問(wèn)題算法。

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

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

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

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

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

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

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

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

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

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

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

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

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

● 教學(xué)反思

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

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

點(diǎn) ?評(píng)

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

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