枚举及迭代.docVIP

枚举法 　　在进行归纳推理时，如果逐个考察了某类事件的所有可能情况，因而得出一般结论，那么这结论是可靠的，这种 HYPERLINK /view/391647.htm \t _blank 归纳方法叫做枚举法． 　　一、特点：将问题的所有可能的答案一一列举，然后根据条件判断此答案是否合适，合适就保留，不合适就丢弃。例如： 　　找出1到100之间的素数。需要将1到100之间的所有整数进行判断。 　　枚举算法因为要列举问题的所有可能的答案，所有它具备以下几个特点： 　　1、得到的结果肯定是正确的； 　　2、可能做了很多的无用功，浪费了宝贵的时间，效率低下。 　　3、通常会涉及到求极值（如最大，最小，最重等）。 　　二、枚举算法的一般结构：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)为判定条件，穷举各种鸡的个数。 　　下面是解这个百鸡问题的程序 　　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个数分成三组,分别组成三个三位数,且使这三个三位数构