枚舉法(窮舉法)

枚舉法

窮舉法一般指本詞條

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

基本介紹

  • 中文名:枚舉法
  • 外文名: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.
枚舉法,常常稱之為窮舉法,是指從可能的集合中一一枚舉各個元素,用題目給定的約束條件判定哪些是無用的,哪些是有用的。能使命題成立者,即為問題的解。

優缺點

優點

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

缺點

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

枚舉法的最佳化

枚舉法的時間複雜度可以用狀態總數*考察單個狀態的耗時來表示,因此最佳化主要是:
⑴減少狀態總數(即減少枚舉變數和枚舉變數的值域);
⑵降低單個狀態的考察代價。
最佳化過程從幾個方面考慮。具體講
⑴提取有效信息;⑵減少重複計算;⑶將原問題化為更小的問題;⑷根據問題的性質進行截枝;
⑸引進其他算法。

相關詞條

熱門詞條

聯絡我們