Pascal 窮舉.ppt

《Pascal 窮舉.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、窮舉法2008夏令營執(zhí)教：江蘇省丹陽高級中學(xué)荊曉虹一、引入實例一：編一個程序找出三位數(shù)到七位數(shù)中所有的阿姆斯特朗數(shù)。阿姆斯特朗數(shù)也叫水仙花數(shù),它的定義如下:若一個n位自然數(shù)的各位數(shù)字的n次方之和等于它本身,則稱這個自然數(shù)為阿姆斯特朗數(shù)。例如153(153=1*1*1+3*3*3+5*5*5)是一個三位數(shù)的阿姆斯特朗數(shù),8208則是一個四位數(shù)的阿姆斯特朗數(shù)。窮舉法算法分析：程序只能采用窮舉法,一一驗證范圍內(nèi)的數(shù)是否阿姆斯特朗數(shù),若是則打印之。一、引入算法描述：forI:=100to9999999dobegin驗證是否是阿姆斯特朗數(shù)，若是則輸出；end;窮舉

2、法一、引入實例二：從鍵盤輸入一個正整數(shù)N，驗證其是否為質(zhì)數(shù)，若是則輸出“YES”，否則輸出“NO”。窮舉法算法分析：程序采用窮舉法,一一驗證范圍內(nèi)的數(shù)是否是N的因子,若是做標(biāo)記。一、引入算法描述：Read(n);forI:=2ton-1dobegin驗證i是否是n的因子，若是則做標(biāo)記；end;窮舉法二、窮舉法的基本概念窮舉法窮舉方法是基于計算機特點而進行解題的思維方法。窮舉算法特點是算法簡單，但運行時所花費的時間量大。因此，我們在用窮舉方法解決問題時，應(yīng)盡可能將明顯的不符合條件的情況排除在外，以盡快取得問題的解。根據(jù)問題中的的部分條件（約束條件）將所有可

3、能解的情況列舉出來，然后通過一一驗證是否符合整個問題的求解要求，而得到問題的解。三、窮舉算法模式窮舉法1、問題解的可能搜索范圍：用循環(huán)或循環(huán)嵌套結(jié)構(gòu)實現(xiàn)3、能使程序優(yōu)化的語句，以便縮小搜索范圍，減少程序運行時間。forI:=100to9999999do2、寫出符合問題解的條件。forI:=2ton-1do四、窮舉法應(yīng)用窮舉法窮舉法應(yīng)用很多，比如一些密碼破譯軟件通常就是用的窮舉算法。如在QQ上，OicqPassOver這個工具窮舉你的口令，它根據(jù)機器性能最高可以每秒測試20000個口令，如果口令簡單，一分鐘內(nèi)，密碼就會遭到破譯。下面我們來以兩個例子說明窮舉

4、法的基本應(yīng)用。實例二：有形如：ax3+bx2+cx+d=0這樣的一個一元三次方程。給出該方程中各項的系數(shù)(a，b，c，d均為實數(shù))，并約定該方程存在三個不同實根(根的范圍在-100至100之間)，且根與根之差的絕對值>=1。要求由小到大依次在同一行輸出這三個實根(根與根之間留有空格)，并精確到小數(shù)點后2位。樣例輸入：1??-5??-4??20輸出：-2.00??2.00??5.00四、窮舉法應(yīng)用本題是2001年全國信息學(xué)奧林匹克競賽高中組復(fù)賽第一題，如果考慮解方程的話則比較麻煩。我們可以換個角度思考問題，在-100到100之間找三個滿足方程的實數(shù)，由于窮

5、舉時必須用整型變量，題目又要求保留兩位小數(shù)，我們只需將循環(huán)變量擴大100倍即可順利窮舉，最后只要將所求結(jié)果再縮小100倍即可。四、窮舉法應(yīng)用程序如下：Vara,b,c,d,x:real;i,x1,x2,x3:Integer;BeginRead(a,b,c,d);x1:=MaxInt;x2:=x1;x3:=x1;四、窮舉法應(yīng)用Fori:=-10000To10000DoBeginx:=i/100;IfThenIfi

6、(x1/100:0:2,'',x2/100:0:2,'',x3/100:0:2);End.四、窮舉法應(yīng)用Abs(a*x*x*x+b*x*x+c*x+d)<0.000001四、窮舉法應(yīng)用窮舉法實例三：學(xué)校名次。問題描述：有A，B，C，D，E5所學(xué)校。在一次檢查評比中，已知E?？隙ú皇堑?名或第3名，他們互相進行推測。A校有人說，E校一定是第1名；B校有人說，我?？赡苁堑?名；C校有人說，A校最差；D校有人說，C校不是最好的；E校有人說，D校會獲第1名。結(jié)果只有第1名和第2名學(xué)校的人猜對了。編程指出這5所學(xué)校的名次。四、窮舉法應(yīng)用窮舉法分析：本題是一個邏輯判

7、斷題，一般的邏輯判斷題都采用窮舉法進行解決。我們對5所學(xué)校所得名次的各種可能情況進行窮舉。在每種情況中，為了防止不同學(xué)校取相同的名次，設(shè)立了邏輯數(shù)組x，x[I]為false表示已有某校取第I名。此題的難點在于確定判斷條件。我們設(shè)立邏輯變量b0來描述這一條件，主要有兩個條件：“E校不是第2名或第3名”與“只有第1名和第2名的學(xué)校的人猜對”，后一條件要判斷：1）是否只有兩人說法正確？2）說得正確的人是否是取得第1名和第2名的學(xué)校的人？要判斷是否僅有兩人說正確，須統(tǒng)計正確命題的個數(shù)。為此，設(shè)立了函數(shù)bton，將邏輯量數(shù)值化。四、窮舉法應(yīng)用窮舉法程序：progr

8、aml3(output);vari,a,b,c,d,e,m:integer;x: