2013教科版選修1《窮舉法》

1、窮舉法 一、引入實例一：輸入繩子的長度實例一：輸入繩子的長度n n，將該繩子分成三段，將該繩子分成三段，每段的長度為正整數(shù)，輸出由該三段繩子組成的每段的長度為正整數(shù)，輸出由該三段繩子組成的三角形個數(shù)。三角形個數(shù)。 一、引入s:=0;s:=0;for a:=1 to n-2 dofor a:=1 to n-2 do for b:=a to n-2 do for b:=a to n-2 do for c:=b to n-2 do for c:=b to n-2 do if (a+bc) and (b+ca) and (c+ab) and if (a+bc) and (b+ca) and (c+ab

2、) and (a+b+c(a+b+c=n) =n) then s:=s+1; then s:=s+1;s:=0;s:=0;for a:=1 to n-2 dofor a:=1 to n-2 do for b:=a to n-2 do for b:=a to n-2 do begin begin c:=n-a-b c:=n-a-b; ; if (a+bc) and (b+ca) and (c+a if (a+bc) and (b+ca) and (c+ab) b) and (c=b) and (c=b) then s:=s+1; then s:=s+1; end; end; 一、引入二、窮舉法的

3、基本概念 三、窮舉算法模式 1、問題解的可能搜索的范圍：問題解的可能搜索的范圍： 用循環(huán)或循環(huán)嵌套結(jié)構(gòu)實現(xiàn)用循環(huán)或循環(huán)嵌套結(jié)構(gòu)實現(xiàn) 2、寫出符合問題解的條件。寫出符合問題解的條件。 3、能使程序優(yōu)化的語句，以便縮小搜索范能使程序優(yōu)化的語句，以便縮小搜索范 圍，減少程序運行時間。圍，減少程序運行時間。 四、窮舉法應(yīng)用 窮舉法應(yīng)用很多，比如一些密碼破譯軟件通窮舉法應(yīng)用很多，比如一些密碼破譯軟件通常就是用的窮舉算法。如在常就是用的窮舉算法。如在QQQQ上，上，OicqPassOverOicqPassOver這個工具窮舉你的口令，它根這個工具窮舉你的口令，它根據(jù)機器性能最高可以每秒測試據(jù)機器性能最高可

4、以每秒測試2000020000個口令，個口令，如果口令簡單，一分鐘內(nèi)，密碼就會遭到破如果口令簡單，一分鐘內(nèi)，密碼就會遭到破譯。下面我們來以三個例子說明窮舉法的基譯。下面我們來以三個例子說明窮舉法的基本應(yīng)用。本應(yīng)用。 實例二：有形如：實例二：有形如：ax3+bx2+cx+d=0這樣的一個一這樣的一個一元三次方程。給出該方程中各項的系數(shù)元三次方程。給出該方程中各項的系數(shù)(a，b，c，d均為實數(shù)均為實數(shù))，并約定該方程存在三個不同實根，并約定該方程存在三個不同實根(根的范圍在根的范圍在-100至至100之間之間)，且根與根之差的絕，且根與根之差的絕對值對值=1。要求由小到大依次在同一行輸出這三。要求

5、由小到大依次在同一行輸出這三個實根個實根(根與根之間留有空格根與根之間留有空格)，并精確到小數(shù)點，并精確到小數(shù)點后后2位。位。提示：記方程提示：記方程f(x)=0，若存在，若存在2個數(shù)個數(shù)x1和和x2，且，且x1x2，f(x1)*(x2)0，則在，則在(x1，x2)之間一定有之間一定有一個一個根。根。樣例樣例輸入：輸入：1-5-420輸出：輸出：-2.002.005.00四、窮舉法應(yīng)用 本題是本題是2001年全國信息學(xué)奧林匹克競賽高中組復(fù)年全國信息學(xué)奧林匹克競賽高中組復(fù)賽第一題，如果考慮解方程的話則比較麻煩。我賽第一題，如果考慮解方程的話則比較麻煩。我們可以換個角度思考問題，在們可以換個角度思

