枚举法:数学与计算机算法术语-中文百科频道

特点

将问题的所有可能的答案一一列举，然后根据条件判断此答案是否合适，合适就保留，不合适就丢弃。例如：找出1到100之间的素数，需要将1到100之间的所有整数进行判断。枚举算法因为要列举问题的所有可能的答案，所有它具备以下几个特点：

1、得到的结果肯定是正确的；

2、可能做了很多的无用功，浪费了宝贵的时间，效率低下。

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

4、数据量大的话，可能会造成时间崩溃。

结构

枚举算法的一般结构：while循环。

首先考虑一个问题：将1到100之间的所有整数转换为二进制数表示。

算法一

fori:=1to100dobegin

将i转换为二进制，采用不断除以2，余数即为转换为2进制以后的结果。一直除商为0为止。

end;

算法二

二进制加法，此时需要数组来帮忙。

programp;

vara:array[1..100]ofinteger;{用于保存转换后的二进制结果}

i,j,k:integer;

begin

fillchar(a,sizeof(a),0);{100个数组元素全部初始化为0}

fori:=1to100dobegin

k:=100;

whilea[k]=1dodec(k);{找高位第一个为0的位置}

a[k]:=1;{找到了立刻赋值为1}

forj:=k+1to100doa[j]:=0;{它后面的低位全部赋值为0}

k:=1;

whilea[k]=0doinc(k);{从最高位开始找不为0的位置}

write('(',i,')2=');

forj:=kto100dowrite(a[j]);{输出转换以后的结果}

writeln;

end;

end.

枚举法，常常称之为穷举法，是指从可能的集合中一一枚举各个元素，用题目给定的约束条件判定哪些是无用的，哪些是有用的。能使命题成立者，即为问题的解。

基本思路

采用枚举算法解题的基本思路：

（1）确定枚举对象、枚举范围和判定条件；

（2）枚举可能的解，验证是否是问题的解。

重点

用这种方法，很快就可以把程序编出来，再将样例数据代入测试也是对的，等成绩下来才发现这题没有全对，只得了一半的分。这种解法为什么是错的呢？错在哪里？前面的分析好象也没错啊，难道这题不能用枚举法做吗？看到这里大家可能有点迷惑了。

在上面的解法中，枚举范围和枚举对象都没有错，而是在验证枚举结果时，判定条件用错了。因为要保留二位小数，所以求出来的解不一定是方程的精确根，也许会正好离精确根差一点，再代入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是方程的根，这时根据四舍五入，方程的根也为x。（不用f（x+0.005）是由于这个问题是有下个循环解决）所以我们用(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;

functionf(x:extended):extended;{计算ax3+bx2+cx+d的值}

begin

f:=((a*x+b)*x+c)*x+d;

end;

begin

read(a,b,c,d);

fork:=-10000to10000do

begin

x:=k/100;

if(f(x-0.005)*f(x+0.005)<0)or(f(x-0.005)=0)thenwrite(x:0:2,'');{若x两端的函数值异号或x-0.005刚好是方程的根，则确定x为方程的根}

end;

end.

优缺点

缺点

用枚举法解题的最大的缺点是运算量比较大，解题效率不高，如果枚举范围太大（一般以不超过两百万次为限），在时间上就难以承受。但枚举算法的思路简单，程序编写和调试方便，比赛时也容易想到，在竞赛中，时间是有限的，我们竞赛的最终目标就是求出问题解，因此，如果题目的规模不是很大，在规定的时间与空间限制内能够求出解，那么我们最好是采用枚举法，而不需太在意是否还有更快的算法，这样可以使你有更多的时间去解答其他难题。