窮舉算法的研究報(bào)告

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

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

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

3、一錢(qián)3只、問(wèn)一百只雞中公雞母雞、小雞各多少。分析：窮舉的范圍：X:0-100Y:0-100Z:0-100判斷式：X+Y+Z=1005X+3Y+Z/3=100優(yōu)化策略來(lái)提高算法效率，減少循環(huán)的次數(shù)，通過(guò)縮小窮舉范闈.0<-X<-200<-Y<-100/3Z=100-X-Y四.窮舉算法的實(shí)例剖析.用C語(yǔ)言程序來(lái)實(shí)現(xiàn)百錢(qián)買(mǎi)雞fnj題的求解：程序代碼及其運(yùn)行結(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)運(yù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時(shí),在z〈=84;y>二4;消去y;8z-6*x=600；因?yàn)閦<=84所以x<=12；x最小為0時(shí)，z>=75消去z:無(wú)意義。*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ù)問(wèn)題的實(shí)際需要，將反復(fù)操作部分預(yù)處理掉；2、根據(jù)問(wèn)題的實(shí)際的條件實(shí)施剪枝處理。窮舉法是將所有可能性一一代入條件驗(yàn)證的方法。充分利用計(jì)算機(jī)計(jì)算速度快的特點(diǎn)，來(lái)進(jìn)行循環(huán)的方式解決問(wèn)題。在實(shí)際解決問(wèn)題中，應(yīng)注意分析循環(huán)方式，減少循環(huán)次數(shù)，簡(jiǎn)化程序運(yùn)算過(guò)程。根據(jù)問(wèn)題背景，優(yōu)化程序，減小搜索范圍，以便減少程序運(yùn)行時(shí)間。課P題123：1、簡(jiǎn)述計(jì)算機(jī)發(fā)展的兒

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

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