6、考問題，在-100到到100之間找之間找三個滿足方程的實數(shù)，由于窮舉時必須用整型變?nèi)齻€滿足方程的實數(shù)，由于窮舉時必須用整型變量，題目又要求保留兩位小數(shù)，我們只需將循環(huán)量，題目又要求保留兩位小數(shù)，我們只需將循環(huán)變量擴大變量擴大100倍即可順利窮舉，最后只要將所求倍即可順利窮舉，最后只要將所求結(jié)果再縮小結(jié)果再縮小100倍即可。倍即可。四、窮舉法應(yīng)用 程序如下：程序如下：VarVar a,b,c,d,x:real a,b,c,d,x:real; ; i,x1,x2,x3:Integer; i,x1,x2,x3:Integer;BeginBegin Read(a,b,c,d Read(a,b,c,d)

7、;); x1:=MaxInt x1:=MaxInt; ; x2:=x1; x2:=x1; x3:=x1; x3:=x1;四、窮舉法應(yīng)用 For i:=-10000 To 10000 DoFor i:=-10000 To 10000 Do Begin Begin x:=i/100; x:=i/100; If Abs(a If Abs(a* *x x* *x x* *x+bx+b* *x x* *x+cx+c* *x+dx+d)0.000001 )0.000001 ThenThen If ix1 Then x1:=i If ix1 Then x1:=i Else If ix2 Then x2:=i

8、 Else If ix2 Then x2:=i Else If ix3 Then x3:=i; Else If ix3 Then x3:=i;確保確保x1x23x1x23 End; End;Writeln(x1/100:0:2, ,x2/100:0:2, ,x3/100:0:2);Writeln(x1/100:0:2, ,x2/100:0:2, ,x3/100:0:2);End.End.四、窮舉法應(yīng)用 四、窮舉法應(yīng)用 實例三：學(xué)校名次。實例三：學(xué)校名次。 問題描述：有問題描述：有A A，B B，C C，D D，E5E5所學(xué)校。在一次檢所學(xué)校。在一次檢查評比中，已知查評比中，已知E E校肯定不是

9、第?？隙ú皇堑? 2名或第名或第3 3名，他名，他們互相進行推測。們互相進行推測。A A校有人說，校有人說，E E校一定是第校一定是第1 1名；名；B B校有人說，我?？赡苁堑谛Ｓ腥苏f，我?？赡苁堑? 2名；名；C C校有人說，校有人說，A A校校最差；最差；D D校有人說，校有人說，C C校不是最好的；校不是最好的；E E校有人說，校有人說，D D校會獲第校會獲第1 1名。結(jié)果只有第名。結(jié)果只有第1 1名和第名和第2 2名學(xué)校的人名學(xué)校的人猜對了。編程指出這猜對了。編程指出這5 5所學(xué)校的名次。所學(xué)校的名次。 四、窮舉法應(yīng)用 分析：本題是一個邏輯判斷題，一般的邏輯判斷題都采分析：本題是一個邏

10、輯判斷題，一般的邏輯判斷題都采用窮舉法進行解決。我們對用窮舉法進行解決。我們對5 5所學(xué)校所得名次的各種可所學(xué)校所得名次的各種可能情況進行窮舉。在每種情況中，為了防止不同學(xué)校取能情況進行窮舉。在每種情況中，為了防止不同學(xué)校取相同的名次，設(shè)立了邏輯數(shù)組相同的名次，設(shè)立了邏輯數(shù)組x x，xIxI為為falsefalse表示已有表示已有某校取第某校取第I I名。名。此題的難點在于確定判斷條件。我們設(shè)立邏輯變量此題的難點在于確定判斷條件。我們設(shè)立邏輯變量b0b0來來描述這一條件，主要有兩個條件：描述這一條件，主要有兩個條件：“E E校不是第校不是第2 2名或第名或第3 3名名”與與“只有第只有第1 1

11、名和第名和第2 2名的學(xué)校的人猜對名的學(xué)校的人猜對”，后一，后一條件要判斷：條件要判斷：1 1）是否只有兩人說法正確？）是否只有兩人說法正確？2 2）說得正確）說得正確的人是否是取得第的人是否是取得第1 1名和第名和第2 2名的學(xué)校的人？要判斷是否名的學(xué)校的人？要判斷是否僅有兩人說正確，須統(tǒng)計正確命題的個數(shù)。為此，設(shè)立僅有兩人說正確，須統(tǒng)計正確命題的個數(shù)。為此，設(shè)立了函數(shù)了函數(shù)btonbton，將邏輯量數(shù)值化。，將邏輯量數(shù)值化。 四、窮舉法應(yīng)用 程序：程序：program l3(output);var i,a,b,c,d,e,m:integer; x:array1.5 of boolean;

12、b0,b1:boolean;function bton(b:boolean):integer; begin if b then bton:=-1 else bton:=0 end;四、窮舉法應(yīng)用 begin for i:=1 to 5 do xi:=true; for a:=1 to 5 do begin xa:=false; for b:=1 to 5 do if xb then begin xb:=false; for c:=1 to 5 do if xc then begin xc:=false; for d:=1 to 5 do if xd then四、窮舉法應(yīng)用 begin e:=1

