枚舉法的程序?qū)崿F(xiàn)及優(yōu)化

計(jì)新明

內(nèi)容分析

本部分內(nèi)容是教育科學(xué)出版社出版的必修1《數(shù)據(jù)與計(jì)算》第四單元第一節(jié)中的內(nèi)容，整本書(shū)的思路是初始數(shù)據(jù)與計(jì)算、編程計(jì)算、認(rèn)識(shí)數(shù)據(jù)、計(jì)算與問(wèn)題解決、數(shù)據(jù)分析與人工智能，第四章屬于比較重要的一章，主要介紹算法的概念和特征、算法的實(shí)現(xiàn)以及怎樣通過(guò)算法來(lái)解決現(xiàn)實(shí)中的問(wèn)題。枚舉法作為最重要的算法之一，在現(xiàn)實(shí)生活中也經(jīng)常用它來(lái)解決問(wèn)題，所以筆者把它挑出來(lái)用一節(jié)課的時(shí)間來(lái)講。

本節(jié)知識(shí)需要用兩課時(shí)，第一課時(shí)主要講解算法及其特征，第二課時(shí)主要講解枚舉法的程序?qū)崿F(xiàn)及其優(yōu)化，本節(jié)課是該節(jié)的第二課時(shí)。

學(xué)情分析

本節(jié)課的教學(xué)對(duì)象是高一的學(xué)生，他們?cè)谇懊娴膶W(xué)習(xí)中已經(jīng)學(xué)習(xí)過(guò)Python語(yǔ)言，對(duì)該語(yǔ)言的基本語(yǔ)法以及程序的基本結(jié)構(gòu)都有一定的了解，所以本節(jié)課中枚舉法的實(shí)現(xiàn)部分將使用Python語(yǔ)言。

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

了解枚舉法的概念;掌握枚舉法的特征;枚舉法的程序?qū)崿F(xiàn);對(duì)枚舉法進(jìn)行優(yōu)化。

核心素養(yǎng)

引導(dǎo)學(xué)生對(duì)提出的問(wèn)題進(jìn)行分析，探討問(wèn)題的解決方案，設(shè)計(jì)出解決問(wèn)題的算法并使用程序設(shè)計(jì)語(yǔ)言來(lái)實(shí)現(xiàn)此算法，最終解決問(wèn)題。解決之后繼續(xù)思考是否有更好的解決方案，能否對(duì)算法進(jìn)行優(yōu)化，從而更高效地解決問(wèn)題。通過(guò)本課學(xué)習(xí)，對(duì)學(xué)生的核心素養(yǎng)，特別是信息意識(shí)和計(jì)算思維的提高都有一定的促進(jìn)作用。

教學(xué)重難點(diǎn)

重點(diǎn)：枚舉法的特征、枚舉法的程序?qū)崿F(xiàn)。

難點(diǎn)：枚舉法的程序?qū)崿F(xiàn)、枚舉法的優(yōu)化。

教學(xué)媒體

多媒體計(jì)算機(jī)教室、廣播教學(xué)軟件、投影儀、教學(xué)幻燈片、Python軟件。

教學(xué)策略

本節(jié)課主要采用信息技術(shù)網(wǎng)絡(luò)教學(xué)平臺(tái)支持下的教學(xué)模式，即在教師教學(xué)引導(dǎo)下，學(xué)生通過(guò)任務(wù)驅(qū)動(dòng)實(shí)現(xiàn)自主學(xué)習(xí)的教學(xué)方法。教學(xué)流程為：提出問(wèn)題→學(xué)生探討解決問(wèn)題的方法→引出枚舉法的概念和特征→怎樣用Python來(lái)實(shí)現(xiàn)枚舉法→是否能讓我們的程序更加高效→枚舉法的優(yōu)化。

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

1.新課導(dǎo)入（3分鐘）

