数学枚举法课件

根本算法——枚举法技术教研组谷方明1例如求满足表达式A+B=C的所有整数解，其中A，B，C为1~3之间的整数。例题分析此题非常简单，即枚举变量A,B,C的所有可能取值情况，对每种取值情况判断是否符合表达式即可。算法如下for(intA=1;A<=3;A++)for(intB=1;B<=3;B++)for(intB=1;B<=3;B++)if(A+B==C)输出A,B,C;枚举法的定义所谓枚举法，指的是从可能的解的集合中一一枚举各元素，用题目给定的检验条件判定哪些是无用的，哪些是有用的。能使命题成立的，即为解。例如中的解变量有3个：A，B，C。其中解变量A的可能取值范围A∈{1，…，3}解变量B的可能取值范围B∈{1，…，3}解变量C的可能取值范围C∈{1，…，3}从而问题的可能解有3*3*3=27个，可能解集：〔A，B，C〕∈{〔1，1，1〕，〔1，1，2〕，〔1，1，3〕，…，〔3，3，1〕，〔3，3，2〕，〔3，3，3〕}在上述可能解集中，满足题目给定的检验条件〔A+B==C〕的解元素，即为问题的解。枚举法的适用条件对于可能确定解的值域又一时找不到其他更好的算法时可以考虑枚举法。用枚举法求解的问题须满足两个条件能确定解变量〔枚举变量〕的个数n；每个解变量Ai〔1<=i<=n〕的可能值能确定范围且能连续取得。枚举法算法框架设解变量的个数是n,Ai1—解变量Ai的最小值；Aik—解变量Ai的最大值(1≤i≤n)，即A11≤A1≤A1k，Ai1≤Ai≤Aik，……，An1≤An≤Ank算法框架如下〔伪代码〕：forA1←A11toA1kdoforA2←A21toA2kdo……forAi←Ai1toAikdo……forAn←An1toAnkdoif状态(A1，…，Ai，…，An)满足检验条件then输出问题的解；枚举算法的特点及优化枚举法的特点是算法简单，但有时运算量大。优化枚举算法〔考察重点〕枚举算法的时间复杂度=状态总数*考察单个状态的耗时排除明显不属于解集的元素减少状态总数〔即减少枚举变量和枚举变量的值域〕降低单个状态的考察代价例如算法显然可以修改如下:for(intA=1;A<=3;A++)for(intB=1;B<=3;B++){C=A+B;if(C>=1)&&(C<=3)输出A,B,C;}通过变量的依赖关系减少了解变量的个数(局部枚举)，优化了枚举算法，n^3->n^2。枚举法解题的一般思路对命题建立正确的数学模型；根据命题确定的数学模型中各变量的变化范围〔即可能解集〕；利用循环语句、条件判断语句逐步求解或证明；每一步都可以考虑优化2例1巧妙填数将1～9这九个数字填入九个空格中。每一横行的三个数字组成一个三位数。如果要使第二行的三位数是第一行的两倍,第三行的三位数是第一行的三倍,应怎样填数。〔一共4组解，一组如以下图)此题目有9个格子，要求填数，如果不考虑问题给出的条件，共有9！=362880种方案，在这些方案中符合问题条件的即为解。因此可以采用枚举法。但仔细分析问题，显然第一行的数不会超过400，实际上只要确定第一行的数就可以根据条件算出其他两行的数了。这样仅需枚举400次。〔优化：解变量的依赖关系，也叫局部枚举〕例2谁是第几名在某次数学竞赛中,A、B、C、D、E五名学生被取为前五名。请据以下说法判断出他们的具体名次,即谁是第几名？条件1:你如果认为A,B,C,D,E就是这些人的第一至第五名的名次排列,便大错。因为:没猜对任何一个优胜者的名次。也没猜对任何一对名次相邻的学生。条件2:你如果按D,A,E,C,B来排列五人名次的话,其结果是:说对了其中两个人的名次。还猜中了两对名次相邻的学生的名次顺序。分析：此题是一个逻辑判断题，一般的逻辑判断题或推理题都采用枚举法进行解决。5个人的名次分别可以有5！=120种排列可能，因为120比较小，因此我们对每种情况进行枚举，然后根据条件判断哪些符合问题的要求。根据条件，A<>1,B<>2,C<>3,D<>4,E<>5,因此排除了一种可能性，只有4！=24种情况了。〔优化：减少了解变量的取值范围〕例3古纸残篇在一位数学家的藏书中夹有一张古旧的纸片。纸片上的字早已模糊不清了,只留下曾经写过字的痕迹,依稀还可以看出它是一个乘法算式,如图7所示。这个算式上原来的数字是什么呢？夹着这张纸片的书页上,“素数〞两个字被醒目的划了出来。难道说,这个算式与素数有什么关系吗？有人对此作了深入的研究,果然发现这个算式中的每一个数字都是素数,而且这样的算式是唯一的。请你也研究一番,并把这个算式写出来。***×**----------********----------*****分析：实际上，只要知道乘数和被乘数就可以写出乘法算式，所以我们可以枚举乘数与被乘数的每一位。然后再判断是不是满足条件即可。计算量是45=1024，对于计算机来说，计算量非常小。例4时钟问题〔IOI94-4〕九种时钟状态输入数据：读9个数码，这些数码给出了9个时钟时针的初始位置。数码与时刻的对应关系为：0——12点1——3点2——6点3——9点图中的例子对应以下输入数据：330222212输出数据：输出一个最短的移动序列〔数字序列〕，该序列要使所有的时钟指针指向12点，假设有等价的多个解，仅需给出其中一个.在我们的例子中，相应的OUTPUT.TXT的内容为：5849输入输出例如：INPUT.TXTOUTPUT.TXT3305489222212具体的移动方案如下图。我们分析一下表示时钟时针初始位置的数码j〔0≦j≦3〕与时刻的对应关系：0——12点1——3点2——6点3——9点移动方案选取与顺序无关。样例中，最正确移动序列为5849，同样4589序列也可到达目标。因此，求解过程中可以直接选取序列中从小至大排列的移动序列即可。(优化：用顺序减少解集的元素)每移动一次，时针将顺时针旋转90度。由此我们可以得出：对于任意一个时钟i〔1≦i≦9〕来说，从初始位置j出发至少需要Ci=〔4-j〕%4次操作，才能使得时针指向12点。而对每种移动方法要么不采用，要么采用1次、2次或3次，因为操作四次以后，时钟将重复以前状态。因此，9种旋转方案最多产生49个状态。〔优化：用次数减少解集的元素〕设pi表示第i种旋转方法的使用次数〔0≦pi≦3，1≦i≦9〕。那么可能的解的集合为{〔P1，P2，……，P9〕}，该集合共含49个状态。从题目的示意图中，我们可以分析出9个时钟分别被哪些方法所控制，见下表：建立时钟控制表设计算法因此我们可以设计如下枚举算法(伪代码)：