13、5-a-b-c-d;b0:=(e2) and (e3); m:=bton(e=1)+bton(b=2)+bton(a=5)+bton(c1)+bton(d=1); b0:=b0 and (m=-2); b1:=(e=1) and (a2); b1:=b1 or (a=5) and(c1) and(c2); b1:=b1 or (c1) and (d1) and (d2); b1:=b1 or (d=1) and (e2); b0:=b0 and not b1; if b0 then writeln(a=,a:2, b=,b:2, c=,c:2, d=,d:2, e=,e:2); xd:=tru

14、e;end;四、窮舉法應(yīng)用 xc:=true; end; xb:=true; end; xa:=true; end;end.運行結(jié)果：運行結(jié)果：a=5 b=2 c=1 d=3 e=4實例四：阿姆斯特朗數(shù)。實例四：阿姆斯特朗數(shù)。問題描述：問題描述：編一個程序找出所有的三位數(shù)到七位編一個程序找出所有的三位數(shù)到七位數(shù)中的阿姆斯特朗數(shù)。數(shù)中的阿姆斯特朗數(shù)。 阿姆斯特朗數(shù)也叫水仙阿姆斯特朗數(shù)也叫水仙花數(shù)花數(shù), ,它的定義如下它的定義如下: :若一個若一個n n位自然數(shù)的各位數(shù)位自然數(shù)的各位數(shù)字的字的n n次方之和等于它本身次方之和等于它本身, ,則稱這個自然數(shù)為阿則稱這個自然數(shù)為阿姆斯特朗數(shù)。例如姆斯特

15、朗數(shù)。例如153(153=1153(153=1* *1 1* *1+31+3* *3 3* *3+53+5* *5 5* *5)5)是一個三位數(shù)的阿姆斯特朗數(shù)是一個三位數(shù)的阿姆斯特朗數(shù),8208,8208則是一個四則是一個四位數(shù)的阿姆斯特朗數(shù)。位數(shù)的阿姆斯特朗數(shù)。 五、窮舉算法的深入應(yīng)用算法分析：算法分析：為了使得程序盡快運行出正確結(jié)果為了使得程序盡快運行出正確結(jié)果, ,程序中使用程序中使用了一個數(shù)組了一個數(shù)組powerpower存放所有數(shù)字的各次冪之值存放所有數(shù)字的各次冪之值, , poweri,jpoweri,j等于等于i i的的j j次方。變量次方。變量currentnumbercurr

16、entnumber存放當(dāng)前要被驗證的數(shù)存放當(dāng)前要被驗證的數(shù), ,數(shù)組數(shù)組digitdigit存放當(dāng)前數(shù)的存放當(dāng)前數(shù)的各位數(shù)字各位數(shù)字, ,開始時開始時digit3=1,digit3=1,其它元素均為其它元素均為0,0,此此時表示當(dāng)前數(shù)為時表示當(dāng)前數(shù)為100100。 highesthighest為當(dāng)前數(shù)的位數(shù)。為當(dāng)前數(shù)的位數(shù)。五、窮舉算法的深入應(yīng)用程序：程序：program ex3(input,outoutp);program ex3(input,outoutp);const maxlen=7;const maxlen=7;var i,j,currentnumber,highest,sum,to

17、tal:longintvar i,j,currentnumber,highest,sum,total:longint; ; digit:array 0.maxlen+1 of integer; digit:array 0.maxlen+1 of integer; power:array 0.9,0.maxlen of longint power:array 0.9,0.maxlen of longint; ;beginbegin for i:=0 to 9 do for i:=0 to 9 do begin begin poweri,0:=1; poweri,0:=1;for j:=1 to

18、maxlen do poweri,j:=poweri,j-1for j:=1 to maxlen do poweri,j:=poweri,j-1* *i i end; end; 五、窮舉算法的深入應(yīng)用 for i:=1 to maxlen do digiti:=0; for i:=1 to maxlen do digiti:=0; digit3:=1; highest:=3; digit3:=1; highest:=3; currentnumber:=100; total:=0; currentnumber:=100; total:=0; while digitmaxlen+1=0 do wh

