枚举

简单枚举算法教案朱全民简单枚举法•枚举法•所谓枚举法,指的是从可能的解集合中一一枚举各元素,用题目给定的检验条件判定哪些是无用的,哪些是有用的.能使命题成立,即为其解。一般思路：•对命题建立正确的数学模型；•根据命题确定的数学模型中各变量的变化范围（即可能解的范围）；•利用循环语句、条件判断语句逐步求解或证明；•枚举法的特点是算法简单，但有时运算量大。对于可能确定解的值域又一时找不到其他更好的算法时可以采用枚举法。虽然枚举法本质上属于搜索策略，但是它与回溯法有所不同。因为适用枚举法求解的问题必须满足两个条件：⑴可预先确定每个状态的元素个数n；⑵状态元素a1，a2，…，an的可能值为一个连续的值域。设ai1—状态元素ai的最小值；aik—状态元素ai的最大值(1≤i≤n)，即a11≤a1≤a1k，a21≤a2≤a2k，ai1≤ai≤aik，……，an1≤an≤ankfora1←a11toa1kdofoa2←a21toa2kdo……………………forai←ai1toaikdo……………………foran←an1toankdoif状态(a1，…，ai，…，an)满足检验条件then输出问题的解；枚举法的优点：⑴由于枚举算法一般是现实生活中问题的“直译”，因此比较直观，易于理解；⑵由于枚举算法建立在考察大量状态、甚至是穷举所有状态的基础上，所以算法的正确性比较容易证明。枚举法的缺点：枚举算法的效率取决于枚举状态的数量以及单个状态枚举的代价，因此效率比较低。枚举法优缺点示例求满足表达式A+B=C的所有整数解，其中A，B，C为1~100之间的整数。•分析：本题非常简单，即枚举所有情况，符合表达式即可。•算法如下：•forA:=1to100do•forB:=1to100do•forC:=1to100do•ifA+B=Cthen•Writeln(A,‘+’,B,‘=’,C);显然可以修改如下:forA:=1to100do•forB:=1to100do•C:=A+B•if(C=100)AND(C=1)then•Writeln(A,‘+’,B,‘=’,C);巧妙填数•将1～9这九个数字填入九个空格中。每一横行的三个数字组成一个三位数。如果要使第二行的三位数是第一行的两倍,第三行的三位数是第一行的三倍,应怎样填数。如图192384576分析•本题目有9个格子，要求填数，如果不考虑问题给出的条件，共有9！=362880种方案，在这些方案中符合问题条件的即为解。因此可以采用枚举法。•但仔细分析问题，显然第一行的数不会超过400，实际上只要确定第一行的数就可以根据条件算出其他两行的数了。这样仅需枚举400次。因此设计参考程序：vari,j,k,s:integer;functionsum(s:integer):integer;beginsum:=sdiv100+sdiv10mod10+smod10end;functionmul(s:integer):longint;beginmul:=(sdiv100)*(sdiv10mod10)*(smod10)end;程序•begin•fori:=1to3do•forj:=1to9do•ifjithenfork:=1to9do•if(kj)and(ki)thenbegin•s:=i*100+j*10+k;{求第一行数}•if3*s1000then•if(sum(s)+sum(2*s)+sum(3*s)=45)and(mul(s)*mul(2*s)*mul(3*s)=362880)then{满足条件，并数字都由1~9组成}•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个人的名次分别可以有5！=120种排列可能，因为120比较小，因此我们对每种情况进行枚举，然后根据条件判断哪些符合问题的要求。分析:根据已知条件，A1,B2,C3,D4,E5,因此排除了一种可能性，只有4！=24种情况了。•ProgramExam;•Var•A,B,C,D,E:Integer;•Cr:Array[1..5]OfChar;•Begin•ForA:=1To5Do•ForB:=1To5Do•ForC:=1To5Do•ForD:=1To5Do•ForE:=1To5DoBegin•If(A=1)Or(B=2)Or(C=3)Or(D=4)Or(E=5)•ThenContinue;{ABCDE没猜对一个人的名次}•If[A,B,C,D,E][1,2,3,4,5]ThenContinue;{他们名次互不重复}•IfOrd(A=2)+Ord(B=5)+Ord(C=4)+Ord(D=1)+Ord(E=3)2•ThenContinue;{DAECB猜对了两个人的名次}•If(B=A+1)Or(C=B+1)Or(D=C+1)Or(E=D+1)•ThenContinue;{ABCDE没猜对一对相邻名次}•IfOrd(A=D+1)+Ord(E=A+1)+Ord(C=E+1)+Ord(B=C+1)2•ThenContinue;{DAECB猜对了两对相邻人名次}•Cr[A]:='A';Cr[B]:='B';Cr[C]:='C';•Cr[D]:='D';Cr[E]:='E';•WRITELN(CR[1],'',CR[2],'',CR[3],'',CR[4],'',CR[5]);•End;•End.跳远在水平面上整齐的放着n个正三角形，相邻两个三角形的底边之间无空隙，如左图所示。一个小孩子想站在某个三角形i的顶端，跳到三角形j的顶端上(ij)。他总是朝着斜向45度的方向起跳，且初始水平速度v不超过一个给定值v0。在跳跃过程中，由于受到重力作用（忽略空气阻力），小孩子将沿着抛物线行进，水平运动方程为x=x0+vt，竖直运动方程为y=y0+vt–0.5gt2，运动轨迹是一条上凸的抛物线。取g=10.0，(x0，y0)是起跳点坐标。请编程求出他从每个位置起跳能到达的最远三角形的编号。注意：跳跃过程中不许碰到非起点和终点的其他三角形。输入第一行为两个正整数n，v0(3≤n≤10，1≤v0≤100)，表示三角形的个数和最大水平初速度。第二行有n个正整数li(1≤li≤20)，表示从左到右各个三角形的边长。输出输出仅一行，包括n-1个数，表示从三角形1，2，3…n-1的顶点出发能到达的最右的三角形编号。如果从某三角形出发无法达到任何三角形，相应的数为0。状态：起跳点i和i点后的点j。每个状态元素的取值范围：1≤i≤n-1，i+1≤j≤n约束条件的分析：判断小孩能否从i点跳到j点的方法如下：设起点和终点间的水平距离为l、垂直距离为h。则由物理知识（已在题目中给出）有：t=l/vh=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即为试题要求的最远点。2)(vlvarlen：array[1..20]oflongint；x，y：array[1..20]ofdouble；{三角形顶端顶点的坐标序列}l，h，t，v，v0：double；ok：boolean；{跳跃成功标志}i，j，k，n，best：integer；beginread(n，v0)；{输入三角形的个数和最大水平初速度}fori←1tondoread(len[i])；入从左到右各个三角形的边长}x[1]←len[1]/2；{计算每一个三角形顶端顶点的坐标}y[1]←len[1]*sqrt(3)/2；fori←2tondobeginx[i]←x[i-1]+len[i-1]/2+len[i]/2；y[i]←len[i]*sqrt(3)/2；end；{for}fori←1ton-1do{依次计算每一个三角形所能到达的最远点}beginbest←0；{从三角形i出发能到达的最右的三角形编号初始化}forj←i+1tondo{依次枚举右方的每一个三角形}beginl←x[j]-x[i]；{计算三角形i与三角形j的两个顶端的水平距离和垂直距离}h←y[j]-y[i]；iflhthenbreak；{若起跳角度超过45度，则无法从三角形i起跳}v←sqrt(5*l*l/(l-h))；{计算即时速度v}ifvv0thenbreak；{若大于极限速度v0，则无法从三角形i起跳}ok←true；fork←i+1toj-1do{判断跳跃过程中是否碰到其他三角形}begint←(x[k]-x[i])/v；{计算到达三角形k的时间}if(v*t-5*t*t)-(y[k]-y[i])1e-6thenbegin{如果该时刻的竖直坐标增量大于起点到顶点k的竖直坐标增量，则抛物线在上方}ok←false；break；end；{then}end；{for}ifokthenbest←j{若跳远成功，则三角形j为目前三角形i所能到达的最远点，否则跳远不能完成}elsebreak；end；{for}write(best，'')；{输出从三角形i的顶点出发所能到达的最右的三角形编号）end；{for}writeln；end.{main}二、枚举算法的优化枚举算法的时间复杂度可以用状态总数*考察单个状态的耗时来表示，因此优化主要是⑴减少状态总数（即减少枚举变量和枚举变量的值域）⑵降低单个状态的考察代价优化过程从几个方面考虑。具体讲⑴提取有效信息⑵减少重复计算⑶将原问题化为更小的问题⑷根据问题的性质进行截枝⑸引进其他算法现有一个棱长为n的立方体，可以分成n3个1*1*1的单位立方体。每个单位立方体都有一个整数值。n3个单位立方体的数和不会超过longint范围。现在要求在这个立方体找到一个包含完整单位立方体的长方体，使得该长方体内所有单位立方体的数和最大。输入：n(1≤n≤20)；n个n*n的数字矩阵，每个数字矩阵代表一层，每个数字代表一个单位立方体的整数值，-999≤单位立方体的整数值≤999输出：长方体的数和1、“直译”枚举过程forx1←1tondo{枚举所有可能的平面}forx2←1tondofory1←1tondofory2←1tondoforz1←1tondo{枚举所有可能的上平面和下底面}forz2←1tondo考察状态（x1，y1，z1，x2，y2，z2）；立方体问题考察状态（x1，y1，z1，x2，y2，z2）的任务是计算长方体的体积，并调整最优解。设map为立方体对应的三维矩阵；sum为当前长方体的体积；best为最优解。考察过程如下sum←0；forx←x1tox2do{计算长方体的体积}fory←y1toy2doforz←z1toz2dosum←sum+map[x，y，z]；{调整最优解}ifsumbestthenbest←sum；这个算法相当粗糙，枚举状态的费用为O（n9）2、从减少重复计算入手记录先前考察的结果。在统计长方体2时，只