【基本思路】确定枚舉對象、枚舉範圍和判定條件;一一枚舉可能的解,驗證是否是問題的解。
【缺點】運算量比較大,解題效率不高,若枚舉範圍太大(一般以不超過兩百萬次為限),在時間上就難以承受。
- 雄雞7元1隻,母雞5元1隻,小雞1元3隻,花100元買100隻雞,如果雄雞、母雞與小雞都必須有。則雄雞、母雞與小雞應該各買多少隻?
先考慮雄雞、母雞與小雞的取值範圍(當然也可從金額着手)
1)由于各種雞都必須有,是以雄雞的最高耗用金額為100-5-1=94元,取7的倍數,得91元,是以雄雞數範圍為1至13
2)母雞的最高耗用金額為100-7-1=92元,取5的倍數,得90元,是以母雞數範圍為1至18
3)小雞的最高耗用金額為100-7-5=88元,則小雞可買88*3=264隻,但由于總雞數限制,小雞數不可>98,是以小雞數範圍為3至96
本題條件為:(1)小雞數+母雞數+雄雞數=100;(2)買小雞款+買母雞款+買雄雞款=100;(3)小雞數為3的倍數。
#include<stdio.h>
int main(){
int c,h,x;//c……雄雞;h……母雞;x……小雞。
for(c=1;c<=13;c++)
for(h=1;h<=18;h++){
if((100-c-h)%3==0&&(7*c+5*h+(100-c-h)/3)==100)
printf("c:%d h:%d x:%d\n",c,h,100-c-h);
}
return 0;
}
- 将1,2...9共9個數分成三組,分别組成三個三位數,且使這三個三位數構成1:2:3的比例,試求出所有滿足條件的三個三位數。例如:三個三位數192,384,576滿足以上條件。
此題資料規模不大,可進行枚舉,但如果我們不假思索地以每一個數位為枚舉對象,一位一位地去枚舉:
for a:=1 to 9 do
for b:=1 to 9 do
………
for i:=1 to 9 do
其枚舉次數達
次,若分别設三個數為x,2x,3x,以x為枚舉對象,窮舉範圍就減少為198次,在細節上再進一步優化,枚舉範圍就可以更少
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.
- 一進制三次方程求解,有 的一進制三次方程。給出該方程中各項的系數(a,b,c,d均為實數),并約定該方程存在三個不同實根(根的範圍在-100至100之間),且根與根之差的絕對值>=1。要求由小到大依次在同一行輸出這三個實根(根與根之間留有空格),并精确到小數點後2位。
枚舉問題
記方程f(x)=0,若存在2個數x1和x2,且x1<x2,f(x1)*(x2)<0,則在(x1,x2)之間一定有一個根。
由題目的提示很符合二分法求解的原理,是以此題可以用二分法。用二分法解題相對于枚舉法來說要複雜很多。此題是否能用枚舉法求解呢?再分析一下題目,根的範圍在-100到100之間,結果隻要保留兩位小數,我們不妨将根的值域擴大100倍(-10000<=x<=10000),再以根為枚舉對象,枚舉範圍是-10000到10000,用原方程式進行一一驗證,找出方程的解。
我們換一個角度來思考問題,設f(x)=ax^3+bx^2+cx+d,若x為方程的根,則根據提示可知,必有f(x-0.005)*f(x+0.005)<0,如果我們以此為枚舉判定條件,問題就逆刃而解。另外,如果f(x-0.005)=0,那麼就說明x-0.005是方程的根,這時根據四舍五入,方程的根也為x。是以我們用(f(x-0.005)*f(x+0.005)<0) 和 (f(x-0.005)=0)作為判定條件。
var
k:integer; a,b,c,d,x:extended;
function f(x:extended):extended; {計算ax^3+bx^2+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.