19、ile digitmaxlen+1=0 do begin begin sum:=0; sum:=0; for i:=1 to highest do for i:=1 to highest do sum:=sum+powerdigiti,highest; sum:=sum+powerdigiti,highest; if sum=currentnumber if sum=currentnumber then begin total:=total+1; then begin total:=total+1; write(currentnumber:maxlen+5); write(currentnum

20、ber:maxlen+5); if total if total mod 6=0 then writeln mod 6=0 then writeln end; end;五、窮舉算法的深入應(yīng)用 digit1:=digit1+1; i:=1; digit1:=digit1+1; i:=1; while digiti=10 do while digiti=10 do begin begin digiti+1:=digiti+1+1; digiti+1:=digiti+1+1; digiti:=0; i:=i+1 digiti:=0; i:=i+1 end; end; if ihighest then

21、 highest:=i; if ihighest then highest:=i; currentnumber:=currentnumber+1 currentnumber:=currentnumber+1 end; end; writeln writelnend.end.五、窮舉算法的深入應(yīng)用優(yōu)化策略一：算法中的時間和空間往往是矛盾的，優(yōu)化策略一：算法中的時間和空間往往是矛盾的，時間復(fù)雜性和空間復(fù)雜性在一定條件下也是可以時間復(fù)雜性和空間復(fù)雜性在一定條件下也是可以相互轉(zhuǎn)化的相互轉(zhuǎn)化的, ,有時候為了提高程序運行的速度有時候為了提高程序運行的速度, ,在在算法的空間要求不苛刻的前提下算法的空間要

22、求不苛刻的前提下, ,設(shè)計算法時可考設(shè)計算法時可考慮充分利用有限的剩余空間來存儲程序中反復(fù)要慮充分利用有限的剩余空間來存儲程序中反復(fù)要計算的數(shù)據(jù)計算的數(shù)據(jù), ,這就是這就是“用空間換時間用空間換時間”策略策略, ,是優(yōu)是優(yōu)化程序的一種常用方法。化程序的一種常用方法。五、窮舉算法的深入應(yīng)用五、窮舉算法的深入應(yīng)用實例五：郵票面值。實例五：郵票面值。問題描述：郵局發(fā)行一套票面有四種不同值的郵票，問題描述：郵局發(fā)行一套票面有四種不同值的郵票，如果每封信所貼郵票張數(shù)不超過三枚，存在整數(shù)，如果每封信所貼郵票張數(shù)不超過三枚，存在整數(shù)，使得用不超過三枚的郵票，可以貼出連續(xù)的整數(shù)、使得用不超過三枚的郵票，可以貼

23、出連續(xù)的整數(shù)、，、，來，找出這四種面值數(shù)，使得值，來，找出這四種面值數(shù)，使得值最大。最大。五、窮舉算法的深入應(yīng)用分析：分析：本題知道每封信郵票數(shù)的范圍（本題知道每封信郵票數(shù)的范圍（=3 ）,郵票有四郵票有四種類型，編程找出能使面值最大郵票。其算法是：種類型，編程找出能使面值最大郵票。其算法是： (1) 面值不同的四種郵票，每封信所貼郵票不超過面值不同的四種郵票，每封信所貼郵票不超過 3 張。張。(2) 用這四種郵票貼出連序的整數(shù)，并且使值最大。用這四種郵票貼出連序的整數(shù)，并且使值最大。(3) 用窮舉法，找出所有符合條件的解。用窮舉法，找出所有符合條件的解。(4) 本題用集合的方法統(tǒng)計郵票面值，

24、提高判重的速度。本題用集合的方法統(tǒng)計郵票面值，提高判重的速度。 設(shè)四種郵票的面值分別為：設(shè)四種郵票的面值分別為： A , B , C , D ，根據(jù)題意，根據(jù)題意設(shè)：設(shè)： A B C D，因此，因此 A=1 ，用循環(huán)語句完成搜索。，用循環(huán)語句完成搜索。 五、窮舉算法的深入應(yīng)用Program p12_3 ; var a, b , c , d ： integer ; x, x0, x1 , x2 , x3, x4 ： integer ; st1 ： set of 1 100 ; Function number( a, b, c, d : integer ) ： integer ; var n1,

