窮舉法-VB教學(xué)課件

復(fù)習(xí)解析法問(wèn)題：小球從10米處自由落下，每次彈起的高度是下落高度的70%，當(dāng)小球彈起的高度不足原來(lái)高度的千分之一時(shí)，小球就快停止跳動(dòng)了。計(jì)算小球在整個(gè)彈起過(guò)程中所經(jīng)過(guò)的總路程。（忽略彈起高度不足千分之一的部分）復(fù)習(xí)解析法PrivateSubCommand1_Click()DimtAsSingleDimsAsSingleDimdAsSingleDimuAsSinglet=Val(shuru.Text)s=td=tDou=0.7*dd=us=s+d+uLoopWhile(u>=t/1000)shuchu.Text=sEndSub窮舉法窮舉法-VB導(dǎo)入問(wèn)題1：有一把鎖和一串鑰匙（共有10把鑰匙），怎樣找出所有開這把鎖的鑰匙？窮舉法的基本含義“窮舉法”也稱為“枚舉法”或“列舉法”。窮舉法，指在一個(gè)有窮的可能的解的集合中，一一列舉出集合中的每一個(gè)元素，用題目給定的檢驗(yàn)條件來(lái)判斷該元素是否符合條件，若滿足條件，則該元素即為問(wèn)題的一個(gè)解；否則，該元素就不是該問(wèn)題的解。窮舉完所有對(duì)象，問(wèn)題最終得以解決。窮舉法在具體的程序?qū)崿F(xiàn)過(guò)程中，可以通過(guò)循環(huán)和條件判斷語(yǔ)句來(lái)完成。窮舉法常用于解決“是否存在”或“有多少種可能”等類型的問(wèn)題。窮舉法的特點(diǎn)窮舉法的特點(diǎn)是算法簡(jiǎn)單，在用窮舉法設(shè)計(jì)算法時(shí)，重點(diǎn)注意優(yōu)化，減少運(yùn)算工作量。將與問(wèn)題有關(guān)的知識(shí)條理化、完備化、系統(tǒng)化，從中找出規(guī)律，減少列舉量。窮舉法的應(yīng)用舉例11、“水仙花數(shù)問(wèn)題”。水仙花數(shù)是指一個(gè)三位數(shù)，它的各位數(shù)的立方和正好是等于該數(shù)本身。153=1^3+5^3+3^3。請(qǐng)?jiān)O(shè)計(jì)算法求解該問(wèn)題。思路：三位數(shù)范圍100-999約束條件：該三位數(shù)的各位數(shù)的立方和正好是等于該數(shù)本身程序結(jié)構(gòu)選擇：一重循環(huán)水仙花數(shù)問(wèn)題PrivateSubcommand1_Click()DimxAsIntegerDimaAsIntegerDimbAsIntegerDimcAsIntegerx=100DoWhilex<=999a=xMod10b=x\10Mod10c=x\100Ifx=a*a*a+b*b*b+c*c*cThenPrintx;x=x+1LoopEndSub窮舉法的應(yīng)用舉例22、

（百錢買百雞問(wèn)題）大約在公元5世紀(jì)，數(shù)學(xué)家張邱建在他的《算經(jīng)》中提出了一個(gè)聞名于后世的百錢百雞問(wèn)題：雞翁一，值錢五，雞母一，值錢三，雞雛三，值錢一，百錢買百雞，翁、母、雛各幾何？設(shè)公雞、母雞、小雞各為x、y、z，列出方程為：x+y+z=1005x+3y+z/3=100三個(gè)未知數(shù)，兩個(gè)方程，此題有若干個(gè)解，采用“窮舉法”，把每一種情況都考慮到。解決此類問(wèn)題采用“試湊法”，把每一種情況都考慮到。方法一：最簡(jiǎn)單三個(gè)未知數(shù)利用三重循環(huán)來(lái)實(shí)現(xiàn)。方法二：從三個(gè)未知數(shù)的關(guān)系，利用兩重循環(huán)來(lái)實(shí)現(xiàn)。注意：減少窮舉的范圍和不必要的窮舉是優(yōu)化窮舉算法的關(guān)鍵。百錢買百雞PrivateSubCommand1_Click()Dimx,y,zAsIntegerDimaAsIntegerForx=0To20Fory=0To33Forz=0To100If5*x+3*y+z/3=100Andx+y+z=100ThenPrint"x=";x;Print"y=";y;Print"z=";zEndIfNextzNextyNextxPrintEndSub小結(jié)窮舉法是最簡(jiǎn)單的一種解題策略，也是最容易想到的一種方法，利用窮舉法解題需要列舉出問(wèn)題的解的所有狀態(tài)，其弱點(diǎn)便在于列舉量太大，從而導(dǎo)致算法效率十分低下。優(yōu)化：通過(guò)對(duì)問(wèn)題的分析，挖掘出問(wèn)題的隱含條件，盡可能排除那些明顯不可能屬于問(wèn)題的解的狀態(tài)，就是一個(gè)行之有效的辦法。練習(xí)實(shí)例：輸出100~200間不能被3整除的數(shù)。分析：驗(yàn)證100到200間所有的數(shù)，如果滿足條件則輸出。實(shí)現(xiàn)：在窗體上添加command1按鈕，其代碼窗口中輸入代碼，如右所示。說(shuō)明（1）10個(gè)數(shù)打印一行，a為計(jì)數(shù)變量，i為要驗(yàn)證的數(shù)。（2）“print”為打印一回車，光標(biāo)跳至下一行；“printi；”為在當(dāng)前位置打印，光標(biāo)向后移動(dòng)。PrivateSubcommand1_Click()dimaasinteger,iasintegera=0fori=100to200ifimod3<>0thenifa=10thenprinta=0