窮舉算法的研究報告

《窮舉算法的研究報告》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、:信工142:成立:201406030218什么是窮舉算法？窮舉算法是對可能是解的眾多候選解按照某種順序進(jìn)行逐一枚舉和檢驗，并從中找出那些符合要求的候選解作為問題的解.窮舉算法是基于計算機(jī)運算速度快，善于重復(fù)做同一件事情這一特點的古老算法。窮舉法又稱枚舉法，其運用循環(huán)的方式解決問題，但用窮舉算法解決問題的缺點是當(dāng)問題越復(fù)雜，循環(huán)的次數(shù)越多，所消耗的時間也就越多。窮舉算法的兩個關(guān)鍵點：〈1〉.確定范圍：列舉該問題所有可能的解?！?〉.驗證條件:驗證每個可能解是不是問題的真正解二.窮舉算法設(shè)計的基本方法.采用窮舉法解體的基本

2、思想：〈1〉.明確I'nJ題要求，確定枚舉對象，采用合適類型的變量表示枚舉對象.〈2〉.根據(jù)題目要求，寫出有關(guān)的條件表達(dá)式。這里的條件表達(dá)式可以是數(shù)學(xué)表達(dá)式、關(guān)系表達(dá)式或者邏輯表達(dá)式.<4>.使用循環(huán)語句每句出可能的解，再循環(huán)體內(nèi)驗證各種表達(dá)式是否滿足.〈5〉.根據(jù)問題背景，優(yōu)化程序，以便縮小搜索范圍，減少程序運行時間。三.窮舉算法的優(yōu)化策略.窮舉算法優(yōu)化策的核心思想：減少循環(huán)語句的循環(huán)次數(shù)通過除去明顯不符合條件的可能解，減少循環(huán)運算量.舉例說明：百錢買雞問題：一百個銅錢買了一百只雞，其屮公雞一只5錢、母雞一只3錢，小雞

3、一錢3只、問一百只雞中公雞母雞、小雞各多少。分析：窮舉的范圍：X:0-100Y:0-100Z:0-100判斷式：X+Y+Z=1005X+3Y+Z/3=100優(yōu)化策略來提高算法效率，減少循環(huán)的次數(shù)，通過縮小窮舉范闈.0<-X<-200<-Y<-100/3Z=100-X-Y四.窮舉算法的實例剖析.用C語言程序來實現(xiàn)百錢買雞fnj題的求解：程序代碼及其運行結(jié)果如下：#includeintmain（）{inti，j，k;intn=0；for（i=0;i<=20;i十十）for（j=0;j<=33;j十十）for

4、（k=3;k〈=99;k十=3）n十十sif（（5*i+3*j+k/3==100）&&（i+j+k==100））printf（"公雞=%dt母為=%dt小雞=%d”，i,j,k）;}printf（"程序循環(huán)次數(shù)：％d”，n）;}優(yōu)化程序：三重循環(huán)改為二重循環(huán)運行結(jié)果:#includeintmainOinti，j,k;intn=0；for（i=0；i<=20；i十十）for（j=0；j<=33；j++）ri十十ik=100-i-j;if（k%3=0&&i*5+j*3+k/3==100）prin

5、tf（”公雞=%dt母雞=%dt小雞=%d”，i,j,k）;}printf（"程序循環(huán)次數(shù)：％d”，n）;繼續(xù)優(yōu)化;消去x:7*z+3*y=600;當(dāng)y=0時,在z〈=84;y>二4;消去y;8z-6*x=600；因為z<=84所以x<=12；x最小為0時，z>=75消去z:無意義。*include〈stdio.h>intmain（）{inti，j,k;intn=0；for（i=0;i<=12;i十十）for（j=4;j<=25;j十十）n十十jk=100-i-j；if（k%3==0&&i*5+j*3+k/3

6、==100）printf（"公雞=%（11:母雞=%dt小雞=%d",i，j，k）;printf（”程序循環(huán)次數(shù)：%dn,n）；五、結(jié)果分析提高窮舉效率的方法：1、根據(jù)問題的實際需要，將反復(fù)操作部分預(yù)處理掉；2、根據(jù)問題的實際的條件實施剪枝處理。窮舉法是將所有可能性一一代入條件驗證的方法。充分利用計算機(jī)計算速度快的特點，來進(jìn)行循環(huán)的方式解決問題。在實際解決問題中，應(yīng)注意分析循環(huán)方式，減少循環(huán)次數(shù)，簡化程序運算過程。根據(jù)問題背景，優(yōu)化程序，減小搜索范圍，以便減少程序運行時間。課P題123：1、簡述計算機(jī)發(fā)展的兒

7、個階段的特點。答：第一階段：計算機(jī)主要原件是電+管，可以用機(jī)器語言和匯編語言來編寫程序。第二階段，邏輯單元是晶體管，開始使用管理程序，并出現(xiàn)了操作系統(tǒng)，出現(xiàn)了高級語言，體積比第一代縮小了1000倍。第三階段：中小規(guī)模集成電路，采用半導(dǎo)體寄存器，速度，操作系統(tǒng)的精確度，容量和可靠性人人提高。第四階段：岀現(xiàn)大規(guī)模和超大規(guī)模集成電路。計算機(jī)的運行速度和容量大幅度提高，特點是體積更小，集成度更高的微型化，智能化，網(wǎng)絡(luò)化。1、什么叫計算機(jī)軟件？其有哪幾個發(fā)展階段？答：計算機(jī)軟件是計算機(jī)程序、程序所使用的數(shù)據(jù)以及有關(guān)的文檔資料的集合

8、。即:軟件=程序+數(shù)據(jù)+文檔/第一個階段：電子管計算機(jī)階；第二個階段，晶體管時代；第三個階段：集成電路時代；第四個階段：大規(guī)模和超大規(guī)模的集成電路時代。2、簡述本章所述的基本算法。迭代法；不斷的用變量的舊值遞推新值的過程；遞推法：用問題本身所具有的一種遞推關(guān)系求解問題的方法。遞歸法：為求解規(guī)模較大復(fù)雜問題求解推到比原