25、n2, n3 ,n4 , sum :integer ; begin st1:= ; for n1:= 0 to 3 do 每種郵票所取的張數(shù)每種郵票所取的張數(shù) for n2:= 0 to 3-n1 do for n3:= 0 to 3-n1- n2 do for n4:= 0 to 3-n1-n2-n3 do begin 五、窮舉算法的深入應(yīng)用 if n1+n2+n3+n4 x0 then beginx0:=x; x1:=a ; x2:=b ; x3:=c ; x4:=d 保存最大面值郵票保存最大面值郵票 write( x1：5, x2：5, x3：5, x4：5 );writeln( :10

26、, x0=, x0 );end;end; end.五、窮舉算法的深入應(yīng)用程序運行后，其輸出結(jié)果是：程序運行后，其輸出結(jié)果是： 解答結(jié)果有解答結(jié)果有11 組組1 2 3 4 x0=121 2 3 5 x0=13.1 3 6 10 x0=231 4 7 8 x0=24五、窮舉算法的深入應(yīng)用優(yōu)化思路二：減少窮舉的變量，在使用窮舉算法之優(yōu)化思路二：減少窮舉的變量，在使用窮舉算法之前，先考慮一下解元素之間的關(guān)聯(lián)，將一些非窮舉前，先考慮一下解元素之間的關(guān)聯(lián)，將一些非窮舉不可的解元素列為窮舉變量，其他元素通過計算和不可的解元素列為窮舉變量，其他元素通過計算和分析得出解元素的可能值。分析得出解元素的可能值。優(yōu)

27、化思路三：優(yōu)化思路三： 減少窮舉變量的值域，通過和窮舉變量間的數(shù)減少窮舉變量的值域，通過和窮舉變量間的數(shù)學(xué)關(guān)系定義解元素的值域。學(xué)關(guān)系定義解元素的值域。 五、窮舉算法的深入應(yīng)用實例實例六六：方格填數(shù)。：方格填數(shù)。問題描述：如圖所示的問題描述：如圖所示的8個格子中放入個格子中放入18八個數(shù)八個數(shù)字，使得相鄰的和對角線的數(shù)字之差不為字，使得相鄰的和對角線的數(shù)字之差不為1。編。編程找出所有放法。程找出所有放法。五、窮舉算法的深入應(yīng)用分析：我們先不考慮后一條件，分析：我們先不考慮后一條件，只考慮第一個條件，即把只考慮第一個條件，即把18八八個數(shù)字放入個數(shù)字放入8個格子中。這是容易個格子中。這是容易做到

28、的，就是做到的，就是8個數(shù)字的全排列，個數(shù)字的全排列，共有共有8!=40320種放法。然后對種放法。然后對這這8!個可行解用后一個條件加以個可行解用后一個條件加以檢驗，輸出符合條件的解。對于檢驗，輸出符合條件的解。對于后一個條件中后一個條件中“相鄰相鄰”的判斷，的判斷，可以建立一個鄰接表來解決：可以建立一個鄰接表來解決：11221331442352562673413671478五、窮舉算法的深入應(yīng)用表中表示哪兩個格子是相鄰的，表中表示哪兩個格子是相鄰的，linki,1和和linki,2是相是相鄰的格子的編號。全排列的產(chǎn)生，可以用八重循環(huán)，也可鄰的格子的編號。全排列的產(chǎn)生，可以用八重循環(huán)，也可以

29、用專門的算法，程序留給同學(xué)們自己去完成。利用窮舉以用專門的算法，程序留給同學(xué)們自己去完成。利用窮舉策略編制的程序，其運算量一般是很大的，因此如何提高策略編制的程序，其運算量一般是很大的，因此如何提高算法效率是窮舉算法一個很重要的問題。一般應(yīng)盡量減少算法效率是窮舉算法一個很重要的問題。一般應(yīng)盡量減少可行解的個數(shù)，使得第二步的檢驗運算量盡可能地少?？尚薪獾膫€數(shù)，使得第二步的檢驗運算量盡可能地少。如何來優(yōu)化算法呢如何來優(yōu)化算法呢?五、窮舉算法的深入應(yīng)用如果注意到如果注意到b3和和b6兩個格子，與它們兩個格子，與它們“相鄰相鄰”的格子有的格子有6個，也就是說，放入這兩個格子中的數(shù)，必須和個，也就是說，

30、放入這兩個格子中的數(shù)，必須和6個數(shù)個數(shù)不連續(xù)，僅可以和一個數(shù)是連續(xù)的，這樣的數(shù)只有不連續(xù)，僅可以和一個數(shù)是連續(xù)的，這樣的數(shù)只有2個，個，即即1和和8。這樣，。這樣，b1，b3，b6，b8；4個格子中數(shù)的放法個格子中數(shù)的放法僅有兩種可能：僅有兩種可能：2、8、1、7和和7、1、8、2。而。而b2、b4、b5、b7四個格子中的數(shù)僅需在四個格子中的數(shù)僅需在36四個數(shù)中選擇。經(jīng)過四個數(shù)中選擇。經(jīng)過上述優(yōu)化，可行解僅有：上述優(yōu)化，可行解僅有：24！48個，大大減少了計個，大大減少了計算量。并且檢驗是否符合要求，也只需檢查算量。并且檢驗是否符合要求，也只需檢查(1，2)，(1，4)，(2，5)，(4，7)

