用窮舉法解決問題.ppt

《用窮舉法解決問題.ppt》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。

1、閱讀下面程序，分析執(zhí)行過程，說出程序功能ForI=100to999A=int(I/100)B=int(I/10)mod10C=Imod10Ifa^3+b^3+c^3=IthenprintINextIiabc100100101101153153999999求出100到999之間的所有水仙花數(shù)3.2用窮舉法解決問題一、什么是窮舉法窮舉法又稱枚舉法、列舉法，它將求解對象一一列舉出來，然后逐一加以分析、處理，并驗證結(jié)果是否滿足給定的條件，窮舉完所有對象，問題將最終得以解決。方法一：ForI=100to999A=

2、int(I/100)B=int(I/10)mod10C=Imod10Ifa^3+b^3+c^3=IthenprintINextI方法二：Fora=1to9forb=0to9forc=0to9ifa^3+b^3+c^3=a*100+b*10+cthenprinta*100+b*10+cendifnextcnextbnexta二、用窮舉法解決問題的步驟1、確定問題解可能搜索的范圍：用循環(huán)或嵌套來實現(xiàn)）2、寫出符合問題解的條件：用if語句實現(xiàn)3、盡可能地縮小搜索的范圍，減少程序運行時間，提高程序的執(zhí)行效率。例

3、：公元前5世紀，我國數(shù)學家張丘建在《算經(jīng)》一書中提出了一個“百錢買百雞問題”。問題如下：雞翁一值錢5，雞母一值錢3，雞雛三值錢1。百錢買百雞，問雞翁、雞母和雞雛各幾何？分析：窮舉的對象：窮舉的范圍：判斷式：雞翁、雞母、雞雛0≤X≤1000≤Y≤1000≤Z≤100x+y+z=100且5*x+3*y+z/3=100思考：如何提高算法的效率？1、減少循環(huán)的次數(shù)，通過縮小窮舉范圍0≤a≤100/50≤b≤100/30≤c≤1002、減少循環(huán)嵌套的層數(shù)0≤a≤100/50≤b≤100/3c=100–a–b例3：

4、生活中的問題某同學用自己的QQ號登錄，可他記不清密碼了，你能幫他找回密碼嗎？他的密碼是一個5位數(shù)，67□□8，其中百位和十位上的數(shù)字他不記得了，但他還記得該數(shù)能夠被78整除，也能被67整除。你能幫他設計一個算法求出該密碼嗎？(1)判斷下列兩題能否用窮舉算法解決，為什么？①在一個直角三角形中，三條邊a、b、c的長度都為整數(shù)，且一條直角邊a的長度已確定，斜邊c的長度不能超過某數(shù)I，找出滿足條件的所有直角三角形。②使用一根長度為L厘米的鐵絲，制作一個面積為S的矩形框，要求，計算出滿足這種條件的矩形的高h和寬w

5、。③《孫子算經(jīng)》中有許多有趣的數(shù)學題，“雞兔同籠”問題就是一個典型的例子。原題是：“今有雞兔同籠，上有三十五頭，下有九十四足，問雞兔各幾何？”四、窮舉算法的優(yōu)點與缺點：優(yōu)點：算法簡單缺點：運行時所花費的時間長。三、窮舉算法適用的條件：有明顯的窮舉范圍且求解對象應該是有限的；可以按某種規(guī)則列舉對象；有窮舉規(guī)則；一時找不出解決問題的更好途徑時。