提出問(wèn)題：有一類(lèi)四位數(shù)，如3025，分為30和25兩個(gè)兩位數(shù)，這兩個(gè)數(shù)之和的平方正好等于該數(shù)本身，即（30+25）2=552=3025，求所有符合這一特征的四位數(shù)。請(qǐng)同學(xué)們嘗試解決這個(gè)問(wèn)題，并告訴老師你的思路是怎樣的。

設(shè)計(jì)意圖：提出實(shí)際問(wèn)題并讓學(xué)生自己去解決，引出今天要講的內(nèi)容;讓學(xué)生使用不同的方法，為后面的優(yōu)化埋下伏筆;最后讓學(xué)生自己動(dòng)手，讓學(xué)生理解得更深刻。

2.引出枚舉法的概念（3分鐘）

教師引出枚舉法的概念：一一列舉所有可能的答案，合適就保留，不合適就丟棄（也就是我們?nèi)粘Ｉ钪型ǔＫf(shuō)的一個(gè)一個(gè)去試）。

要求學(xué)生列舉出日常生活中可能用到或見(jiàn)到的枚舉法，如密碼鎖忘記密碼了;公安機(jī)關(guān)破案時(shí)先鎖定幾個(gè)嫌疑人，一個(gè)一個(gè)驗(yàn)證指紋，最后抓到犯罪嫌疑人。

設(shè)計(jì)意圖：不管學(xué)生有沒(méi)有解決這個(gè)問(wèn)題，他們的方法都是一個(gè)一個(gè)去試是否滿(mǎn)足條件，這樣就可以引出枚舉法的概念。

3.引導(dǎo)學(xué)生歸納總結(jié)出枚舉法的特征（2分鐘）

歸納總結(jié)：觀察以上例子，它們有什么共同點(diǎn)？明確：①有枚舉范圍;②有一定的驗(yàn)證條件。

設(shè)計(jì)意圖：在教師的引導(dǎo)下，學(xué)生根據(jù)前面的例子歸納出枚舉法的特征。

4.枚舉算法的程序?qū)崿F(xiàn)（4分鐘）

教師講解枚舉算法實(shí)現(xiàn)的三部曲：

（1）確定枚舉對(duì)象、枚舉范圍和判定條件。

這個(gè)數(shù)i的范圍為1000到9999，判定條件為前兩位數(shù)x和后兩位數(shù)y和的平方等于這個(gè)數(shù)。

（2）枚舉可能的解（使用循環(huán)結(jié)構(gòu)）。

for i in range（1000，9999）：

（3）驗(yàn)證是不是問(wèn)題的解（使用選擇結(jié)構(gòu)）。

If（x+y）2=i：

pirnt（i）

設(shè)計(jì)意圖：將枚舉法的實(shí)現(xiàn)分成三步來(lái)實(shí)現(xiàn)，讓學(xué)生更容易理解枚舉法，也更好去實(shí)現(xiàn)。

5.課堂活動(dòng)：實(shí)踐與嘗試（15分鐘）

實(shí)踐一：按照上面講解的枚舉法實(shí)現(xiàn)的三部曲，寫(xiě)出以下兩道習(xí)題的三部曲。

題1：班里要舉行班級(jí)聚會(huì)，要用600元班會(huì)費(fèi)為50名同學(xué)準(zhǔn)備50份禮品進(jìn)行抽獎(jiǎng)。選定了公仔（20元/個(gè)）、水杯（15元/個(gè)）和筆筒（10元/個(gè)）三類(lèi)商品。要求剛好用完600元買(mǎi)50件禮品（每種禮品至少一件），這三種禮品的數(shù)量可以如何搭配？（提示：假設(shè)這三種物品的數(shù)量分別為x、y、z，它們的范圍是多少？）

題2：這次面試的冠軍在A、B、C、D四位同學(xué)中產(chǎn)生。A說(shuō)：“不是我?！盉說(shuō)：“是C?！盋說(shuō)：“是D?！盌說(shuō)：“C說(shuō)的不對(duì)?！币阎娜酥杏幸蝗苏f(shuō)了假話(huà)。你能判斷出到底誰(shuí)是冠軍嗎？（提示：可以將A、B、C、D看成1、2、3、4）