forp1<-0to3do forp2<-0to3do.........forp9<-0to3do

ifc1满足时钟1andc2满足时钟2and...andc9满足时钟9then

打印解路径；显然，上述枚举算法枚举了所有49=262144个状态，运算量和运行时间颇大。优化P4~P9可直接由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); P9=order(C6-P3-P5-P6); P8=order(C8-P5-P7-P9);结果然后将P1，P2，…，P9代入下述三个检验条件C5=(P1+P3+P5+P7+P9)mod4C7=(P4+P7+P8)mod4C9=(P6+P8+P9)mod4上述局部枚举的方法〔枚举状态数为43个〕比较全部枚举的方法〔枚举状态数为49个〕来说，由于大幅度削减了枚举量，减少运算次数，因此其时效显著改善〔优化：依赖关系〕例5最正确游览线路〔NOI94〕某旅游区的街道成网格状。其中东西向的街道都是旅游街，南北向的街道都是林荫道。由于游客众多，旅游街被规定为单行道，游客在旅游街上只能从西向东走，在林阴道上那么既可从南向北走，也可以从北向南走。阿龙想到这个旅游区游玩。他的好友阿福给了他一些建议，用分值表示所有旅游街相邻两个路口之间的街道值得游览的程度，分值时从-100到100的整数，所有林阴道不打分。所有分值不可能全是负分。以下图是被打过分的某旅游区的街道图。阿龙可以从任一个路口开始游览，在任一个路口结束游览。请写一个程序，帮助阿龙找一条最正确的游览线路，使得这条线路的所有分值总和最大。图11某旅游区街道示例图输入数据：输入文件是INPUT.TXT。文件的第一行是两个整数M和N，之间用一个空格符隔开，M表示有多少条旅游街〔1≦M≦100〕，N表示有多少条林阴道〔1≦M≦20001〕。接下来的M行依次给出了由北向南每条旅游街的分值信息。每行有N-1个整数，依次表示了自西向东旅游街每一小段的分值。同一行相邻两个数之间用一个空格隔开。输出数据：输出文件是OUTPUT.TXT。文件只有一行，是一个整数，表示你的程序找到的最正确游览线路的总分值。输入输出例如：INPUT.TXTOUTPUT.TXT3684-50–4736–30–2317–19–34–13–8-42–3–4334–45INPUT.TXTOUTPUT.TXT3684-50–4736–30–2317–19–34–13–8-42–3–4334–45分析：设Lij为第I条旅游街上自西向东第J段的分值〔1≦I≦M，1≦J≦N–1〕。例如样例中L12=17，L23=-34，L34=34。我们将网格状的旅游区街道以林荫道为界分为N–1个段，每一段由M条旅游街的对应段成，即第J段成为{L1J，L2J，……，LMJ}〔1≦J≦N–1〕。由于游览方向规定横向自西向东，纵向即可沿林阴道由南向北，亦可由北向南，而横行的街段有分值，纵行无分值，因此最正确游览路现必须具备如下三个特征：来自假设干个连续的段，每一个段中取一个分值；每一个分值是所在段中最大的；起点段和终点段任意，但途经段的分值和最大。设Li为第I个段中的分值最大的段。即Li=Max{L1I，L2I，……，LMI}〔1≦I≦N–1〕。例如对于样例数据：L1=Max〔-50，17，-42〕=17；L2=Max〔-47，-19，-3〕=-3；L3=Max〔36，-34，-43〕=36；L4=Max〔-30，-13，34〕=34；L5=Max〔-23，-8，-45〕=-8；有了以上的根底，我们便可以通过图示描述解题过程，见求解过程例如图

