《枚举与迭代》由会员分享，可在线阅读，更多相关《枚举与迭代（17页珍藏版）》请在金锄头文库上搜索。
1、枚举法在进行归纳推理时，如果逐个考察了某类事件的所有可能情况，因而得出 一般结论，那么这结论是可靠的，这种 归纳方法叫做枚举法.一、特点：将问题的所有可能的答案一一列举，然后根据条件判断此答案 是否合适，合适就保留，不合适就丢弃。例如：找出 1到100 之间的素数。需要将 1到100之间的所有整数进行判断。 枚举算法因为要列举问题的所有可能的答案，所有它具备以下几个特点：1、得到的结果肯定是正确的；2、可能做了很多的无用功，浪费了宝贵的时间，效率低下。3、通常会涉及到求极值(如最大，最小，最重等)。二、枚举算法的一般结构：while 循环。首先考虑一个问题：将 1到100 之间的所有整数转换为
2、二进制数表示。 算法一：for i:=1 to 100 do begin将 i 转换为二进制，采用不断除以 2，余数即为转换为 2 进制以后的结果 一直除商为 0 为止。end;算法二：二进制加法，此时需要数组来帮忙。program p;var a:array1.100 of integer; 用于保存转换后的二进制结果 i,j,k:integer;beginfillchar(a,sizeof(a),0); 100 个数组元素全部初始化为 0for i:=1 to 100 do begink:=100;while ak=1 do dec(k); 找高位第一个为 0 的位置ak:=1; 找到了立
3、刻赋值为 1for j:=k+1 to 100 do aj:=0; 它后面的低位全部赋值为 0k:=1;while ak=0 do inc(k); 从最高位开始找不为 0 的位置write(,i,)2=);for j:=k to 100 do write(aj); 输出转换以后的结果 writeln;end;end.枚举法，常常称之为穷举法，是指从可能的集合中一一枚举各个元素，用 题目给定的约束条件判定哪些是无用的，哪些是有用的。能使命题成立者，即 为问题的解。采用枚举算法解题的基本思路：(1) 确定枚举对象、枚举范围和判定条件；(2) 一一枚举可能的解，验证是否是问题的解 下面我们就从枚举算
4、法的的优化、枚举对象的选择以及判定条件的确定， 这三个方面来探讨如何用枚举法解题。例 1 ：百钱买百鸡问题：有一个人有一百块钱，打算买一百只鸡。到市场 一看，大鸡三块钱一只，小鸡一块钱三只，不大不小的鸡两块钱一只。现在， 请你编一程序，帮他计划一下，怎么样买法，才能刚好用一百块钱买一百只鸡？算法分析：此题很显然是用枚举法，我们以三种鸡的个数为枚举对象(分 别设为 x,y,z ),以三种鸡的总数( x+y+z )和买鸡用去的钱的总数 (x*3+y*2+z) 为判定条件，穷举各种鸡的个数。下面是解这个百鸡问题的程序var x,y,z:integer;beginfor x:=0to100dofor
5、y:=0to100dofor z:=0to100do 枚举所有可能的解 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;beginfor x:=0 to 100 dofor y:=0 to 100-x dobeginz:
6、=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 个数分成三组 , 分别组成三个三位数
7、 , 且使这三个三位 数构成 1:2:3 的比例 ,试求出所有满足条件的三个三位数 .例如 :三个三位数 192,384,576 满足以上条件 .(NOIP1998pj) 算法分析：这是 1998 年全国分区联赛普及组试题(简称 NOIP1998pj ， 以下同)。此题数据规模不大，可以进行枚举，如果我们不加思地以每一个数 位为枚举对象，一位一位地去枚举：for a:=1 to 9 dofor b:=1 to 9 dofor i:=1 to 9 do这样下去，枚举次数就有9 9次，如果我们分别设三个数为x,2x,3x，以x 为枚举对象，穷举的范围就减少为9 3,在细节上再进一步优化，枚举范围就
8、 更少了。程序如下：vart,x:integer;s,st:string;c:char;beginfor x:=123 to 321 do枚举所有可能的解begint:=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.在枚举法解题中，判定
9、条件的确定也是很重要的，如果约束条件不对或者 不全面，就穷举不出正确的结果， 我们再看看下面的例子。例3 元三次方程求解(noip2001tg)问题描述 有形如： ax3+bx2+cx+d=0 这样的一个一元三次方程。给出该 方程中各项的系数 (a，b，c，d 均为实数 )，并约定该方程存在三个不同实根 (根 的范围在-100 至100 之间) ，且根与根之差的绝对值 =1。要求由小到大依次在同一行输出这三个实根 (根与根之间留有空格 )，并精 确到小数点后 2 位。提示：记方程f(x)=0，若存在2个数x1和x2，且x1vx2 , f(x1)*(x2)v0 , 则在(x1，x2)之间一定有一
10、个根。样例输入： 1 -5 -4 20输出： -2.00 2.00 5.00算法分析：由题目的提示很符合二分法求解的原理，所以此题可以用二分 法。用二分法解题相对于枚举法来说很要复杂很多。此题是否能用枚举法求解 呢？再分析一下题目，根的范围在 -100 到100 之间，结果只要保留两位小数， 我们不妨将根的值域扩大100倍(-10000v=xv=10000)，再以根为枚举对象， 枚举范围是 -10000 到 10000，用原方程式进行一一验证，找出方程的解。有的同学在比赛中是这样做vark:integer;a,b,c,d,x :real;beginread(a,b,c,d);for k:=-1
11、0000 to 10000 dobeginx:=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 中，所得的结果也就不
12、一定等于 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.00 5)0) 和 (f(x-0.005)=0) 作为判定条件。为了程序设计的方便，我们设计一个 函数 f(x) 计算 ax3+bx2+cx+d 的值，
13、程序如下：$N+vark:integer;a,b,c,d,x:extended;function f(x:extended):extended; 计算 ax3+bx2+cx+d 的值beginf:=(a*x+b)*x+c)*x+d;end;beginread(a,b,c,d);for k:=-10000 to 10000 dobeginx:=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. 用枚举法解题的最大的缺
14、点是运算量比较大，解题效率不高，如果枚举范 围太大(一般以不超过两百万次为限)，在时间上就难以承受。但枚举算法的 思路简单，程序编写和调试方便，比赛时也容易想到，在竞赛中，时间是有限的，我们竞赛的最终目标就是求出问题解，因此，如果题目的规模不是很大， 在规定的时间与空间限制内能够求出解，那么我们最好是采用枚举法，而不需 太在意是否还有更快的算法，这样可以使你有更多的时间去解答其他难题。迭代法迭代法也称 辗转法 ，是一种不断用变量的旧值递推新值的过程 ,跟迭代法 相对应的是直接法（或者称为一次解法），即一次性解决问题。迭代法又分为 精确迭代和近似迭代。“二分法”和“牛顿迭代法”属于近似迭代法。迭
15、代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复 执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个 新值。利用迭代算法解决问题，需要做好以下三个方面的工作：一、确定迭代变量。在可以用迭代算法解决的问题中，至少存在一个直接 或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。二、建立迭代关系式。所谓迭代关系式，指如何从变量的前一个值推出其 下一个值的公式（或关系）。迭代关系式的建立是解决迭代问题的关键，通常 可以使用递推或倒推的方法来完成。三、对迭代过程进行控制。在什么时候结束迭代过程？这是编写迭代程序 必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通 常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另 一种是所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的 循环来实现对迭代过程的
