1、,登錄11，將“課堂資料”中名字為“窮舉法”的文件夾下載到自己的電腦上。,窮舉法,陳忍,復(fù)習(xí)解析法,Private Sub Command1_Click() Dim t As Single Dim s As Single Dim d As Single Dim u As Single t = Val(shuru.Text) s = t d = t Do u = 0.7 * d d = u s = s + d + u Loop While (u = t / 1000) shuchu.Text = s End Sub,導(dǎo)入,某個(gè)暑假你攜帶密碼行李箱外出旅游，旅行中發(fā)

2、現(xiàn)自己忘記了開鎖的密碼，怎么辦？,用窮舉法設(shè)計(jì)程序,一、窮舉法的基本思想 二、窮舉法的程序?qū)嵺` 三、窮舉算法小結(jié),窮舉法的基本含義,“窮舉法”也稱為“枚舉法”或“列舉法”。 窮舉法，指在一個(gè)有窮的可能的解的集合中，一一列舉出集合中的每一個(gè)元素，用題目給定的檢驗(yàn)條件來判斷該元素是否符合條件，若滿足條件，則該元素即為問題的一個(gè)解；否則，該元素就不是該問題的解。窮舉完所有對象，問題最終得以解決。 窮舉法在具體的程序?qū)崿F(xiàn)過程中，可以通過循環(huán)和條件判斷語句來完成。 窮舉法常用于解決“是否存在”或“有多少種可能”等類型的問題。,窮舉法的特點(diǎn),窮舉法的特點(diǎn)是算法簡單，在用窮舉法設(shè)計(jì)算法時(shí)，重點(diǎn)注意優(yōu)化，減少

3、運(yùn)算工作量。 將與問題有關(guān)的知識(shí)條理化、完備化、系統(tǒng)化，從中找出規(guī)律，減少列舉量。,窮舉法的應(yīng)用舉例1,1、“水仙花數(shù)問題” 。 水仙花數(shù)是指一個(gè)三位數(shù)，它的各位數(shù)的立方和正好是等于該數(shù)本身。153=13+53+33。請?jiān)O(shè)計(jì)算法求解該問題。,思路：三位數(shù)范圍100-999 約束條件：該三位數(shù)的各位數(shù)的立方和正好是等于該數(shù)本身 程序結(jié)構(gòu)選擇：一重循環(huán),水仙花數(shù)問題,Private Sub command1_Click() Dim x As Integer Dim a As Integer Dim b As Integer Dim c As Integer x = 100 Do While x =

4、 999 a = x Mod 10 b = x 10 Mod 10 c = x 100 If x = a*a*a+b*b*b+c*c*c Then Print x; x = x + 1 Loop End Sub,窮舉法的應(yīng)用舉例2,2、公雞一只值5元，雞母一只值3元，小雞三只值1元?，F(xiàn)在有100只雞，正好值100元錢，問公雞、母雞和小雞各有幾只？ 設(shè)公雞、母雞、小雞各為x、y、z，列出方程為： x+y+z=100 5x+3y+z/3=100 三個(gè)未知數(shù)，兩個(gè)方程，此題有若干個(gè)解，采用“窮舉法”，把每一種情況都考慮到。 解決此類問題采用“試湊法”，把每一種情況都考慮到。 方法一：最簡單三個(gè)未知數(shù)

5、利用三重循環(huán)來實(shí)現(xiàn)。 方法二：從三個(gè)未知數(shù)的關(guān)系，利用兩重循環(huán)來實(shí)現(xiàn)。,注意：減少窮舉的范圍和不必要的窮舉是優(yōu)化窮舉算法的關(guān)鍵。,百錢買百雞,Private Sub Command1_Click() Dim x, y, z As Integer Dim a As Integer For x = 0 To 20 For y = 0 To 33 For z = 0 To 100 If 5*x+3*y+z/3=100 And x+y+z=100 Then Print x=; x; Print y=; y; Print z=; z End If Next z Next y Next x Print E

6、nd Sub,小結(jié),窮舉法是最簡單的一種解題策略，也是最容易想到的一種方法，利用窮舉法解題需要列舉出問題的解的所有狀態(tài)，其弱點(diǎn)便在于列舉量太大，從而導(dǎo)致算法效率十分低下。 優(yōu)化：通過對問題的分析，挖掘出問題的隱含條件，盡可能排除那些明顯不可能屬于問題的解的狀態(tài)，就是一個(gè)行之有效的辦法。,練習(xí),實(shí)例：輸出100200間不能被3整除的數(shù)。 分析：驗(yàn)證100到200間所有的數(shù)，如果滿足條件則輸出。 實(shí)現(xiàn)：在窗體上添加command1按鈕，其代碼窗口中輸入代碼，如右所示。 說明（1）10個(gè)數(shù)打印一行，a為計(jì)數(shù)變量，i為要驗(yàn)證的數(shù)。 （2）“print”為打印一回車，光標(biāo)跳至下一行；“print i；”為在當(dāng)前位置打印，光標(biāo)向后移動(dòng)。,Private Sub command1_Click() dim a as integer,i as integer a=0 for i=100 to 200 if i mo