枚舉法

枚舉法是利用計算機運算速度快、精確度高的特點，對要解決問題的所有可能情況，一個不漏地進行檢驗，從中找出符合要求的答案，因此枚舉法是通過犧牲時間來換取答案的全面性。 ^[1] 

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

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

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

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

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

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

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

枚舉法的基本思想是: 逐一列舉問題所涉及的所有情形，並根據問題提出的條件檢驗哪些是問題的解，哪些應予排除。 ^[4]  採用枚舉算法解題的基本思路：

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

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

枚舉算法的一般結構：循環+判斷語句。 ^[4] 

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

for i:=1 to 100 do begin

將i轉換為 ^[2]  二進制，採用不斷除以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.

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

算法簡單，正確性容易證明，在局部地方使用枚舉法，效果十分的好。 ^[3] 

運算量過大，當問題的規模變大的時候，循環的階數越大，執行速度越慢。 ^[3] 

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

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

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

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

⑴提取有效信息；⑵減少重複計算；⑶將原問題化為更小的問題；⑷根據問題的性質進行截枝；

⑸引進其他算法。