枚舉法的程序實現及優化

計新明

內容分析

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

本節知識需要用兩課時，第一課時主要講解算法及其特征，第二課時主要講解枚舉法的程序實現及其優化，本節課是該節的第二課時。

學情分析

本節課的教學對象是高一的學生，他們在前面的學習中已經學習過Python語言，對該語言的基本語法以及程序的基本結構都有一定的了解，所以本節課中枚舉法的實現部分將使用Python語言。

學習目標

了解枚舉法的概念;掌握枚舉法的特征;枚舉法的程序實現;對枚舉法進行優化。

核心素養

引導學生對提出的問題進行分析，探討問題的解決方案，設計出解決問題的算法并使用程序設計語言來實現此算法，最終解決問題。解決之后繼續思考是否有更好的解決方案，能否對算法進行優化，從而更高效地解決問題。通過本課學習，對學生的核心素養，特別是信息意識和計算思維的提高都有一定的促進作用。

教學重難點

重點：枚舉法的特征、枚舉法的程序實現。

難點：枚舉法的程序實現、枚舉法的優化。

教學媒體

多媒體計算機教室、廣播教學軟件、投影儀、教學幻燈片、Python軟件。

教學策略

本節課主要采用信息技術網絡教學平臺支持下的教學模式，即在教師教學引導下，學生通過任務驅動實現自主學習的教學方法。教學流程為：提出問題→學生探討解決問題的方法→引出枚舉法的概念和特征→怎樣用Python來實現枚舉法→是否能讓我們的程序更加高效→枚舉法的優化。

教學過程

1.新課導入（3分鐘）

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

設計意圖：提出實際問題并讓學生自己去解決，引出今天要講的內容;讓學生使用不同的方法，為后面的優化埋下伏筆;最后讓學生自己動手，讓學生理解得更深刻。

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

教師引出枚舉法的概念：一一列舉所有可能的答案，合適就保留，不合適就丟棄（也就是我們日常生活中通常所說的一個一個去試）。

要求學生列舉出日常生活中可能用到或見到的枚舉法，如密碼鎖忘記密碼了;公安機關破案時先鎖定幾個嫌疑人，一個一個驗證指紋，最后抓到犯罪嫌疑人。

設計意圖：不管學生有沒有解決這個問題，他們的方法都是一個一個去試是否滿足條件，這樣就可以引出枚舉法的概念。

3.引導學生歸納總結出枚舉法的特征（2分鐘）

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

設計意圖：在教師的引導下，學生根據前面的例子歸納出枚舉法的特征。

4.枚舉算法的程序實現（4分鐘）

教師講解枚舉算法實現的三部曲：

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

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

（2）枚舉可能的解（使用循環結構）。

for i in range（1000，9999）：

（3）驗證是不是問題的解（使用選擇結構）。

If（x+y）2=i：

pirnt（i）

設計意圖：將枚舉法的實現分成三步來實現，讓學生更容易理解枚舉法，也更好去實現。

5.課堂活動：實踐與嘗試（15分鐘）

實踐一：按照上面講解的枚舉法實現的三部曲，寫出以下兩道習題的三部曲。

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

題2：這次面試的冠軍在A、B、C、D四位同學中產生。A說：“不是我。”B說：“是C。”C說：“是D。”D說：“C說的不對。”已知四人中有一人說了假話。你能判斷出到底誰是冠軍嗎？（提示：可以將A、B、C、D看成1、2、3、4）

實踐二：使用Python軟件寫出上面題1的完整程序。

注意點：①提示學生寫程序時注意縮進，Python對這個要求比較嚴格;②三種循環是怎樣實現的（教師演示）;③學生完成之后教師使用廣播軟件轉播學生的完成情況，將錯得比較多的地方挑出來講解，總結并評價一些學生的程序。完整程序如下：

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）

設計意圖：這兩道習題主要用來訓練學生怎樣用程序來實現枚舉法，第一道題難點在于確定枚舉對象和范圍，有一個三重循環，第二道題難點在于判斷條件，怎樣將現實中說的話轉換為計算機里的if語句。

6.交流評價，優化枚舉（10分鐘）

提出問題：枚舉法是一種比較耗時的方法，能不能克服這個缺點呢？有的時候我們可以通過優化來解決這個問題，讓計算量減少，最常用的方法就是減少枚舉的范圍。同學們能不能通過優化使上面的題1的枚舉范圍減小呢？相鄰的同學比一比，看誰優化得好，讓循環的次數最少。優化前后本題循環次數分別是多少？同時思考，本節課開始的問題能不能優化呢？怎么優化？

設計意圖：通過枚舉優化及優化前后枚舉次數的比較，培養學生優化程序的思想;交流優化方案，引導學生自我反思，加深對所學知識的認識和理解，從而得到思想與方法的提升。

7.總結與拓展（3分鐘）

回顧和總結本課所學的知識：枚舉法的概念、枚舉法的特征、枚舉法的程序實現、枚舉法的優化。

枚舉法是日常生活中經常用到的一種算法，是在沒有其他更好的方法情況下所使用的容易理解的算法，它的缺點是所耗費的時間比較長，但是我們可以通過優化來縮短它的計算時間。本節課我們使用了縮小枚舉范圍的方法來優化枚舉法，大家也可以到網絡上搜索其他的優化方法，讓枚舉法更優秀。

設計意圖：通過總結，讓學生進一步鞏固本節課的知識;通過知識的拓展，擴展學生的知識視野，激發他們的學習興趣。