31、，(5，8)，(7，8)這這6對數(shù)之差就對數(shù)之差就可以了?？梢粤恕?五、窮舉算法的深入應(yīng)用program exampleb; const link:array1.6,1.2 of integer= (1,2),(1,4),(2,5),(4,7),(5,8),(7,8); var b:array1.8 of integer; procedure print; begin writeln( ,b1:2); writeln(b2:2,b3:2,b4:2); writeln(b5:2,b6:2,b7:2); writeln( ,b8:2) end;五、窮舉算法的深入應(yīng)用function choose:

32、boolean; var i: integer; begin choose:= false; for i:=1 to 6 do if abs(blinki, 1 - blinki ,2) = 1 then exit; choose := true end;五、窮舉算法的深入應(yīng)用procedure try; begin for b2:=3 to 6 do for b4:= 3 to 6 do if b2b4 then for b5:= 3 to 6 do if (b5b2) and (b5b4) then begin b7:= 18 - b2 - b4 - b5; if choose then

33、print; end; end;五、窮舉算法的深入應(yīng)用begin b1:=2;b3:=8;b6:= 1;b8:=7; try; b1:=7;b3:=1 ;b6:=8;b8:=2; try; readlnend.五、窮舉算法的深入應(yīng)用優(yōu)化思路四：分解約束條件，將拆分的約束條件嵌優(yōu)化思路四：分解約束條件，將拆分的約束條件嵌套在相應(yīng)的循環(huán)體間，盡可能減少可行解的數(shù)目，套在相應(yīng)的循環(huán)體間，盡可能減少可行解的數(shù)目，也稱為也稱為“剪枝剪枝”，即把明顯不符合條件的可行解盡，即把明顯不符合條件的可行解盡可能地剪去，減少窮舉的計算量?？赡艿丶羧?，減少窮舉的計算量。六、窮舉算法的代碼實現(xiàn)方法：實例七：實例七：4皇

34、后問題?；屎髥栴}。問題描述：在問題描述：在44的棋盤上安置的棋盤上安置4個皇后，要求個皇后，要求任意兩個皇后不在同一行、不在同一列、不在同任意兩個皇后不在同一行、不在同一列、不在同一對角線上，輸出所有的方案。一對角線上，輸出所有的方案。分析：分析：1 1） 本題是一個搜索問題，搜索范圍本題是一個搜索問題，搜索范圍 4 44 4，找出符，找出符合條件的方案；合條件的方案；2 2）方案必須滿足的條件：任意兩個不在同一行、）方案必須滿足的條件：任意兩個不在同一行、同一列和同一對角線。同一列和同一對角線。 六、窮舉算法的代碼實現(xiàn)方法：方法一程序：方法一程序：const n=4;const n=4;ty

35、pe stack=array1.n of integer;type stack=array1.n of integer;var i1,i2,i3,i4:integer;var i1,i2,i3,i4:integer; s:stack; s:stack;function check:boolean;function check:boolean;var i,j:integer;var i,j:integer;beginbegin for i:=1 to n-1 do for i:=1 to n-1 do for j:=i+1 to n do for j:=i+1 to n doif (si=sj)

36、 or (si-i=sj-j) or (si+i=sj+j)if (si=sj) or (si-i=sj-j) or (si+i=sj+j) then begin check:=false; then begin check:=false; exit exit end; end; check:=true check:=trueend;end;六、窮舉算法的代碼實現(xiàn)方法：procedure print;procedure print;var i:integer;var i:integer;beginbegin for i:=1 to n do write(si:2); for i:=1 to n

37、 do write(si:2); writeln writelnend;end;beginbegin for i1:=1 to n do for i1:=1 to n do for i2:=1 to n do for i2:=1 to n do for i3:=1 to n do for i3:=1 to n do for i4:=1 to n do for i4:=1 to n do begin begins1:=i1;s2:=i2;s3:=i3;s4:=i4;s1:=i1;s2:=i2;s3:=i3;s4:=i4; if check then print; if check then pr