實(shí)踐二：使用Python軟件寫(xiě)出上面題1的完整程序。

注意點(diǎn)：①提示學(xué)生寫(xiě)程序時(shí)注意縮進(jìn)，Python對(duì)這個(gè)要求比較嚴(yán)格;②三種循環(huán)是怎樣實(shí)現(xiàn)的（教師演示）;③學(xué)生完成之后教師使用廣播軟件轉(zhuǎn)播學(xué)生的完成情況，將錯(cuò)得比較多的地方挑出來(lái)講解，總結(jié)并評(píng)價(jià)一些學(xué)生的程序。完整程序如下：

for x in range（1，50）：

for y in range（1，50）：

for z in range（1，50）：

if （x+y+z==50） and （x*20+y*15+z*10==600）：

print（x，y，z）

設(shè)計(jì)意圖：這兩道習(xí)題主要用來(lái)訓(xùn)練學(xué)生怎樣用程序來(lái)實(shí)現(xiàn)枚舉法，第一道題難點(diǎn)在于確定枚舉對(duì)象和范圍，有一個(gè)三重循環(huán)，第二道題難點(diǎn)在于判斷條件，怎樣將現(xiàn)實(shí)中說(shuō)的話(huà)轉(zhuǎn)換為計(jì)算機(jī)里的if語(yǔ)句。

6.交流評(píng)價(jià)，優(yōu)化枚舉（10分鐘）

提出問(wèn)題：枚舉法是一種比較耗時(shí)的方法，能不能克服這個(gè)缺點(diǎn)呢？有的時(shí)候我們可以通過(guò)優(yōu)化來(lái)解決這個(gè)問(wèn)題，讓計(jì)算量減少，最常用的方法就是減少枚舉的范圍。同學(xué)們能不能通過(guò)優(yōu)化使上面的題1的枚舉范圍減小呢？相鄰的同學(xué)比一比，看誰(shuí)優(yōu)化得好，讓循環(huán)的次數(shù)最少。優(yōu)化前后本題循環(huán)次數(shù)分別是多少？同時(shí)思考，本節(jié)課開(kāi)始的問(wèn)題能不能優(yōu)化呢？怎么優(yōu)化？

設(shè)計(jì)意圖：通過(guò)枚舉優(yōu)化及優(yōu)化前后枚舉次數(shù)的比較，培養(yǎng)學(xué)生優(yōu)化程序的思想;交流優(yōu)化方案，引導(dǎo)學(xué)生自我反思，加深對(duì)所學(xué)知識(shí)的認(rèn)識(shí)和理解，從而得到思想與方法的提升。

7.總結(jié)與拓展（3分鐘）

回顧和總結(jié)本課所學(xué)的知識(shí)：枚舉法的概念、枚舉法的特征、枚舉法的程序?qū)崿F(xiàn)、枚舉法的優(yōu)化。

枚舉法是日常生活中經(jīng)常用到的一種算法，是在沒(méi)有其他更好的方法情況下所使用的容易理解的算法，它的缺點(diǎn)是所耗費(fèi)的時(shí)間比較長(zhǎng)，但是我們可以通過(guò)優(yōu)化來(lái)縮短它的計(jì)算時(shí)間。本節(jié)課我們使用了縮小枚舉范圍的方法來(lái)優(yōu)化枚舉法，大家也可以到網(wǎng)絡(luò)上搜索其他的優(yōu)化方法，讓枚舉法更優(yōu)秀。

設(shè)計(jì)意圖：通過(guò)總結(jié)，讓學(xué)生進(jìn)一步鞏固本節(jié)課的知識(shí);通過(guò)知識(shí)的拓展，擴(kuò)展學(xué)生的知識(shí)視野，激發(fā)他們的學(xué)習(xí)興趣。