【基本思路】确定枚举对象、枚举范围和判定条件;一一枚举可能的解,验证是否是问题的解。
【缺点】运算量比较大,解题效率不高,若枚举范围太大(一般以不超过两百万次为限),在时间上就难以承受。
- 雄鸡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.