枚举法_在线百科全书查询
枚举法
在进行归纳推理时，如果逐个考察了某类事件的所有可能情况，因而得出一般结论，那么这结论是可靠的，这种归纳方法叫做枚举法．
简介
枚举法是利用计算机运算速度快、精确度高的特点，对要解决问题的所有可能情况，一个不漏地进行检验，从中找出符合要求的答案，因此枚举法是通过牺牲时间来换取答案的全面性。
在数学和计算机科学理论中，一个集的枚举是列出某些有穷序列集的所有成员的程序，或者是一种特定类型对象的计数。这两种类型经常（但不总是）重叠。
特点
将问题的所有可能的答案一一列举，然后根据条件判断此答案是否合适，合适就保留，不合适就丢弃。例如：
找出1到100之间的素数。需要将1到100之间的所有整数进行判断。
枚举算法因为要列举问题的所有可能的答案，所有它具备以下几个特点：
1、得到的结果肯定是正确的；
2、可能做了很多的无用功，浪费了宝贵的时间，效率低下。
3、通常会涉及到求极值（如最大，最小，最重等）。
4、数据量大的话，可能会造成时间崩溃。
结构
枚举算法的一般结构：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/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)。从上面的对比可以看出，对于枚举算法，加强约束条件，缩小枚举的范围，是程序优化的主要考虑方向。
在枚举算法中，枚举对象的选择也是非常重要的，它直接影响着算法的时间复杂度，选择适当的枚举对象可以获得更高的效率。如下例：
例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 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.
在枚举法解题中，判定条件的确定也是很重要的，如果约束条件不对或者不全面，就穷举不出正确的结果， 我们再看看下面的例子。
例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是方程的根，这时根据四舍五入，方程的根也为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;
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.
缺点
用枚举法解题的最大的缺点是运算量比较大，解题效率不高，如果枚举范围太大（一般以不超过两百万次为限），在时间上就难以承受。但枚举算法的思路简单，程序编写和调试方便，比赛时也容易想到，在竞赛中，时间是有限的，我们竞赛的最终目标就是求出问题解，因此，如果题目的规模不是很大，在规定的时间与空间限制内能够求出解，那么我们最好是采用枚举法，而不需太在意是否还有更快的算法，这样可以使你有更多的时间去解答其他难题。
优点
（1）由于枚举法一般是现实生活中问题的“直译”，因此比较直观，易于理解；
（2）枚举法建立在考察大量状态、甚至是穷举所有状态的基础上，所以算法的正确性比较容易证明。
枚举法的优化
枚举法的时间复杂度可以用状态总数*考察单个状态的耗时来表示，因此优化主要是：
⑴减少状态总数（即减少枚举变量和枚举变量的值域）
⑵降低单个状态的考察代价
优化过程从几个方面考虑。具体讲
⑴提取有效信息
⑵减少重复计算
⑶将原问题化为更小的问题
⑷根据问题的性质进行截枝
⑸引进其他算法
