枚舉法

在 數學和 計算機科學理論中，一個集的 枚舉是列出某些有窮序列集的所有成員的 程序，或者是一種特定類型對象的 計數。這兩種類型經常（但不總是）重疊。

將問題的所有可能的答案一一 列舉，然後根據條件判斷此答案是否合適，合適就保留，不合適就丟棄。例如：找出1到100之間的素數，需要將1到100之間的所有 整數進行判斷。

枚舉演演算法因為要列舉問題的所有可能的答案，所有它具備以下幾個特點：

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

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

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

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

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

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

for i:=1 to 100 do begin

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

end;

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

program p;

var a:array[1..100] of integer; {用於保存轉換后的二進位結果}

i,j,k:integer;

begin

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

for i:=1 to 100 do begin

k:=100;

while a[k]=1 do dec(k); {找高位第一個為0的位置}

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

for j:=k+1 to 100 do a[j]:=0; {它後面的低位全部賦值為0}

k:=1;

while a[k]=0 do inc(k); {從最高位開始找不為0的位置}

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

for j:=k to 100 do write(a[j]); {輸出轉換以後的結果}

writeln;

end;

end.

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

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

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

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

百錢買百雞問題：有一個人有一百塊錢，打算買一百隻雞。到市場一看，大雞三塊錢一隻，小雞一塊錢三隻，不大不小的雞兩塊錢一隻。現在，請你編一程序，幫他計劃一下，怎麼樣買法，才能剛好用一百塊錢買一百隻雞？

此題很顯然是用枚舉法，我們以三種雞的個數為枚舉對象（分別設為x,y,z）,以三種雞的總數（x+y+z）和買雞用去的錢的總數(x*3+y*2+z/3)為判定條件，窮舉各種雞的個數。

下面是解這個百雞問題的程序

var x,y,z:integer;

begin

for x:=0 to 100 do

for y:=0 to 100 do

for z:=0 to 100 do{枚舉所有可能的解}

if (x+y+z=100)and(x*3+y*2+z div 3=100)and(z mod 3=0)then writeln('x=',x,'y=',y,'z=',z); {驗證可能的解，並輸出符合題目要求的解}

end.

上面的條件還有優化的空間，三種雞的和是固定的，我們只要枚舉二種雞（x,y），第三種雞就可以根據 約束條件求得（z=100-x-y），這樣就縮小了枚舉範圍，請看下面的程序：

var x,y,z:integer;

begin

for x:=0 to 100 do

for y:=0 to 100-x do

begin

z:=100-x-y;

if (x*3+y*2+z div 3=100)and(z mod 3=0)then writeln('x=',x,'y=',y,'z=',z);

end;

end.

未經優化的程序循環了1013 次，時間複雜度為O(n3)；優化后的程序只循環了（102*101/2）次，時間複雜度為O(n2)。從上面的對比可以看出，對於枚舉演演算法，加強約束條件，縮小枚舉的範圍，是程序優化的主要考慮方向。

將1,2...9共9個數分成三組，分別組成三個三位數，且使這三個三位數構成1:2:3的比例，試求出所有滿足條件的三個三位數.

在枚舉演演算法中，枚舉對象的選擇也是非常重要的，它直接影響著演演算法的時間複雜度，選擇適當的枚舉對象可以獲得更高的效率。

例如：三個三位數192,384,576滿足以上條件.(NOIP1998pj)

演演算法分析：這是1998年全國分區聯賽普及組試題（簡稱NOIP1998pj，以下同）。此題數據規模不大，可以進行枚舉，如果我們不加思地以每一個 數位為枚舉對象，一位一位地去枚舉：

for a:=1 to 9 do

for b:=1 to 9 do

………

for i:=1 to 9 do

這樣下去，枚舉次數就有99次，如果我們分別設三個數為x,2x,3x，以x為枚舉對象，窮舉的範圍就減少為93，在細節上再進一步優化，枚舉範圍就更少了。程序如下：

var

t,x:integer;

s,st:string;

c:char;

begin

for x:=123 to 333 do{枚舉所有可能的解}

begin

t:=0;

str(x,st);{把整數x轉化為字元串，存放在st中}

str(x*2,s); st:=st+s;

str(x*3,s); st:=st+s;

for c:='1' to '9' do{枚舉9個字元，判斷是否都在st中}

if pos(c,st)<>0 then inc(t) else break;{如果不在st中，則退出循環}

if t=9 then writeln(x,' ',x*2,' ',x*3);

end;

end.

在枚舉法解題中，判定條件的確定也是很重要的，如果 約束條件不對或者不全面，就窮舉不出正確的結果，我們再看看下面的例子。

一元三次方程求解(noip2001tg)

問題描述 有形如：ax3+bx2+cx+d=0 這樣的一個一元三次方程。給出該方程中各項的係數(a，b，c，d 均為實數)，並約定該方程存在三個不同實根(根的範圍在-100至100之間)，且根與根之差的絕對值>=1。

要求由小到大依次在同一行輸出這三個 實根(根與根之間留有空格)，並精確到小數點后2位。

提示：記方程f(x)=0，若存在2個數x1和x2，且x1<0，則在(x1，x2)之間一定有一個根。

樣例

輸入：1 -5 -4 20

輸出：-2.00 2.00 5.00

演演算法分析：由題目的提示很符合 二分法求解的原理，所以此題可以用二分法。用二分法解題相對於枚舉法來說很要複雜很多。此題是否能用枚舉法求解呢？再分析一下題目，根的範圍在-100到100之間，結果只要保留 兩位小數，我們不妨將根的值域擴大100倍（-10000<=x<=10000），再以根為枚舉對象，枚舉範圍是-10000到10000，用原 方程式進行一一驗證，找出 方程的解。

有的同學在比賽中是這樣做

var

k:integer;

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

begin

read(a,b,c,d);

for k:=-10000 to 10000 do

begin

x:=k/100;

if a*x*x*x+b*x*x+c*x+d=0 then write(x:0:2,' ');

end;

end.

用這種方法，很快就可以把程序編出來，再將樣例數據代入測試也是對的，等成績下來才發現這題沒有全對，只得了一半的分。

這種解法為什麼是錯的呢？錯在哪裡？前面的分析好象也沒錯啊，難道這題不能用枚舉法做嗎？看到這裡大家可能有點迷惑了。

在上面的解法中，枚舉範圍和枚舉對象都沒有錯，而是在驗證枚舉結果時，判定條件用錯了。因為要保留二位小數，所以求出來的解不一定是方程的精確根，也許會正好離精確根差一點，再代入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;

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

begin

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

end;

begin

read(a,b,c,d);

for k:=-10000 to 10000 do

begin

x:=k/100;

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

end;

end.

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

由於枚舉法一般是現實生活中問題的“直譯”，因此比較直觀，易於理解；枚舉法建立在考察大量狀態、甚至是窮舉所有狀態的基礎上，所以演演算法的正確性比較容易證明。

枚舉法的時間複雜度可以用狀態總數*考察單個狀態的耗時來表示，因此優化主要是：

⑴減少狀態總數（即減少枚舉變數和枚舉變數的值域）

⑵降低單個狀態的考察代價

優化過程從幾個方面考慮。具體講

⑴提取有效信息

⑵減少重複計算

⑶將原問題化為更小的問題

⑷根據問題的性質進行截枝

⑸引進其他演演算法