38、int; end; end;end.end.方法二程序：方法二程序：const n=4;const n=4;type stack=array1.n of integer;type stack=array1.n of integer;var i1,i2,i3,i4:integer;var i1,i2,i3,i4:integer; s:stack; s:stack;function check:boolean;function check:boolean;var i,j:integer;var i,j:integer;beginbegin for i:=1 to n-1 do for i:=1 t

39、o n-1 do for j:=i+1 to n do for j:=i+1 to n doif (si=sj) or (si-i=sj-j) or (si+i=sj+j)if (si=sj) or (si-i=sj-j) or (si+i=sj+j) then begin check:=false; then begin check:=false; exit exit end; end; check:=true check:=trueend;end;六、窮舉算法的代碼實現(xiàn)方法：procedure print;procedure print;var i:integervar i:integer

40、; ;beginbegin for i:=1 to n do write(si:2); writeln for i:=1 to n do write(si:2); writelnend;end;beginbegin while s0=1 do while s0=1 do begin j:=n; begin j:=n; while (sj while (sj=4)=4) do j:=j-1; do j:=j-1; sj:=sj+1; sj:=sj+1; for I:=j+1 to n do sI for I:=j+1 to n do sI ：=1;=1; if check then print;

41、 if check then print; end; end;end.end.方法三程序：方法三程序：const n=8;const n=8;type stack=array1.n of integer;type stack=array1.n of integer;var count:integervar count:integer; ; s:stack s:stack; ;function check:booleanfunction check:boolean; ;var i,j:integervar i,j:integer; ;beginbegin for i:=1 to n-1 do f

42、or i:=1 to n-1 do for j:=i+1 to n do for j:=i+1 to n doif (si=sj) or (si-i=sj-j) or if (si=sj) or (si-i=sj-j) or (si+i=sj+j(si+i=sj+j) then begin check:=false;) then begin check:=false; exit exit end; end; check:=true end;check:=true end;六、窮舉算法的代碼實現(xiàn)方法：procedure print;procedure print;var i:integervar

43、 i:integer; ;beginbegin for i:=1 to n do write(si:2); writeln for i:=1 to n do write(si:2); writelnend;end;procedure search(kprocedure search(k: integer);: integer); var i:integer var i:integer; ;beginbegin if k n then begin if k n then begin if check then begin count:=count+1;print;end; if check th

44、en begin count:=count+1;print;end; endend else for i := 1 to n do else for i := 1 to n do begin begin sk sk := i; search(k+1); := i; search(k+1); end end end end; ;begin count := 0; search(1);write(count); end.begin count := 0; search(1);write(count); end.方法四程序：方法四程序：const n=8;const n=8;type stack=a

45、rray0.n of integer;type stack=array0.n of integer;var top,count:integervar top,count:integer; ; s:stack s:stack; ;function check:booleanfunction check:boolean; ;var i,j:integervar i,j:integer; ;beginbegin for i:=1 to n-1 do for i:=1 to n-1 do for j:=i+1 to n do for j:=i+1 to n doif (si=sj) or (si-i=

46、sj-j) or if (si=sj) or (si-i=sj-j) or (si+i=sj+j(si+i=sj+j) then begin check:=false;) then begin check:=false; exit exit end; end; check:=true end; check:=true end;六、窮舉算法的代碼實現(xiàn)方法：beginbeginfillchar(s,sizeof(s),0);fillchar(s,sizeof(s),0); count:=0; count:=0;top:=1;top:=1;repeatrepeat inc(stop inc(stop

47、);); if stop if stop=n then=n then if top=n then if top=n then begin if check then begin if check then begin begin stop stop:=0;dec(top); count:=count+1;:=0;dec(top); count:=count+1; end end end end else inc(top else inc(top) ) else begin stop else begin stop:=0;dec(top);end;:=0;dec(top);end;until t

48、op=0; write(countuntil top=0; write(count);); end. end.七、實例分析：實例八：巧妙填數(shù)。實例八：巧妙填數(shù)。問題描述：將問題描述：將19這九個數(shù)字填入九個空格中。這九個數(shù)字填入九個空格中。每一橫行的三個數(shù)字組成一個三位數(shù)。如果要使第每一橫行的三個數(shù)字組成一個三位數(shù)。如果要使第二行的三位數(shù)是第一行的兩倍，第三行的三位數(shù)是二行的三位數(shù)是第一行的兩倍，第三行的三位數(shù)是第一行的三倍，應(yīng)怎樣填數(shù)。如圖所示。第一行的三倍，應(yīng)怎樣填數(shù)。如圖所示。192384576 七、實例分析：分析：本題目有分析：本題目有9個格子，要求填數(shù)，如果不考慮個格子，要求填數(shù)，如

