《用窮舉法解決問題》教學設計

　　教學分析
　　
　　1.教學目標
　　知識與技能：了解什么是窮舉法及其特點，以及用窮舉法設計算法的基本過程；能夠根據具體問題的要求，使用窮舉法設計算法。
　　過程和方法：運用觀察、發現、歸納、應用的方法，發展學生的歸納思維；培養學生獨立探究與自主發現的學習能力。
　　情感態度與價值觀：了解算法和程序設計在計算機解決問題過程中的重要性；體驗將算法轉變為程序的過程，享受計算機解決問題的快樂。
　　
　　2.教學重點和難點
　　重點：用窮舉算法解決問題的一般步驟；能根據具體問題的要求，提高運用窮舉算法解決問題的能力。
　　難點：通過觀察、類比多種方式培養學生歸納思維。
　　
　　教學過程
　　
　　1.創設情境激趣引入
　　教師活動：某同學用自己的QQ號登錄，可他記不清密碼了，你能幫他找回密碼嗎？他的密碼是一個5位數，67□□8，其中百位和十位上的數字他不記得了，但他還記得該數能夠被78整除，也能被67整除。你能幫他設計一個算法求出該密碼嗎？希望大家能在學習完下面這個例子后就可以解決這個問題。
　　設計意圖：成功的教學不是強制，而是激發學生的學習興趣，該導入正是從學生感興趣的事情著手的。
　　
　　2.觀察—發現—歸納—應用
　　(1)觀察。
　　教師活動：逐語句調試以下程序，分析程序的執行過程，讓學生填寫下表，指出此程序功能。
　　For i=100 to 999
　　a=int(i /100)
　　b=int(i /10) mod 10
　　C=i mod 10
　　If a^3+b^3+c^3=ithen
　　Printi
　　Endif
　　Next i
　　(2)發現。
　　教師引導：在分析上一程序過程中，你能發現什么？
　　學生發現：①通過分析程序的執行過程，可看出變量a存放的是一個三位的自然數百位上的數字，變量b存放的是其十位上的數字，變量c存放的是其個位上的數字；②一個三位的自然數，若滿足百位的立方、十位的立方與個位的立方之和等于它本身，就輸出；③此程序的功能是輸出100～999之間的自然數。
　　教師總結：此程序的特點是將求解對象一一列舉出來，然后逐一加以分析、處理，并驗證結果是否滿足給定的條件。當窮舉完所有對象，問題將最終得以解決。我們把這種算法稱之為窮舉法。
　　
　　教師引導：對于此題，某同學給出了另一種解法，請分析程序的執行過程，說出他采用的是什么算法，比較哪一種方法的效率更高，為什么？
　　For a=1 to 9
　　 For b=0 to 9
　　For c=0 to 9
　　 If a^3+b^3+c^3=a*100+b*10+c then
　　Print a*100+b*10+c
　　 Endif
　　Next c
　　 Next b
　　Next a
　　學生發現：第二種方法依然采用的是窮舉算法。在第一個程序中，循環的次數是900次，每次循環要執行四條語句。而在第二個程序中，循環的次數是9×10×10=900次，但每次循環只執行一條語句，所以第二個程序的執行效率高。
　　(3)歸納。
　　教師活動：通過“輸出自然數”這一例子，能歸納出用窮舉法解決問題的步驟嗎？
　　學生歸納：①確定窮舉對象及搜索范圍：用循環或循環嵌套實現；②寫出符合問題解的條件：用IF語句實現；③盡可能縮小搜索范圍，減少程序運行時間，提高程序的執行效率。
　　(4)應用。
　　教師活動：現在我們反回頭來看剛開始時讓大家思考的那道找回QQ密碼的題，在編程實現之前，我們先來分析回答以下幾個和此題相關的問題：①窮舉的對象是什么？其搜索的范圍是什么？②符合問題解的條件是0vur3OAtfOxEMkQTAM68/Q==什么？③你有方法減小搜索范圍，提高程序的執行效率嗎？
　　學生活動：①窮舉的對象是密碼，其搜索的范圍是67008～67998；②符合問題解的條件是：此數既能被78整除，也能被67整除。
　　學生活動：在用自然語言描述其算法后，編程實現，幫助某同學找回QQ密碼。
　　師生互動：在編程過程中，你遇到哪些困難？你是如何解決的？
　　設計意圖：從一個學生熟悉的例子著手，讓學生在觀察中發現，在發現中質疑，在質疑中歸納，在歸納中解決問題。學生增長知識的過程是輕松愉快的。
　　
　　3.對比歸納，深化思維
　　(1)判斷下列兩題能否用窮舉算法解決，為什么？通過分析，你能歸納出哪些能用窮舉法解決，哪些不能用窮舉法解決？
　　①在一個直角三角形中，三條邊a、b、c的長度都為整數，且一條直角邊a的長度已確定，斜邊c的長度不能超過某數I，找出滿足條件的所有直角三角形。
　　②使用一根長度為L厘米的鐵絲，制作一個面積為S的矩形框，要求，計算出滿足這種條件的矩形的高h和寬w。
　　學生歸納：通過兩題的對比分析，窮舉算法適用的條件是：有明顯的窮舉范圍且求解對象應該是有限的；可以按某種規則列舉對象；有窮舉規則；一時找不出解決問題的更好途徑時。
　　(2)《孫子算經》中有許多有趣的數學題，“雞兔同籠”問題就是一個典型的例子。原題是：“今有雞兔同籠，上有三十五頭，下有九十四足，問雞兔各幾何？”
　　①此題能用窮舉算法解決嗎？若能，請編程實現。
　　學生活動：首先用自然語言描述用窮舉算法解決，然后在此基礎上編程實現。
　　②此題還可以用其他算法解決嗎？若能，請編程實現。
　　問題分析：此題可用現在的方程來解，可以設雞有x只，兔有y只。根據題目條件，因為1只雞有1個頭和2只腳，一只兔有1個頭和4只腳，所以可列出這樣一個二元一次方程組。
　　學生活動：用解析法編程實現。
　　③通過以上問題分析，歸納窮舉算法的優點與缺點。
　　學生活動：比較兩種不同算法，歸納出窮舉算法的優點及缺點。
　　設計意圖：學生的頭腦不是一個需要填滿的容器，而是一個需要燃燒的火把。通過對比、分析、歸納，引導學生的思維活動向縱深發展，由表及里，培養學生良好的思維習慣。