枚舉法

在進行歸納推理時，如果逐個考察了某類事件的所有可能情況，因而得出一般結論，那么這結論是可靠的，這種歸納方法叫做枚舉法．

基本介紹

• 中文名：枚舉法
• 外文名：Enumeration method
• 定義：逐個考察了某類事件的所有可能
• 藉助：計算機運算速度快精確度高特點
• 結構：while循環
• 算法：二進制加法，此時需要數組來幫忙

簡介

在進行歸納推理時，如果逐個考察了某類事件的所有可能情況，因而得出一般結論，那么這結論是可靠的，這種歸納方法叫做枚舉法。枚舉法是利用計算機運算速度快、精確度高的特點，對要解決問題的所有可能情況，一個不漏地進行檢驗，從中找出符合要求的答案，因此枚舉法是通過犧牲時間來換取答案的全面性。

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

特點

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

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

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

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

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

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

基本思路

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

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

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

結構

枚舉算法的一般結構：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.

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

優缺點

優點

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

缺點

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

枚舉法的最佳化

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

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

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

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

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

⑸引進其他算法。