49、果不考慮問題給出的條件，共有問題給出的條件，共有9！=362880種方案，在種方案，在這些方案中符合問題條件的即為解。因此可以采用這些方案中符合問題條件的即為解。因此可以采用窮舉法。窮舉法。但仔細(xì)分析問題，顯然第一行的數(shù)不會超過但仔細(xì)分析問題，顯然第一行的數(shù)不會超過400，實際上只要確定第一行的數(shù)就可以根據(jù)條件算出實際上只要確定第一行的數(shù)就可以根據(jù)條件算出其他兩行的數(shù)了。這樣僅需窮舉其他兩行的數(shù)了。這樣僅需窮舉400次。次。七、實例分析：program ex_8(input,output); var i,j,k,s:integer; function sum(s:integer):intege

50、r; begin sum:=s div 100+s div 10 mod 10+s mod 10 end;sum function mul(s:integer):longint; begin mul:=(s div 100)*(s div 10 mod 10)*(s mod 10) end;mul七、實例分析：Begin for i:=1 to 3 do for j:=1 to 9 do if ji then for k:=1 to 9 do if (kj) and (ki) then begin s:=i*100+j*10+k; if 3*s1000 then if (sum(s)+sum(

51、2*s)+sum(3*s)=45) and (mul(s)*mul(2*s)*mul(3*s)=362880) then begin writeln(s);writeln(2*s);writeln(3*s); writeln; end; end; end. 實例九：數(shù)塔問題 問題描述：有形如下圖所示的數(shù)塔，從頂部出發(fā)，在每一結(jié)點可以選擇向左走或是向右走，一直走到底層，要求找出一條路徑，使路徑上的數(shù)值的和最接近零。七、實例分析： 輸入數(shù)據(jù)： 輸入文件是numbertap.dat。該文件有若干行，第一行是一個正整數(shù)n(n=20)，下面共有n行整數(shù)，每行整數(shù)的個數(shù)依次是1，2，n個，行首行末無多余空

52、格。并且每個數(shù)字的絕對值不超過1000000。 輸出數(shù)據(jù)： 輸出文件是numbertap.out。文件輸出一行，代表最接近零數(shù)值的絕對值。七、實例分析：const n=4;const n=4;type stack=array0.n of integer;type stack=array0.n of integer;var i,j,k,sum,min:integervar i,j,k,sum,min:integer; ; s:stack s:stack; ; a:array1.n,1.n of integer; a:array1.n,1.n of integer;beginbegin for i

53、:=0 to n do si for i:=0 to n do si:=0;:=0; for i:=1 to n do for i:=1 to n do for j:=1 to i do for j:=1 to i do begin read(ai,j);end begin read(ai,j);end; ; min:=10000; min:=10000; while s1=0 dowhile s1=0 do begin j:=n; begin j:=n; while (sj while (sj=1) do j:=j-1;=1) do j:=j-1; sj sj:=sj+1;:=sj+1; f

54、or I:=j+1 to n do sI for I:=j+1 to n do sI:=0;:=0; k:=1;sum:=0; k:=1;sum:=0; for i:=1 to n do for i:=1 to n do begin begin k:=k+si;write(k,k k:=k+si;write(k,k);); sum:=sum+aI,k sum:=sum+aI,k; write(ai,k,sum);readln write(ai,k,sum);readln; ; end; end; if abs(sum)abs(min if abs(sum)abs(min) then ) the

55、n min:=sum;min:=sum; end; end;end.end. 實例十：選數(shù) 問題描述：已知n（1=n=20）個整數(shù)x1,x2,xn（1=xi=5000000），以及一個整數(shù)k（kn）。從n個整數(shù)中任選k個整數(shù)相加，可分別得到一系列的和?，F(xiàn)在，要求你計算出和為素數(shù)共有多少種。七、實例分析： 本題無數(shù)學(xué)公式可尋，1=n1)是否為素數(shù)最簡單的方法就是看是否是否為素數(shù)最簡單的方法就是看是否存在一個素數(shù)存在一個素數(shù)a(a=sqrt(P)是是P的約數(shù)的約數(shù)，如果不存在，該數(shù)就為素數(shù)，由于在此題中1=xi=5000000,n=20,所以要判斷的數(shù)P不會超過100000000，sqrt(p)=10000，因此，為了加快速度，我們可以用篩選法將210000之間的素數(shù)保存到一個數(shù)組里（共1229個），這樣速度估計將提高好幾倍。窮舉法小結(jié):窮舉的思想往往是最容