枚舉演算法優化手段

Ⅰ 枚舉演算法的說明

如同結構和聯合一樣，枚舉變數也可用不同的方式說明， 即先定義後說明，同時定義說明或直接說明。設有變數a,b,c被說明為上述的weekday，可採用下述任一種方式：
enum weekday
{
......
};
enum weekday a,b,c;或者為： enum weekday
{
......
}a,b,c;或者為： enum
{
......
}a,b,c;

Ⅱ 枚舉法的實例分析

百錢買百雞問題：有一個人有一百塊錢，打算買一百隻雞。到市場一看，大雞三塊錢一隻，小雞一塊錢三隻，不大不小的雞兩塊錢一隻。現在，請你編一程序，幫他計劃一下，怎麼樣買法，才能剛好用一百塊錢買一百隻雞？
此題很顯然是用枚舉法，我們以三種雞的個數為枚舉對象（分別設為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<x2，f(x1)*(x2)<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.

Ⅲ 枚舉法是什麼

在進行歸納推理時，如果逐個考察了某類事件的所有可能情況，因而得出一般結論，那麼這結論是可靠的，這種歸納方法叫做枚舉法． 一、特點：將問題的所有可能的答案一一列舉，然後根據條件判斷此答案是否合適，合適就保留，不合適就丟棄。例如： 找出1到100之間的素數。需要將1到100之間的所有整數進行判斷。 枚舉演算法因為要列舉問題的所有可能的答案，所有它具備以下幾個特點： 1、得到的結果肯定是正確的； 2、可能做了很多的無用功，浪費了寶貴的時間，效率低下。 3、通常會涉及到求極值（如最大，最小，最重等）。 二、枚舉演算法的一般結構：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） 一一枚舉可能的解，驗證是否是問題的解 下面我們就從枚舉演算法的的優化、枚舉對象的選擇以及判定條件的確定，這三個方面來探討如何用枚舉法解題。 例1：百錢買百雞問題：有一個人有一百塊錢，打算買一百隻雞。到市場一看，大雞三塊錢一隻，小雞一塊錢三隻，不大不小的雞兩塊錢一隻。現在，請你編一程序，幫他計劃一下，怎麼樣買法，才能剛好用一百塊錢買一百隻雞？ 演算法分析：此題很顯然是用枚舉法，我們以三種雞的個數為枚舉對象（分別設為x,y,z）,以三種雞的總數（x+y+z）和買雞用去的錢的總數(x*3+y*2+z)為判定條件，窮舉各種雞的個數。 下面是解這個百雞問題的程序 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)。從上面的對比可以看出，對於枚舉演算法，加強約束條件，縮小枚舉的范圍，是程序優化的主要考慮方向。 在枚舉演算法中，枚舉對象的選擇也是非常重要的，它直接影響著演算法的時間復雜度，選擇適當的枚舉對象可以獲得更高的效率。如下例： 例2、將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 321 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. 在枚舉法解題中，判定條件的確定也是很重要的，如果約束條件不對或者不全面，就窮舉不出正確的結果， 我們再看看下面的例子。 例3 一元三次方程求解(noip2001tg) 問題描述 有形如：ax3+bx2+cx+d=0 這樣的一個一元三次方程。給出該方程中各項的系數(a，b，c，d 均為實數)，並約定該方程存在三個不同實根(根的范圍在-100至100之間)，且根與根之差的絕對值>=1。 要求由小到大依次在同一行輸出這三個實根(根與根之間留有空格)，並精確到小數點後2位。 提示：記方程f(x)=0，若存在2個數x1和x2，且x1<x2，f(x1)*(x2)<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是方程的根，這時根據四舍5入，方程的根也為x。所以我們用(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. 用枚舉法解題的最大的缺點是運算量比較大，解題效率不高，如果枚舉范圍太大（一般以不超過兩百萬次為限），在時間上就難以承受。但枚舉演算法的思路簡單，程序編寫和調試方便，比賽時也容易想到，在競賽中，時間是有限的，我們競賽的最終目標就是求出問題解，因此，如果題目的規模不是很大，在規定的時間與空間限制內能夠求出解，那麼我們最好是採用枚舉法，而不需太在意是否還有更快的演算法，這樣可以使你有更多的時間去解答其他難題

Ⅳ 枚舉法的優缺點主要是什麼

枚舉法的優缺點主要是：
優點

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

缺點

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

Ⅳ 編程，枚舉演算法，急

迪傑斯特拉（Dijkstra）演算法求圖的單源最短路徑
template<class Type>
void Dijkstra(int n, int v, Type dist[], int prev[], Type **c) {
//單源最短路徑問題的 Dijkstra 演算法
bool s[maxint];
for (int i = 1; i <= n; i++) {
dist[i] = c[v][i];
s[i] = false;
if (dist[i] == maxint) prev[i] = 0;
else prev[i] = v;
}
dist[v] = 0; s[v] = true;
for (int i = 1; i < n; i++) {
int temp = maxint;
int u = v;
for (int j = 1; j <= n; j++)
if (!s[j] && dist[j] < temp) {
u = j;
temp = dist[j];
}
s[u] = true;
for (int j = 1; j <= n; j++)
if (!s[j] && c[i][j] < maxint) {
Type newdist = dist[u] + c[u][j];
if (newdist < dist[j]) {
dist[j] = newint;
prev[j] = u;
}
}
}
}
如果還沒解決你的問題，可以加我網路HI賬號。

Ⅵ 數學里的枚舉法是什麼意思

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

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

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

(6)枚舉演算法優化手段擴展閱讀：

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

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

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

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

1、提取有效信息；

2、減少重復計算；

3、將原問題化為更小的問題；

4、根據問題的性質進行截枝；

5、引進其他演算法。

Ⅶ 個位十位,用4個圓形⭕️能擺出幾個不同的兩個數

4個數。分別是13，22，31，40。

本題考查的是枚舉法。採用枚舉演算法解題的基本思路：

（1）確定版枚舉對象、枚舉范權圍和判定條件。

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

(7)枚舉演算法優化手段擴展閱讀：

枚舉法的時間復雜度可以用狀態總數*考察單個狀態的耗時來表示。

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

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

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

1、提取有效信息。

2、減少重復計算。

3、將原問題化為更小的問題。

4、根據問題的性質進行截枝。

5、引進其他演算法。

Ⅷ 枚舉演算法的使用

枚舉類型在使用中有以下規定：
枚舉值是常量，不是變數。不能在程序中用賦值語句再對它賦值。例如對枚舉weekday的元素再作以下賦值： sun=5;mon=2;sun=mon; 都是錯誤的。
枚舉元素本身由系統定義了一個表示序號的數值，從0 開始順序定義為0，1，2…。如在weekday中，sun值為0，mon值為1， …,sat值為6。
例如：
#include<stdio.h>
int main()
{
enum weekday{sun,mon,tue,wed,thu,fri,sat };
weekday a,b,c; //將a，b，c定義為枚舉變數
a=sun;
b=mon;
c=tue;
printf(%d,%d,%d,a,b,c);
return 0;
}
運行結果為：0,1,2
枚舉值也可以用來做判斷比較。如：if(mon>sun) …
枚舉變數的值可以由程序員自己定。如：
enum weekday{sun=7,mon=1,tue,wed,thu,fri,sat};
定義sun為7，mon為1，以後按順序加1，即wed=3。

Ⅸ 枚舉演算法的介紹

在實際問題中， 有些變數的取值被限定在一個有限的范圍內。例如，一個星期內只有七天，一年只有十二個月， 一個班每周有六門課程等等。如果把這些量說明為整型， 字元型或其它類型顯然是不妥當的。 為此，C語言提供了一種稱為「枚舉」的類型。在「枚舉」類型的定義中列舉出所有可能的取值， 被說明為該「枚舉」類型的變數取值不能超過定義的范圍。應該說明的是， 枚舉類型是一種基本數據類型，而不是一種構造類型， 因為它不能再分解為任何基本類型。

Ⅹ 什麼是貪婪連接枚舉演算法

一．貪婪演算法的定義： 貪婪演算法的定義： 貪婪演算法的定義 貪婪演算法又叫登山法，它的根本思想是逐步到達山頂，即逐步獲得最優解，是解決 最優化問題時的一種簡單但適用范圍有限的策略。 二．貪婪演算法思想： 貪婪演算法思想： 貪婪演算法思想 貪婪演算法採用逐步構造最優解的方法， 即在每個階段， 都選擇一個看上去最優的策 略（在一定的標准下） 。策略一旦選擇就不可再更改，貪婪決策的依據稱為貪婪准則， 也就是從問題的某一個初始解出發並逐步逼近給定的目標， 以盡可能快的要求得到更好 的解。而且它在設計時沒有固定的框架，關鍵在於貪婪策略的選擇。但要注意的是選擇 的貪婪策略要具有無後向性， 即某階段狀態一旦確定下來後， 不受這個狀態以後的決策 的影響，也就是說某狀態以後的過程不會影響以前的狀態，只與當前狀態有關。