用窮舉法解決問題

1、第三章 算法的程序?qū)崿F(xiàn) 3.2 用窮舉法設(shè)計程序用窮舉法設(shè)計程序 教學(xué)重點 (1)建立正確的數(shù)學(xué)模型，確定窮舉方案。 (2)根據(jù)命題確定可解空間（即變量的取值范圍） (3)正確表達(dá)“符合條件”的判斷。 教學(xué)難點 o(1)如何確定窮舉方案。o(2)如何評價各種窮舉方案的優(yōu)劣。窮舉法o 窮舉法也是人們常用的解決問題的方法，計算機(jī)的出現(xiàn)大大提升了這種方法的意義 o 計算機(jī)只是人類的工具，窮舉方案的確定得靠人腦來完成，但窮舉過程的實施計算機(jī)卻比人腦有效o 掌握窮舉法窮舉技巧(變量安排、窮舉方案的確定) 問題1：o 公元前5世紀(jì)，我國數(shù)學(xué)家張丘建在算經(jīng)一書中提出了一個“百錢買百雞問題”。問題如下：雞翁一

2、值錢5，雞母一值錢3，雞雛三值錢1。百錢買百雞，問雞翁、雞母和雞雛各幾何？o 設(shè)公雞數(shù)為x，母雞數(shù)為y，小雞數(shù)為z，則有方程： x+y+z=100 5*x+3*y+z/3=100 三個未知數(shù)，兩個方程，如何求解？ 用窮舉法求解問題的基本過程o （1） 分析問題 利用所學(xué)的用解析法設(shè)計程序的方法列出了解析式設(shè)公雞數(shù)為x，母雞數(shù)為y，小雞數(shù)為z，則有方程： x+y+z=100 5*x+3*y+z/3=100根據(jù)題目意思可知： 根據(jù)題目意思上式可優(yōu)化為： 0 X 100 0 X 100 / 5 0 Y 100 0 y 100 / 3 0 Z 100o （2） 設(shè)計算法 X=0 Y=0 z = 100

3、 - x y 判斷5 * x + 3 * y + 1 / 3 * z = 100成立，則打印x,y,z 如果y 33，則 y = y + 1返回 如果x 20，則x = x + 1返回 結(jié)束用窮舉法求解問題的基本過程用窮舉法求解問題的基本過程用窮舉法求解問題的基本過程o （4） 調(diào)試程序o （5） 檢測結(jié)果窮舉法（枚舉法）的基本思想是： 列舉出所有可能的情況，逐個判斷有哪些是符合問題所要求的條件，從而得到問題的全部解答。 即將x、y、z的各種可能的值代入方程，看是否滿足兩個方程，如果滿足，就是一組解。錯誤程序一：（可以得出正確的答案，但程序執(zhí)行的效率較低，錯誤原因是沒有排除不存在的情況,紅色部

4、分為出錯所在） Private Sub Command1_Click()Dim x, y, z As Integer For x = 0 To 100 For y = 0 To 100 z = 100 - x - y If 5 * x + 3 * y + 1 / 3 * z = 100 Then Print x, y, z Next y Next xEnd Sub錯誤程序二：（得出的答案不完整，錯誤原因是：沒有考慮到公雞、母雞均有可能不買。紅色部分為出錯所在）Private Sub Command1_Click()Dim x, y, z As Integer For x = 1 To 20 F

5、or y = 1 To 33 z = 100 - x - y If 5 * x + 3 * y + 1 / 3 * z = 100 Then Print x, y, z Next y Next xEnd Sub本節(jié)小結(jié)o （1）用窮舉算法解決問題，通?？梢詮膬蓚€方面進(jìn)行分析： 確定范圍；問題所涉及的情況有哪些，情況的種數(shù)可不可以確定。 驗證條件：分析出來的這些情況，需要滿足什么條件，才成為問題的答案。o （2）要使用多重循環(huán)。o （3）如何評價一個算法的好壞，在考慮效率的同時，也要考慮程序的易讀性。o 練習(xí)要求（提交作業(yè)） 1、百錢百雞問題的求解百錢百雞問題的求解 2、完成累加器界面和程序完成

6、累加器界面和程序累加器界面和程序累加器界面和程序Private Sub Command1_Click()Dim m, n, k, s As Singlem = Val(Text1.Text) 初值初值n = Val(Text2.Text) 終值終值k = Val(Text3.Text) 步長步長s = 0For i = m To n Step k 求和求和s If k = 0 Then Exit For s = s + iNext iIf k = 0 Then Label6.Caption = 步長為零，錯！步長為零，錯！ Else Label6.Caption = Str$(s)End IfEnd SubPrivate Sub Comman