枚舉法:數學與計算機算法術語-中文百科頻道

特點

将問題的所有可能的答案一一列舉，然後根據條件判斷此答案是否合适，合适就保留，不合适就丢棄。例如：找出1到100之間的素數，需要将1到100之間的所有整數進行判斷。枚舉算法因為要列舉問題的所有可能的答案，所有它具備以下幾個特點：

1、得到的結果肯定是正确的；

2、可能做了很多的無用功，浪費了寶貴的時間，效率低下。

3、通常會涉及到求極值（如最大，最小，最重等）。

4、數據量大的話，可能會造成時間崩潰。

結構

枚舉算法的一般結構：while循環。

首先考慮一個問題：将1到100之間的所有整數轉換為二進制數表示。

算法一

fori:=1to100dobegin

将i轉換為二進制，采用不斷除以2，餘數即為轉換為2進制以後的結果。一直除商為0為止。

end;

算法二

二進制加法，此時需要數組來幫忙。

programp;

vara:array[1..100]ofinteger;{用于保存轉換後的二進制結果}

i,j,k:integer;

begin

fillchar(a,sizeof(a),0);{100個數組元素全部初始化為0}

fori:=1to100dobegin

k:=100;

whilea[k]=1dodec(k);{找高位第一個為0的位置}

a[k]:=1;{找到了立刻賦值為1}

forj:=k+1to100doa[j]:=0;{它後面的低位全部賦值為0}

k:=1;

whilea[k]=0doinc(k);{從最高位開始找不為0的位置}

write('(',i,')2=');

forj:=kto100dowrite(a[j]);{輸出轉換以後的結果}

writeln;

end;

end.

枚舉法，常常稱之為窮舉法，是指從可能的集合中一一枚舉各個元素，用題目給定的約束條件判定哪些是無用的，哪些是有用的。能使命題成立者，即為問題的解。

基本思路

采用枚舉算法解題的基本思路：

（1）确定枚舉對象、枚舉範圍和判定條件；

（2）枚舉可能的解，驗證是否是問題的解。

重點

用這種方法，很快就可以把程序編出來，再将樣例數據代入測試也是對的，等成績下來才發現這題沒有全對，隻得了一半的分。這種解法為什麼是錯的呢？錯在哪裡？前面的分析好象也沒錯啊，難道這題不能用枚舉法做嗎？看到這裡大家可能有點迷惑了。

在上面的解法中，枚舉範圍和枚舉對象都沒有錯，而是在驗證枚舉結果時，判定條件用錯了。因為要保留二位小數，所以求出來的解不一定是方程的精确根，也許會正好離精确根差一點，再代入ax3+bx2+cx+d中，所得的結果也就不一定等于0，因此用原方程ax3+bx2+cx+d=0作為判斷條件是不準确的。

我們換一個角度來思考問題，設f(x)=ax3+bx2+cx+d，若x為方程的根，則根據提示可知，必有f(x-0.005)*(x+0.005)<0，如果我們以此為枚舉判定條件，問題就逆刃而解。另外，如果f(x-0.005)=0，那麼就說明x-0.005是方程的根，這時根據四舍五入，方程的根也為x。（不用f（x+0.005）是由于這個問題是有下個循環解決）所以我們用(f(x-0.005)*f(x+0.005)<0)和(f(x-0.005)=0)作為判定條件。為了程序設計的方便，我們設計一個函數f(x)計算ax3+bx2+cx+d的值，程序如下：

{$N+}

var

k:integer;

a,b,c,d,x:extended;

functionf(x:extended):extended;{計算ax3+bx2+cx+d的值}

begin

f:=((a*x+b)*x+c)*x+d;

end;

begin

read(a,b,c,d);

fork:=-10000to10000do

begin

x:=k/100;

if(f(x-0.005)*f(x+0.005)<0)or(f(x-0.005)=0)thenwrite(x:0:2,'');{若x兩端的函數值異号或x-0.005剛好是方程的根，則确定x為方程的根}

end;

end.

優缺點

缺點

用枚舉法解題的最大的缺點是運算量比較大，解題效率不高，如果枚舉範圍太大（一般以不超過兩百萬次為限），在時間上就難以承受。但枚舉算法的思路簡單，程序編寫和調試方便，比賽時也容易想到，在競賽中，時間是有限的，我們競賽的最終目标就是求出問題解，因此，如果題目的規模不是很大，在規定的時間與空間限制内能夠求出解，那麼我們最好是采用枚舉法，而不需太在意是否還有更快的算法，這樣可以使你有更多的時間去解答其他難題。