《简单枚举算法教案.ppt》由会员分享，可在线阅读，更多相关《简单枚举算法教案.ppt（34页珍藏版）》请在三一办公上搜索。
1、简单枚举算法教案,朱全民,简单枚举法,枚举法所谓枚举法,指的是从可能的解集合中一一枚举各元素,用题目给定的检验条件判定哪些是无用的,哪些是有用的.能使命题成立,即为其解。一般思路：对命题建立正确的数学模型；根据命题确定的数学模型中各变量的变化范围（即可能解的范围）；利用循环语句、条件判断语句逐步求解或证明；枚举法的特点是算法简单，但有时运算量大。对于可能确定解的值域又一时找不到其他更好的算法时可以采用枚举法。,虽然枚举法本质上属于搜索策略，但是它与回溯法有所不同。因为适用枚举法求解的问题必须满足两个条件：可预先确定每个状态的元素个数n；状态元素a1，a2，an的可能值为一个连续的值域。设 ai
2、1状态元素ai的最小值；aik状态元素ai的最大值(1in)，即a11a1a1k，a21a2a2k，ai1aiaik，an1anankfor a1a11 to a1k do fo a2a21 to a2k do for aiai1 to aik do for anan1 to ank do if 状态(a1，ai，an)满足检验条件 then 输出问题的解；,枚举法的优点：由于枚举算法一般是现实生活中问题的“直译”，因此比较直观，易于理解；由于枚举算法建立在考察大量状态、甚至是穷举所有状态的基础上，所以算法的正确性比较容易证明。枚举法的缺点：枚举算法的效率取决于枚举状态的数量以及单个状态枚举的
3、代价，因此效率比较低。,枚举法优缺点,示例,求满足表达式A+B=C的所有整数解，其中A，B，C为1100之间的整数。分析：本题非常简单，即枚举所有情况，符合表达式即可。算法如下：for A:=1 to 100 do for B:=1 to 100 do for C:=1 to 100 do if A+B=C then Writeln(A,+,B,=,C);,显然可以修改如下:for A:=1 to 100 do for B:=1 to 100 do C:=A+B if(C=1)then Writeln(A,+,B,=,C);,巧妙填数,将19这九个数字填入九个空格中。每一横行的三个数字组成一个
4、三位数。如果要使第二行的三位数是第一行的两倍,第三行的三位数是第一行的三倍,应怎样填数。如图,分析,本题目有9个格子，要求填数，如果不考虑问题给出的条件，共有9！=362880种方案，在这些方案中符合问题条件的即为解。因此可以采用枚举法。但仔细分析问题，显然第一行的数不会超过400，实际上只要确定第一行的数就可以根据条件算出其他两行的数了。这样仅需枚举400次。因此设计参考程序：,var i,j,k,s:integer;function sum(s:integer):integer;begin sum:=s div 100+s div 10 mod 10+s mod 10end;functio
5、n mul(s:integer):longint;begin mul:=(s div 100)*(s div 10 mod 10)*(s mod 10)end;,程序,begin for i:=1 to 3 do for j:=1 to 9 do if ji then for k:=1 to 9 do if(kj)and(ki)then begin s:=i*100+j*10+k;求第一行数 if 3*s1000 then if(sum(s)+sum(2*s)+sum(3*s)=45)and(mul(s)*mul(2*s)*mul(3*s)=362880)then 满足条件，并数字都由19组成
6、 begin writeln(s);writeln(2*s);writeln(3*s);writeln;end;end;end.,逻辑判断问题,在某次数学竞赛中,A、B、C、D、E五名学生被取为前五名。请据下列说法判断出他们的具体名次,即谁是第几名？条件1:你如果认为A,B,C,D,E 就是这些人的第一至第五名的名次排列,便大错。因为:没猜对任何一个优胜者的名次。也没猜对任何一对名次相邻的学生。条件2:你如果按D,A,E,C,B 来排列五人名次的话,其结果是:说对了其中两个人的名次。还猜中了两对名次相邻的学生的名次顺序。分析：本题是一个逻辑判断题，一般的逻辑判断题都采用枚举法进行解决。5个人的
7、名次分别可以有5！=120种排列可能，因为120比较小，因此我们对每种情况进行枚举，然后根据条件判断哪些符合问题的要求。,分析:根据已知条件，A1,B2,C3,D4,E5,因此排除了一种可能性，只有4！=24种情况了。,Program Exam;Var A,B,C,D,E:Integer;Cr:Array1.5 Of Char;Begin For A:=1 To 5 Do For B:=1 To 5 Do For C:=1 To 5 Do For D:=1 To 5 Do For E:=1 To 5 Do Begin If(A=1)Or(B=2)Or(C=3)Or(D=4)Or(E=5)The
8、n Continue;ABCDE没猜对一个人的名次 If A,B,C,D,E1,2,3,4,5 Then Continue;他们名次互不重复 If Ord(A=2)+Ord(B=5)+Ord(C=4)+Ord(D=1)+Ord(E=3)2 Then Continue;DAECB猜对了两个人的名次 If(B=A+1)Or(C=B+1)Or(D=C+1)Or(E=D+1)Then Continue;ABCDE没猜对一对相邻名次 If Ord(A=D+1)+Ord(E=A+1)+Ord(C=E+1)+Ord(B=C+1)2 Then Continue;DAECB猜对了两对相邻人名次 CrA:=A;C
9、rB:=B;CrC:=C;CrD:=D;CrE:=E;WRITELN(CR1,CR2,CR3,CR4,CR5);End;End.,跳远,在水平面上整齐的放着n个正三角形，相邻两个三角形的底边之间无空隙，如左图所示。一个小孩子想站在某个三角形i的顶端，跳到三角形j的顶端上(ij)。他总是朝着斜向45度的方向起跳，且初始水平速度v不超过一个给定值v0。在跳跃过程中，由于受到重力作用（忽略空气阻力），小孩子将沿着抛物线行进，水平运动方程为x=x0+vt，竖直运动方程为y=y0+vt 0.5gt2，运动轨迹是一条上凸的抛物线。取g=10.0，(x0，y0)是起跳点坐标。请编程求出他从每个位置起跳能到达
10、的最远三角形的编号。注意：跳跃过程中不许碰到非起点和终点的其他三角形。输入第一行为两个正整数n，v0(3n10，1v0100)，表示三角形的个数和最大水平初速度。第二行有n个正整数li(1li20)，表示从左到右各个三角形的边长。输出输出仅一行，包括n-1个数，表示从三角形1，2，3n-1的顶点出发能到达的最右的三角形编号。如果从某三角形出发无法达到任何三角形，相应的数为0。,状态：起跳点i和i点后的点j。每个状态元素的取值范围：1in-1，i+1jn 约束条件的分析：判断小孩能否从i点跳到j点的方法如下：设起点和终点间的水平距离为l、垂直距离为h。则由物理知识（已在题目中给出）有：t=l/v
11、h=vt 5t2=l 5*。因此，v=sqrt(5*l*l/(l-h)。当然，这个v不一定符合要求，它需要满足两个条件。它不能大于极限速度v0，即必须有v v0 跳跃过程中不得碰到其他三角形。如何判断顶点k是否在抛物线下呢？我们可以算出到达时间t0=dx/v（其中dx为起点到顶点k的水平坐标增量），然后算出该时刻的竖直坐标增量vt0 0.5t02。如果此增量大于起点到顶点k的竖直坐标增量，则抛物线在上方。只有起点和终点之间任何一个三角形的顶点不在抛物线下方，则跳远不能完成。我们在枚举过程中不断将小孩所能跳到的点j调整为best。枚举结束后，best即为试题要求的最远点。,var len：arr
12、ay1.20 of longint；x，y：array1.20 of double；三角形顶端顶点的坐标序列 l，h，t，v，v0：double；ok：boolean；跳跃成功标志 i，j，k，n，best：integer；begin read(n，v0)；输入三角形的个数和最大水平初速度 for i 1 to n do read(leni)；入从左到右各个三角形的边长 x1 len1/2；计算每一个三角形顶端顶点的坐标 y1 len1*sqrt(3)/2；for i 2 to n do begin xi xi-1+leni-1/2+leni/2；yi leni*sqrt(3)/2；end；f
13、or,for i 1 to n-1 do依次计算每一个三角形所能到达的最远点 begin best 0；从三角形i出发能到达的最右的三角形编号初始化 for j i+1 to n do依次枚举右方的每一个三角形 begin l xj-xi；计算三角形i与三角形j的两个顶端顶点的水平距离和垂直距离 h yj-yi；if l v0 then break；若大于极限速度v0，则无法从三角形i起跳 ok true；for k i+1 to j-1 do判断跳跃过程中是否碰到其他三角形begin t(xk-xi)/v；计算到达三角形k的时间,if(v*t-5*t*t)-(yk-yi)1e-6 then
14、begin如果该时刻的竖直坐标增量大于起点到顶点k的竖直坐标增量，则抛物线在上方 ok false；break；end；then end；forif ok then best j 若跳远成功，则三角形j为目前三角形i所能到达的最远点，否则跳远不能完成else break；end；for write(best，)；输出从三角形i的顶点出发所能到达的最右的三角形编号）end；for writeln；end.main,二、枚举算法的优化枚举算法的时间复杂度可以用状态总数*考察单个状态的耗时来表示，因此优化主要是减少状态总数（即减少枚举变量和枚举变量的值域）降低单个状态的考察代价优化过程从几个方面考虑
15、。具体讲提取有效信息减少重复计算将原问题化为更小的问题根据问题的性质进行截枝引进其他算法,现有一个棱长为n的立方体，可以分成n3个1*1*1的单位立方体。每个单位立方体都有一个整数值。n3个单位立方体的数和不会超过longint范围。现在要求在这个立方体找到一个包含完整单位立方体的长方体，使得该长方体内所有单位立方体的数和最大。输入：n(1n20)；n个n*n的数字矩阵，每个数字矩阵代表一层，每个数字代表一个单位立方体的整数值，-999单位立方体的整数值999输出：长方体的数和1、“直译”枚举过程for x11 to n do 枚举所有可能的平面 for x21 to n do for y11
16、 to n do for y21 to n do for z11 to n do 枚举所有可能的上平面和下底面 for z21 to n do 考察状态（x1，y1，z1，x2，y2，z2）；,立方体问题,考察状态（x1，y1，z1，x2，y2，z2）的任务是计算长方体的体积，并调整最优解。设map为立方体对应的三维矩阵；sum为当前长方体的体积；best为最优解。考察过程如下 sum0；for xx1 to x2 do 计算长方体的体积 for yy1 to y2 do for zz1 to z2 do sumsum+mapx，y，z；调整最优解 if sumbest then bestsu
17、m；这个算法相当粗糙，枚举状态的费用为O（n9）2、从减少重复计算入手记录先前考察的结果。在统计长方体2时，只要将长方体1的统计结果加上长方体3就可以了，而不必按上述算法那样重新进行计算。,for x11 to n do 枚举所有可能的水平面 for x21 to n do for y11 to n do for y21 to n do for z11 to n do 枚举上平面的z轴坐标 begin sum0；长方体的体积初始化 for z21 to n do 枚举下底面的z轴坐标 考察状态（x1，y1，z1，x2，y2，z2）；end；for考察过程改为 for xx1 to x2 do
18、计算长方体的体积 for yy1 to y2 do sumsum+mapx，y，z2；if sumbest then bestsum；调整最优解由于利用了计算出的结果，整个算法的时间复杂度降为O（n8）。,3、提取恰当的信息上述考察实际上求出z轴坐标为z2的平面中矩形（x1，y1，x2，y2）的数和。我们将这个数和记为value(a)value(A)=value(ABCD)+value(B)-value(BC)-value(BD)这就启发我们用另一种方法表示立方体的信息：设recx，y，z表示z轴坐标为z的水平面中矩形（1，1，x，y）的数和。z轴坐标为z的水平面中左上角为（x1，y1）、右下
19、角为（x2，y2）的矩阵的数和为recx2，y2，z+recx1，y1，z-recx2，y1，z-recx1，y2，z,Rec数组可以在输入数据的同时计算fillchar(rec，size(rec)，0)；rec数组初始化for z1 to n do 逐层输入信息 for x1 to n do 逐行输入z平面的信息 begin for y1 to n do 逐列输入z平面上x行的信息begin read(mapx，y，z)；输入z平面上（x,y）中的数 if(x=1)and(y=1)计算z平面上以（1，1）为左上角、（x,y）为右下角的矩形的数和then rec1，1，zmap1，1，zels
20、e if y=1 then recx，y，zrecx-1，n，z+mapx，y，z else recx，y，zrecx，y-1，z+mapx，y，z；end；for readln；end；for这样，考察过程就可以改为 sumsum+recx2，y2，z2+recx1，y1，z2-recx2，y1，z2-recx1，y2，z2；if sumbest then bestsum；时间复杂度降为O（n6）。,如果长方体a的数和是负数，则长方体a的计算结果废弃，考察长方体b-a。因为长方体b的数和=长方体b-a的数和+长方体a的数和，由于长方体a的数和为负，长方体b-a的数和一定大于等于长方体b的数和
21、。由此可见，在累计长方体数和的时候，只要由上而下地枚举长方体下底面的z轴坐标即可。设total(z)以z轴坐标为z的平面为下底面的长方体的最大数和total(z)=,for x11 to n do 枚举所有可能的子平面 for x21 to n do for y11 to n do for y21 to n do begin total0；长方体b（该长方体的平面以（x1,y1）为左上角、（x2,y2）为右下上角）的最大数和初始化 for z1 to n do 枚举长方体b下底面的z轴坐标 begin totalmaxtotal，0+recx2，y2，z+recx1-1，y1-1，z-recx
22、2，y1-1，z-recx-1-1，y2，z；计算以z为下底面的长方体b的最大数和if total best then besttotal；调整最优解end；for end；for这一改进使得考察的状态整数降为n5，,时钟问题,时钟问题,输入数据：读9个数码，这些数码给出了9个时钟时针的初始位置。数码与时刻的对应关系为：012点13点26点39点图中的例子对应下列输入数据：330222212输出数据：输出一个最短的移动序列（数字序列），该序列要使所有的时钟指针指向12点，若有等价的多个解，仅需给出其中一个.,分析,我们分析一下表示时钟时针初始位置的数码j（0j3）与时刻的对应关系：012点13
23、点26点39点每移动一次，时针将顺时针旋转90度。由此我们可以得出：对于任意一个时钟i（1i9）来说，从初始位置j出发至少需要Ci=（4-j）mod 4次操作，才能使得时针指向12点。而对每种移动方法要么不采用，要么采用1次、2次或3次，因为操作四次以后，时钟将重复以前状态。因此，9种旋转方案最多产生49个状态。,建立时钟控制表,设计算法,因此我们可以设计如下枚举算法：for p1:=0 to 3 do for p2:=0 to 3 do.for p9:=0 to 3 do if c1满足时钟1 and c2满足时钟2 and.and c9满足时钟9 then 打印解路径；显然，上述枚举算法枚
24、举了所有49=262144个状态，运算量和运行时间颇大。,优化,P4P9可直接由P1，P2，P3求出P4=order(C1-P1-P2);P5=order(C2-P1-P2-P3);P6=order(C3-P2-P3);P7=order(C4-P1-P4-P5);P8=order(C8-P5-P7-P9);P9=order(C6-P3-P5-P6);,结果,所以有C5=(P1+P3+P5+P7+P9)mod 4C7=(P4+P7+P8)mod 4C9=(P6+P8+P9)mod 4上述局部枚举的方法（枚举状态数为43个）比较全部枚举的方法（枚举状态数为49个）来说，由于大幅度削减了枚举量，减少
25、运算次数，因此其时效显著改善,侦探推理,证词中出现的其他话，都不列入逻辑推理的内容。明明所知道的是，他的同学中有N个人始终说假话，其余的人始终说真话。现在，明明需要你帮助他从他同学的话中推断出谁是真正的凶手，请记住，凶手只有一个！要求：判断谁是罪犯？,分析,这道题的关键点是“如何能够快速正确实现出来”，事实上这道题对编码能力的要求要大于对算法本身的要求。由于这道题的数据范围并不是很大，但需要进行“字符串处理”这种比较麻烦的工作，因此在比赛时就可以采用效率低一些的枚举算法来换取编码上的简单。推荐的算法分为两步：1预处理每个人的每一句话，并把它们分类处理；2枚举罪犯和当前星期几，找出所有可能发生的
26、情况。下面我们来逐步细化一下每一步的算法，对于第一步，我们希望的是把一些杂乱的不好处理的“字符串信息”转化为相对比较好处理的信息。为此，我们可以通过把“信息”进行分类的方法使得对于每一类信息，更加方便的处理（即我们可以用一个或者几个变量来表示），由题目描述可以发现语句可分为三类：,分析,1指明i是否是罪犯的语句；2指明今天是星期d的语句；3没有意义的语句(不符合格式要求)。我们必须要说明的是任何不符合格式要求的语句都将被划分到第三类中去，这样在处理每个语句的时候就必须要考虑该语句是否符合格式要求，通过以上的处理，我们对于每一个语句用几个变量就可以表示了。对于第二步的细化，我们在枚举完罪犯和当前
27、星期几之后，就可以比较方便的判断每一句话的真伪了，这样我们再根据每个人所说的话把人进行分类。1没说任何一句有意义的话；2只说真话；3只说假话；4既说真话也说假话。,分析,需要注意的是，对于第一类人我们既可以把他当成说真话的，也可以把他当成说假话的，而如果第四类人存在的话，那么从他本身就可以推出矛盾了。最后，如果对于罪犯i存在一个d使得当前情况是可能的，我们就说i就是可能的罪犯。时间效率O(MP|Day|)（其中Day=Sunday，Monday,Tuesday,Wednesday,Thursday,Friday,Saturday）,优化,我们可以发现在对罪犯和当前星期几进行“双重枚举”时，进行
28、了很多重复的操作，于是我们想到，能不能不枚举是当前星期几？这样我们把这类语句与判断罪犯的语句分离，可以先由判断罪犯的语句中确定一部分人肯定说真话，一部分人肯定说假话，剩下的一部分人就要根据他所说的当前星期几的语句来判断了，首先我们假设所有人判断星期的语句不自相矛盾，这样每个人将在判断这类问题里面至多有一个答案，我们便可以统计判断当前是星期d的总人数，于是改进后的算法对于每一个可能的罪犯，先用O(p)的时间处理所有的话，再用O(|Day|)的时间枚举星期几。这样，改进后算法的复杂度就是O(m(p+|Day|)。那么我们可不可以再进一步，把算法优化到线性？这里面可以比较明确地告诉大家，是可以做到的，具体的算法类似于上面的按照语句的种类分离语句，只是分离得更细，处理得更复杂，在这里就不做赘述，留给大家思考。,