我们把将段设为顶点，所在段的最大分值设为顶点的权，各顶点按自西向东的顺序相连，组成一条游览路线。显然，如果确定西端为起点、东段为终点，那么这条游览路线的总分值最大。图12求解过程示例图我们把将段设为顶点，所在段的最大分值设为顶点的权，各顶点按自西向东的顺序相连，组成一条游览路线。显然，如果确定西端为起点、东段为终点，那么这条游览路线的总分值最大。问题是某些段的最大分值可能是负值，而最优游览路线的起点和终点任意，在这种情况下，上述游览路线就不一定最正确了。因此，我们只能枚举这条游览路线的所有可能的子路线，从中找出一条子路线II+1……J〔1≦I<J≦N–1〕，使得经过顶点的权和LI+LI+1+……+LJ最大。设Best为最正确游览路线的总分值，初始时为0；Sum为当前游览路线的总分值。我们可以得到如下算法(伪代码)：Best<-0;Sum<-0;forI<-1toN–2doforJ<-I+1toN–1dobeginSum<-LI+……+LJ;ifSum>BestthenBest:=Sum;end优化显然，这个算法的时间复杂度为O〔N2〕。而N在1~20001之间，时间复杂度比较高。于是，我们必须对这个算法进行优化。仍然从顶点1开始枚举最优路线。假设当前子路线延伸至顶点I时发现总分值Sum≦0，那么应放弃当前子路线。因为无论LI+1为何值，当前子路线延伸至顶点I+1后的总分值不会大于LI+1。因此应该从顶点I+1开始重新考虑新的一条子路线。通过这种优化，可以使得算法的时间复杂度降到了O〔N〕。优化后的算法描述如下:Best<-0;Sum<-0;forI<-1toN–1dobeginSum<-Sum+LI;ifSum>BestthenBest<-Sum;ifSum<0thenSum<-0;end3小结枚举方法是最简单的一种解题策略，也是最容易想到的一种方法。利用枚举法解题需要枚举出问题的解的所有可能状态，其致命的弱点便在于枚举量太大，从而导致算法效率十分低下。因此，在利用枚举法解题时，尽可能地减少枚举量，提高枚举效率。通过对问题的分析，挖掘出问题的隐含条件，尽可能排除那些明显不可能属于问题的解的状态，就是一个行之有效的方法。4二进制数的分类〔课后练习〕假设将一个正整数转化为二进制数后，1的个数多于0的个数的这类数称为A类数，否那么称为B类数。例如：〔13〕10=〔1101〕2，13为A类数；〔10〕10=〔1010〕210为B类数；〔24〕10=〔11000〕224为B类数；程序要求：求出1～1000之中〔包括1与1000〕，全部A、B两类数的个数。分析：此题是一道统计类题目。解决统计问题的一个常用方法是枚举法：逐一枚举所有情况，同时进行统计，枚举结束时，统计也完成，得到结果。具体对此题而言，采用枚举法的正确性与可行性是显然的，而此题的数据规模又仅为1～1000，所以采用逐一枚举方法进行统计的时间复杂度是完全可以接受的。模式识别的“中心〞问题〔课后练习〕实数矩阵由m行n列组成(1<=m，n<=100)，现给定实数矩阵，求其中心，假设有多个“中心〞，给出任意一个“中心〞即可。中心(i，j)是使第i行上边元素(不包括第i行)的总和与第i行下边元素(不包括第i行)的总和之差的绝对值最小，而且第j列左边元素(不包括第j列)的总和与第j列右边元素(不包括第j列)的总和之差的绝对值最小。分析：求矩阵的中心，即确定矩阵中心的行和列坐标，考虑到矩阵的对性，行坐标和列坐标的求法是类同的。下面是求矩阵中心行坐标的算法。求行坐标采用枚举法，枚举出所有可能的行坐标line，计算出line行上边元素和与下边元素和之差的绝对值difference，difference最小的行即为中心所在行。枚举过程可以描述为〔伪代码〕：min<-+∞;forline<-1tomdobegin求出line行上、下元素绝对值之差difference;ifmin>differencethenbeginmin<-difference;保存line作为矩阵中心所在行；end；end；留学生〔课后练习〕来自不同国家的四位留学生A,B,C,D在一起交谈,他们只会中、英、法、日四种语言中的2种,情况