《枚舉法與算法的優化》教學設計

宋巍巍 任靜 曹恒來

● 學習內容分析

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

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

● 學習者分析

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

● 學習目標

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

● 教學過程

1.創設情境，引入枚舉法

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

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

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

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

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

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

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

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

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

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

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

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

3.歸納提升，認識枚舉法

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

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

設計意圖：通過上面的模仿學習，學生對枚舉法已經有了初步的感性的認識，這個環節通過觀察模仿的代碼，適時地歸納出枚舉法解決問題的一般模式，讓學生對枚舉法有更深刻的理解，也為后面將該方法遷移到解決同類問題做準備。

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

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

（1）分析問題。

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

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

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

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

5.改進算法，優化枚舉法

活動3：優化百雞問題算法。

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

小結：枚舉法的優點是簡單直觀，缺點是效率不高。

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

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

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

小結：縮小枚舉范圍是優化枚舉算法的一種策略。

（3）減少循環層數。

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

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

小結：減少循環層數能有效地減少枚舉的次數。

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

6.思維導圖，知識梳理（如圖8）

設計意圖：用思維導圖梳理本課的知識點使學生在頭腦中形成清晰的知識結構。

● 教學反思

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

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

點 ?評

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

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