基础算法(枚举、贪心、分治策略)

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,基础算法策略,长沙市第一中学,曹利国,第一部分,枚举策略,枚举策略的基本思想,枚举法，又称穷举法，指在一个有穷的可能的解的集合中，一一枚举出集合中的每一个元素，用题目给定的检验条件来判断该元素是否符合条件，若满足条件，则该元素即为问题的一个解；否则，该元素就不是该问题的解。,枚举策略的基本思想,枚举方法也是一种搜索算法，即对问题的所有可能解的状态集合进行一次扫描或遍历。在具体的程序实现过程中，可以通过循环和条件判断语句来完成。,枚举法常用于解决,“,是否存在,”,或,“,有多少种可能,”,等类型的问题。例如，求解不定方程的问题就可以采用列举法。,虽然枚举法本质上属于搜索策略，但是它与回溯法有所不同。因为适用枚举法求解的问题必须满足两个条件： 可预先确定每个状态的元素个数,n,；,状态元素,a,1,，,a,2,，,，,a,n,的可能值为一个连续的值域。,设,a,i1,状态元素,a,i,的最小值；,a,ik,状态元素,a,i,的最大值,(1in),，即,a,11,a,1,a,1k,，,a,21,a,2,a,2k,，,a,i1,a,i,a,ik,，,，,a,n1,a,n,a,nk,for a,1,a,11,to a,1k,do,fo a,2,a,21,to a,2k,do ,for a,i,a,i1,to a,ik,do ,for a,n,a,n1,to a,nk,do,if,状态,(a,1,，,，,a,i,，,，,a,n,),满足检验条件,then,输出问题的解；,枚举策略的基本思想,枚举法的特点是算法比较简单，在用枚举法设计算法时，重点注意优化，减少运算工作量。将与问题有关的知识条理化、完备化、系统化，从中找出规律，减少枚举量。,枚举方法的优化,枚举算法的时间复杂度：状态总数*单个状态的耗时,主要优化方法：, 减少状态总数, 降低单个状态的考察代价,优化过程从以下几个方面考虑：, 枚举对象的选取, 枚举方法的确定,采用局部枚举或引进其他算法,枚举算法的应用,例题,1,：二进制数的分类,若将一个正整数转化为二进制数后，,0,的个数多于,1,的个数的这类数称为,A,类数，否则称为,B,类数。例如：,（,13,）,10=,（,1101,）,2,，,13,为,B,类数；,（,10,）,10=,（,1010,）,2 10,为,B,类数；,（,24,）,10=,（,11000,）,2 24,为,A,类数；,程序要求：求出,1,1000,之中（包括,1,与,1000,），全部,A,、,B,两类数的个数。,【,分析,】,此题是一道统计类题目。解决统计问题的一个常用方法是枚举法：逐一枚举所有情况，同时进行统计，枚举结束时，统计也完成，得到结果。,具体对本题而言，采用枚举法的正确性与可行性是显然的，而本题的数据规模又仅为,1,1000,，所以采用逐一枚举方法进行统计的时间复杂度是完全可以接受的。,枚举算法的应用,例题,2,：,01,统计,例题,4,：圆桌骑士（,IOI,试题）,在一个,8*8,的棋盘上，有一个国王和若干个武士。其中，国王走一字步，骑士走马步。若国王与骑士相会在同一点上，国王可以选择让骑士背他走。求一个点，使所有的骑士和国王相距在这个点上的所走的步数最少。,枚举算法的应用,【,分析,】,此题可从,3,个方面考虑：,分治、枚举、数学方法。,由于无法将这个问题划分为各自独立的小问题来解决，分治显然是不行的。又因武士和国王位置的不固定性和其走法的差异，推导不出一个数学公式。因此考虑使用枚举，需要枚举的三个要点：,1,、最后的汇聚点。,2,、国王与背他的骑士的汇聚点。,3,、国王与背他的骑士。,枚举算法的应用,国王最多只会与一个骑士结合，因为骑士的最终目标也是最终汇聚点，一旦国王与某个骑士汇合后，即马上可与其结合，剩下的只需要将所有的骑士汇合就可以了。更没有必要在中途中有将国王托付给其他的骑士。 这样我们估算一下时间为,O,（,8*8*8*8*63,）,=O,（,36*104,），完全可以承受。,另外，我们需要预先将,2,点之间走马字步的距离计算出来。可以使用,Floyd,或是,Bfs,。,枚举算法的应用,算法流程：,disx1,，,y1,，,x2,，,y2-,（,x1,，,y1,）（,x2,，,y2,）之间的距离。,For I,：,=1 to 8 do,枚举汇合点,For j,：,=1 to 8 do begin,All,：,=,所有骑士到这一点的和；,Best:=min(best,all+,国王到汇聚点的步数,),For x,：,=1 to 8 do ,枚举武士国王的相会点,For y,：,=1 to 8 do begin,For kk,：,=1 to k do ,枚举与国王结合的武士,If disknightkk.x,knightkk.y,x,ymin then begin,Min:= disknightkk.x,knightkk.y,x,y;,Mink:=k;,End;,End,；,Now:= all-mink,武士走到汇合点的距离,+ mink,武士走到汇聚点的距离,+,国王走到汇聚点的距离,+,从汇聚点到汇合点的距离；,Best,：,=min,（,best,，,now,）,End,；,局部枚举,例题,5,：求第一、第二、第三最短路问题,局部枚举,例题,6,：新年好,重庆城里有,n,个车站，,m,条双向公路连接其中的某些车站。每两个车站最多用一条公路直接相连，从任何一个车站出发都可以经过一条或多条公路到达其他车站，但不同的路径需要花费的时间可能不同。在一条路上花费的时间等于路径上所有公路需要的时间之和。,佳佳的家在车站,1,，他有五个亲戚，分别住在车站,a,b,c,d,e,。过年了，他需要从自己的家出发，拜访每个亲戚（顺序任意），给他们送去节日的祝福。怎样走，才需要最少的时间？,分析,这一题中的边数远小于,n2,，所以复杂度也只有,nlogn+m,算法框架是：,（,1,）用,5,次最短路，计算出,6,个点两两之间的距离,（,2,）枚举,5,个结点的全排列，找到一个使得总路程长度最短的方案。,最大子矩阵的求解方法,第二部分,贪心方法,贪心方法的基本思想,贪心是一种解题策略，也是一种解题思想,使用贪心方法需要注意局部最优与全局最优的关系，选择当前状态的局部最优并不一定能推导出问题的全局最优,利用贪心策略解题，需要解决两个问题：,该题是否适合于用贪心策略求解,如何选择贪心标准，以得到问题的最优解,适用于贪心策略求解的问题的特点,适用于贪心策略求解的问题必须具有最优子结构的性质，但并不是所有,具有,最优子结构的问题都可以用贪心策略求解。因为贪心往往是盲目的，需要使用更理性的方法,动态规划（例如,“,0-1,背包问题,”,与,“,部分背包问题,”,）,贪心方法的应用,例题,1,：节点网络。,现有一个,N,！个节点的网络，每个节点的编号都是编号（,A,1,A,2,A,3,A,N,）序列的一个置换。对于任意两个节点,S,和,T,，如果,T,的编号是由,S,编号的首位与除首位外的编号中任一位交换所得 ，则,S,和,T,之间有一条边，求从给定节点,S,走到节点（,A,1,A,2,A,3,A,N,）所需经过的最少边数。其中，,n,100,。,贪心方法的应用,例如,n=3,的情况：,(A,1,A,2,A,3,),(A,1,A,3,A,2,),(A,2,A,3,A,1,),(A,2,A,1,A,3,),(A,3,A,1,A,2,),(A,3,A,2,A,1,),贪心方法的应用,【,分析,】,从题意表面上看，本题是一个求最短路径的问题，但题设中的,N,100,，也就是说图中最多有,100,！个节点，采用二维关系的图结构根本无法存贮这众多的状态。通过问题的本质分析，可以将问题转化为一个序列的最优转化问题。,贪心方法的应用,采用,贪心策略,：,每次让一个节点归位或为下一步工作做准备。,其具体步骤为：,若序列中第一个点为,A,x,(x,1),，则将第一个点和第,x,个点交换。这便完成了让一个点归位的工作；,若第一个是,A,1,，则任找一个编号与位置不相符的点，并与之交换。这样下一步便可让交换到,1,号位置的点归位。,贪心方法,的应用,(A,3,A,4,A,1,A,2,),(A,1,A,4,A,3,A,2,),第一个点,A,1,已归位，但第二个点为,A,4,A,2,，将第,2,个点,A,4,与,A,1,交换,第一个点为,A,3,A,1,，将第,3,个点,A,1,与,A,3,交换,(A,4,A,1,A,3,A,2,),第一个点为,A,4,A,1,，将第,4,个点,A,2,与,A,4,交换,(A,2,A,1,A,3,A,4,),第一个点为,A,2,A,1,，将第,2,个点,A,1,与,A,2,交换,(A,1,A,2,A,3,A,4,),已经符合要求了,一共经过,4,步完成。,下面看一个,n=4,，初始序列为,(A,3,A,4,A,1,A,2,),的推演过程：,贪心方法的应用,例题,2,：,d-,规则问题。,对任意给定的,m(mN,+,),和,n(nN,+,),，满足,m1,，使得,K,aP,，则修改,P,为：,P=P-y|y=s,a,sN,+,，并称该,d,规则具有分值,a,。现要求编制一个程序，对输入的,m,n,值，构造相应的初始集合,P,，对,P,每应用一次,d,规则就累加其相应的分值，求能得到最大累加分值的,d,规则序列，输出每次使用,d,规则时的分值和集合,p,的变化过程。,贪心方法的应用,【,分析,】,初看这一问题，很容易想到用贪心策略来求解，即选择集合中最大的可以删除的数开始删起，直到不能再删除为止，而且通过一些简单的例子来验证，这一贪心标准似乎也是正确的，例如，当,m=3,，,n=10,时，集合,P,3,10,，运用上述“贪心标准”可以得到这一问题的正确的最优解,d=5,4,3,12,，即其,d-,规则过程如下：,1.,a=5 P=3,4,6,7,8,9d=5,2.,a=4 P=3,6,7,9d=5+4=9,3.,a=3 p=7 d=5+4+3=12,贪心方法的应用,但是，如果再仔细地分析一个例子，当,m=3,，,n,18,时，如果还是使用上述“贪心标准”，则得到问题的,d-,规则总分为,d=35,，其,d-,规则序列为（,9,8,7,6,5,），而实际上可以得到最大,d-,规则总分为,d,38,，其对应的,d-,规则序列为（,9,8,7,6,3,5,）。,为什么会出现这样的反例呢？这是因为，问题中要使得,d-,规则总分,d,值越大，不光是要求每一个,d,分值越大越好，也要求取得的,d,分值越多越好。,因此，本题,不能,采用纯粹的贪心策略求解。,贪心方法的应用,【,改进,】,将原算法基础上进行改进。下面给出新的算法：,建立集合,P=m.n,从,n div 2,到,m,每数构造一个集合,ci,，包含该数在,P,中的所有倍数（不包括,i,本身）,从,n div 2,起找到第一个元素个数最少但又不为空的集合,ci,在,d,分值中加上,i,把,i,及,ci,集合从,P,集中删除，更新所有构造集合的元素,检查所有构造集合，若还有非空集合，则继续,3,步骤，否则打印、结束,贪心方法的应用,下面看,m=3, n=18,时的推演过程：,初始,P=3.18,找到,i=9, ci=18, P=3.8,10.17,找到,i=8, ci=16, P=3.7,10.15,17,找到,i=7, ci=14, P=3.6,10.13,15,17,找到,i=6, ci=12, P=3.5,10,11,13,15,17,找到,i=3, ci=15, P=4,5,10,11,13,17,找到,i=5, ci=10, P=4,11,13,17,到此所有构造集合全部为空，,d=9+8+7+6+3+5=38,贪心方法的应用,讨论,：,能否证明此贪心策略是正确的？,能否找到其他更好的算法？,贪心方法的应用,例题,3,：射击竞赛,射击的目标是一个由,R,C(2,R,C,1000),个小方格组成的矩形网格。每一列恰有,2,个白色的小方格和,R-2,个黑色的小方格。行从顶至底编号为,1R,，列从左至右编号为,1C,。射击者可射击,C,次。,在连续的,C,次射击中，若每列恰好有一个白色的方格被射中，且不存在无白色方格被射中的行，这样的射击才是正确的。,如果存在正确的射击方法，则要求找到它。,贪心方法的应用,射击的选择有,2,C,种，符合要求的却很少。要解决问题，还需从正确的射击方法的特征入手。,贪心方法的应用,【,方法一,】,网络流算法,我们将表示列的点编号为,1,到,C,，表示行的点编号为,C+1,到,C+R,，如果一个白色方格处在第,i,行第,j,列，那么从点,j,向点,C+i,连一条弧，弧的容量为,1,。再增设一个源点,S,，从点,S,往点,1,到,C,间各连一条弧，弧的容量为,1,，又设一个汇点,T,，从点,C+1,到点,C+R,向汇点,T,连一条弧，弧的容量为,1,，那么从源点,S,到汇点,T,求最大流，求出的最大流量即为最多可以射击到的行数。各条流的路线则描述了具体的射击方案。,可以看出，如果用网络流求出的最大流量比,R,小，则问题无解，否则我们可以先根据网络流的结果求出该二分图的具体匹配方案。,贪心方法的应用,红色,的连线流量为,1,蓝色,的连线流量为,0,选择的射击格即为：,(1,3), (2,1), (3,2), (4,4),S,2,1,4,3,2,1,4,3,T,列,:,行,:,源,:,汇,:,贪心方法的应用,网络流算法经过优化，时间复杂度可以达到,O,(,C,(,n,+,4C,+,4R,),上述网络流算法虽然可以通过全部数据，但编程复杂度很高，而且极易出错，一不小心就会因为一个小错误影响整个程序。,贪心方法的应用,【,方法二,】,贪心方法,统计所有行包含的白格数,从还没有射击格的行中选出一个白格数最少的,检查所选的行,若所选行的白格数为,0,，则输出无解；,否则从所选行的白格中任选一个作为射击格，并将与该格同列的另一个白格所处行的白格数减,1,返回到第,2,步，直到所有的行都有射击格。,若还有列没有选射击格，则在该列任选一白格作为射击格即可,贪心方法的应用,上面的贪心方法非常高效：,时间复杂度为,O,(,R,C,),，如果在程序中使用堆优化，时间复杂度将降为,O,(,R,log,2,C,),。空间复杂度是线性的，而且非常容易实现。,现在关键的问题就是,如何证明它的正确性？,贪心方法的应用,【,证明,】,用,hi,表示第,i,行的白格数。如果最开始的时候：,minhi=0:,第,i,行已经没有办法找到可作为射击格的白格，那么问题只能无解。,minhi=1:,那么第,i,行的这一个白格必须要作为射击格，否则将因第,i,行没有射击格而造成问题无解。,minhi,2:,那么在这一行任选一个白格，顶多只会造成剩余行中有一行,h,值为,1,，再处理那一行，最多也只会再造成剩余行中有一行,h,值为,1,，如此往复，将保持,h,值为,1,的行数不超过,1,行，最后最坏的情况也是造成最后一行的,h,值为,1,，继续下去所有行就都已选取了射击格了。,因此，如果原问题有解，该贪心方法一定能找到一种正确的方案。,由此可以证明，此贪心方法是正确的。,贪心方法的应用,例题,4,：,Transversal,有一个,(2n+1),(2n+1),的矩阵，每个单元格中有符号,“,+,”,或,“,-,”,。,定义一种取反操作：将,1,至,2n+1,这,2n+1,个整数任意排列，得到序列,A,1,A,2,A,2n+1,，然后将,(1,A,1,),(2,A,2,),(2n+1,A,2n+1,),这,2n+1,个单元格中的符号取反。,求一种操作组合，使得在完成求得的操作组合后，表中,“,+,”,的个数不超过,2n,个。,(n20),+,+,+,+,+,-,-,+,-,贪心方法的应用,一种操作组合：,(1,1), (2,2), (3,3),(1,2), (2,3), (3,1),(1,1), (2,3), (3,2),(1,3), (2,1), (3,2),红色,符号为上一次取反操作后的结果,+,-,+,-,+,+,+,+,+,-,-,+,-,-,+,+,+,-,-,-,-,+,-,+,+,-,-,-,-,-,-,-,-,-,-,+,-,+,-,-,-,+,+,-,+,仅剩一个“,+”,。,贪心方法的应用,讨论：,是否可以用贪心法解决此题？,贪心方法的推广,贪心与其它算法结合,搜索的最优化剪枝（,生日蛋糕）,优化动态规划（,Peter,的快餐店）,贪心方法与解题策略,最优方法不一定是最好方法,想不到最优解法就用较优解法,贪心与其它算法结合,例题,5,：,Peter,的快餐店,（贪心与动态规划）,Peter,最近在,R,市新开了一家快餐店。 该快餐店准备推出一种套餐，每套由,A,个汉堡、,B,个薯条和,C,个饮料组成。为了提高产量，,Peter,引进了,N,条生产线。所有生产线都可以生产汉堡、薯条和饮料，由于每条生产线一天能工作的时间是有限的、不同的，而汉堡、薯条和饮料的单位生产时间又不同，,Peter,需要知道，怎样安排才能是一天中生产的套餐量最大。假设一天中汉堡、薯条和饮料的产量均不超过,100,个，且生产线总数小于等于,10,。,贪心与其它算法结合,【,分析,】,用,p1,、,p2,、,p3,分别表示汉堡、薯条和饮料的单位生产时间，,ti,表示第,i,条生产线每天的生产时间，,pi,j,k,表示用前,i,条生产线生产,j,个汉堡、,k,个薯条的情况下，最多能生产的饮料数，,ri,j,k,表示用第,i,条生产线生产,j,个汉堡、,k,个薯条的情况下，最多能生产的饮料数，则,pi,j,k=maxpi-1,j1,k1+ri,j-j1,k-k1,(j-j1),p1+(k-k1),p2ti),通过对该算法的时间复杂度分析，最坏的情况下时间复杂度将达到,10,9,，是相当费时的。,贪心与其它算法结合,现在加入,贪心方法,，用贪心方法作预处理,：,首先计算出一天生产套数的上限值：,min100 div A,100 div B,100 div C,接着，用贪心方法计算出这,N,条生产线可以生产的套数，并与上限比较，大于或等于则输出上限值并退出，否则再调用动态规划。因为贪心方法的代价很低，这里甚至可以使用多次贪心标准不同的贪心方法，取其最大值。,在运行动态规划的过程中，也可以每完成一阶段工作便与上限值进行比较，将贪心思想充分融入到动态规划过程中，这样以来，便可望在动态规划完成前提前结束程序。,贪心方法小结,贪心作为一种解题思路，虽然有时无法证明它的正确性，但在无法找到其他算法的时候，不失为一种好方法。并且，贪心与其他算法的结合，可以对其他算法起到优化作用。,第三部分,归纳策略,归纳法的基本思想,归纳法的基本思想是通过列举少量的特殊情况，经过分析，最后找出一般的关系。从本质上讲，归纳就是通过观察一些简单而特殊的情况，最后总结出有用的结论或解决问题的有效途径。,归纳法解题,的过程,细心的观察；,丰富的联想；,继续尝试；,总结归纳出结论。,归纳法解题,的过程,归纳是,种抽象，即从特殊现象中找出一般关系。由于在归纳的过程中不可能对所有的可能情况进行枚举，因而最后得到的结论还只是一种猜测,(,即归纳假设,),。所以，严格说来对于归纳假设还必须加以严格的证明。,归纳策略解题应注意的问题：,从问题的简单具体状态分析入手，目的是去寻求可以推广的一般性规律，因此应考虑简单状态与一般性状态之间的联系。,从简单状态中分析出来的规律特征应能够被验证是正确的，不能想当然或任意地提出猜想，否则归纳出来的结论是错误的，必然导致整个问题的解是错解。,归纳策略的应用,例题,1,：,求前,n,个自然数的平方之和：,S=1,2,+2,2,+3,2,+,+n,2,归纳策略的应用,【,分析,】,这本是一道很简单的题目，但如果能找出,S,值与,n,的关系，则此题将更进一步得到简化，由数学证明得知：,(1,2,+2,2,+3,2,+,+n,2,)/(1+2+3+,+n) =(2n+1)/3,又由于,1+2+3+,+n=n(n+1)/2,，因此得到：,1,2,+2,2,+3,2,+,+n,2,=n(n+1) (2n+1)/6,但这只是通过总结归纳而得到的一种猜测，是否正确还需证明，对归纳假设的证明通常采用数学归纳法（证略）。,归纳策略的应用,例题,2,：若干个正整数之和为,n,，其中：,n1,，因此排除了,n3,和,n4,存在的可能性,.,又由于,n,和,m,是整数，因此,1,和,2,应为整数。,由于,m,2,n,2,单调递增，从,m,k,出发，按递减方向将,m,值代入,n,的求根公式。,只要,1,（或,2,）为整数、,n1,（或,n2,）为整数且小于,k,，则得出的一组,m,和,n,一定使,m2,n2,的值最大。,【,算法描述,】,mk,；,while mi do begin,求,1,if 1,为整数,then begin,求,n1,；,if (n1,为整数,) and (n1k),Then begin,输出,m,和,n1,；,halt; end,end;,then,求,2,；,if 2,为整数,then begin,求,n2,；,if,（,n2,为整数）,and,（,n2k,）,then begin,输出,m,和,n2; halt; end,end;then,mm,l;,end;while,归纳策略的应用,上述算法从数学意义上来说，是一定可以出得出正确解的。但是该算法疏漏了一个重要条件 ,1k10,9,。如果,K,值超过,10,5,，上述算法不可能在限定的,15,秒内出解。,归纳策略的应用,【,分析,】,方法二,分析小数据会发现：,m,n,是,Fibonacci,数列的相邻两项。,因为： （,n,2,mn,m,2,）,2,1,故： （,m,2,+ mn,n,2,）,2,1,又：,m,2,mn,n,2,(m,n),2,mn,2n,2,(m,n),2,(m,n)n,n,2,故： （,m,2,mn,n,2,）,2,(m,n),2,(m,n)n,n,2,2,即： （,n,2,mn,m,2,）,2,(m,n),2,(m,n)n,n,2,2,归纳策略的应用,【,分析,】,由上述数学变换式可以得出，如果,m,和,n,为一组满足条件和条件的解，设,n,m,n,，,m,n,那么,n,，,m,也是一组满足条件和条件的一组解。,将所有满足条件和条件的,m,和,n,按递增顺序排成一个,Fibomacci,数列 ,1,，,1,，,2,，,3,，,5,，,8,，,数列中小于,k,的最大两个相邻数即为试题所要求的一组,m,和,n,。,算法,：,利用,Fibomacci,数列顺推,m,n,，求出在条件范围内的,m,n,最大值，此时,m,2,n,2,的值最大。,归纳策略的应用,例题,4,：,“,王,”,棋子遍历问题。,题目大意：在,nn,格（,2,n=20,）棋盘上的任一格子中放置一个棋子，棋子每次只能往其上、下、左、右相邻方格移动一步，求一种遍历方法，使得棋子走,n,2,-1,步遍历整个棋盘，每个方格只能被访问一次。,归纳策略的应用,【,分析,】,此题很容易想到采用搜索回溯的方法去求解，即从起点位置出发，扩展其相邻四个方格的状态节点，生成一个状态树，利用深度搜索的方法求解，但这种纯搜索的方法效率太低，因此可以考虑一些简单的情况时的遍历方法：,归纳策略的应用,【,分析,】,当,n=2,时，该棋盘存在一条回路，所以任意一点作为起点均能遍历整个棋盘，考虑到当,n=4,6,时的情况，进而推广到,n,为偶数时，均可以按规律产生回路，从给定的起点开始沿着该回路均可遍历整个棋盘。,归纳策略的应用,【,分析,】,再考虑,n,为奇数时的情况，先设定,n=3,时，棋盘可划分成,5,个白格和,4,个黑格，人工可以推出，从任一黑格出发将无法遍历整个棋盘，然后考虑,n=5,时的情况，同样可推出，从棋盘中的任一黑格出发无法遍历整个棋盘。,规律,：,当,n,为奇数时，棋子的起始位置若满足其横坐标和纵坐标之和为奇数时（即图中所示的任一黑格位置），问题将无解。,归纳策略的应用,这一规律很容易能够得到验证,因为按照规则，从任一黑格出发，必走一白格再走一黑格，所以白格数目与黑格数目应相等，而图中两者数目并不相等，如,n=5,时，图中共有黑格,12,个，白格共有,13,个。,归纳策略的应用,【,总结,】,通过上述归纳，我们在搜索求解问题时，将会较大地提高算法效率，尤其是在一些问题的无解判定时，运用归纳策略的作用将会十分明显。,归纳策略的应用,例题,5,：,Kathy,函数,(HNCOI),Tiger,非常喜欢数学，所以他参加了学校组织的数学课外兴趣小组。在兴趣小组的学习当中，老师向,Tiger,介绍了,Kathy,函数，,Kathy,函数是这样定义的：,归纳策略的应用,例题,5,：,Kathy,函数,(HNCOI),Tiger,对,Kathy,函数产生了浓厚的兴趣，他通过研究发现有很多的数,n,都满足,对于一个给定的数,m,，他希望你求出所有的满足 的自然数,n,的个数，其中,m8 then begin,分解成四小块；,对于其中一块,devide(n-3),end,else,case n of,6:,按,n=6,分割；,7:,按,n=7,分割；,8:,按,n=8,分割；,end;,End;,分治思想,如果在将规模为,n,的问题分成,k,个不同子集合的情况下，能得到,k,个不同的可分别求解的子问题，其中,1,k,=n,，而且在求出了这些子问题的解之后，还可找到适当的方法把它们合并成整个问题的解，那么，具备上述特性的问题可考虑使用分治策略设计求解。这种设计求解的思想就是将整个问题分成若干个小问题后分而治之。,分治思想,分治,(divide-and-conquer),就是,“,分而治之,”,的意思，其实质就是将原问题分成,n,个规模较小而结构与原问题相似的子问题；然后递归地解这些子问题，最后合并其结果就得到原问题的解。其三个步骤如下；,分解,(Divide),：将原问题分成一系列子问题。,解决,(Conquer),：递归地解各子问题。若子问题足够小，则可直接求解。,合并,(combine),；将子问题的结果合并成原问题的解。,分治思想,问题,S,问题,S,问题,S,S,的解,问题,S1,问题,S,2,问题,S,i,问题,Sn,S,1,的解,S,2,的解,S,i,的解,S,n,的解,问题的分解,子集解的合并,子问题求解,分治思想,由分治法所得到的子问题与原问题具有相同的类型。如果得到的子问题相对来说还太大，则可反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生出不用进一步细分就可求解的子问题。分治求解可用一个递归过程来表示。,要使分治算法效率高，关键在于如何分割？一般地，出于一种平衡原则，总是把大问题分成,K,个规模尽可能相等的子问题，但也有例外，如求表的最大最小元问题的算法，当,n,6,时，等分定量成两个规模为,3,的子表,L1,和,L2,不是最佳分割。,分治的应用举例,例题,2,：,一元三次方程求解,有形如：,ax3+bx2+cx+d=0,这样的一个一元三次方程。给出该方程中各项的系数,(a,，,b,，,c,，,d,均为实数,),，并约定该方程存在三个不同实根,(,根的范围在,-100,至,100,之间,),，且根与根之差的绝对值,=1,。要求由小到大依次在同一行输出这三个实根,(,根与根之间留有空格,),，并精确到小数点后,4,位。,提示：记方程,f(x)=ax3+bx2+cx+d,，若存在,2,个数,x1,和,x2,，且,x1x2,，,f(x1)*f(x2)0,，则在,(x1,，,x2),之间一定有一个根。,样例,输入：,1 -5 -4 20,输出：,-2.00 2.00 5.00,分治的应用举例,如果精确到小数点后两位，可用简单的枚举法：将,x,从,-100.00,到,100.00,（步长,0.01,） 逐一枚举，得到,20000,个,f(x),，取其值与,0,最接近的三个,f(x),，对应的,x,即为答案。而题目已改成精度为小数点后,4,位，枚举算法时间复杂度将达不到要求。,直接使用求根公式，极为复杂。加上本题的提示给我们以启迪：采用二分法逐渐缩小根的范围，从而得到根的某精度的数值。,具体方法如下：,分治的应用举例,A,、当已知区间,(a,b),内有一个根时，用二分法求根，若区间,(a,b),内有根，则必有,f(a),f(b)b,或,f(a+b)/2)=0,，则可确定根为,(a+b)/2,并退出过程；,(2),若,f(a)* f(a+b)/2)0,，则必然有,f(a+b)/2)* f(b)=1,。因此可知：在,-100,-99,、,-99,-98,、,、,99,，,100,、,100,，,100,这,201,个区间内，每个区间内至多只能有一个根。即：除区间,100,，,100,外，其余区间,a,a+1,，只有当,f(a)=0,或,f(a),f(a+1)0,时，方程在此区间内才有解。若,f(a)=0,，解即为,a,；若,f(a),f(a+1)0,，则可以利用,A,中所述的二分法迅速出找出解。,如此可求出方程的所有的解。,分治的应用举例,例题,3,：,旅行家的预算,一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市,（假设出发时油箱是空的）。给定两个城市之间的距离,D1,、汽车,油箱的容量,C,（以升为单位）每升汽油能行驶的距离,D2,、出发点,每升汽油价格,P,和沿途油站数,N,（,N,可以为零），油站,i,离出发点的,距离,Di,、每升汽油价格,Pi,（,i,l,，,2,，,.N,）。 计算结果四舍五,入至小数点后两位。如果无法到达目的地，则输出,“,No solution,”,。,样例：,INPUT ( D1 C D2 P N),275.6 11.9 27.4 2.8 2,油站号,I,离出发点的距离,Di,每升汽油价格,1 102.0 2.9,2 220.0 2.2,OUTPUT,26.95,（该数据表示最小费用）,分析,首先找到,(,从后向前,),油价最低的加油站，显然车至该站油箱应为空，这样就可将起点至该站与该站至终点作为两段独立考虑，分别求其最小费用，二者之和即为总费用，这样一直分下去，若某段只有起点与终点两个加油站时无需再分，如某一段油价最低的加油站即为起点，则如能一次加油即到达该段终点则最好，若不能，则加满油再考虑油箱有油情况下的二分法，考虑起点之外所有的加油站中从后往前油价最低的加油站，若该加油站位于起点加满油后不能到达之处，则到达该站时油箱应该为空，以该站为界将全程分为两个独立段考虑，前半段为有油情况，后半段为无油情况。,第二种情况，若该加油站处于起点加满油后能到达之处，则将该段总路程缩短为该加油站至终点的情况，该加油站在该段路程中最便宜，若从该站加满油仍不能到达终点，则继续分治即可，程序被设计成一个递归函数,money,，形式参数,start,表示起点站，形式参数,stop,表示终点站，形式参数,rest,表示到达加油站,start,时汽车油箱余下的油的容量，,money,函数最终计算出从加油站,start,到,stop,区间内的最小费用。,function money (start,，,stop:longint,；,rest:real):real,；,Var k,：,longint,；,begin,if stop-starl=1,then money:=(dstop-dstar1)/d2-rest)*pstart,else begin,k:=minp(start,，,stop-1),；,minp(b,，,e:longint):longint,；在,b,站到,e,站之间从后往前找油价最低的站,if kstart ,油价最低的加油站不是起点站,then money:=money(start,，,k,，,rest)+money(k,，,stop,，,0),else if dstop-dstart=d2*c ,在起点加满油能直接到达该段终点,then money:=(dstop-dstart)/d2-rest) * pstart,else begin,k:=minp(start+1 , stop-1) ;,if dk - dstart = d2 * c then ,在起点加满油能到达加油站,k,money:=(c-rest) * pstart + money(k, stop, c-(dk - dstart)/d2),else,money := money(start, k, rest) + money( k, stop, O),end,end,end;,分治的应用举例,例题,4,：赛程问题。有,n,个编号为,1,到,n,的运动员参加某项运动的单循环比赛，即每个运动员要和所有其他运动员进行一次比赛。试为这,n,个运动员安排一个比赛日程，使得每个运动员每天只进行一场比赛，且整个比赛在,n-1,天内结束。输入运动员人数,n,（,n=10000,），输出一个,n,阶方阵,A1.N,0.N-1,，当,J,0,时，,AI,J,表示第,I,名运动员在第,J,天的比赛对手。,由于,N,个运动员要进行单循环比赛，且在,N-1,天内要结束全部比赛，经过分析，当且仅当,N,为,2,的整次幂时，问题才有解，当然解是不唯一的。这样可以将运动员分成两组：,1,2,N,2,和,N,2,1,N,2,2,N,。给第一组运动员安排一个比赛日程，得到一个,N,2,阶的方阵,A1,；同时给第二组的运动员安排一个比赛日程，同样会得到一个,N,2,阶的一个方阵,A2,。考虑到比赛的性质，设定第,I,个运动员在某一天的比赛对手为第,K,个运动员，则第,K,个运动员在同一天的比赛对手必然是第,I,个运动员，即若有,AI,J=K,，则,AK,，,J=I,。因此原问题的解,(,一个,N,阶方阵,),可以由分解后的两个子问题的解，合并起来。同时每一个子问题又可以按照上述的二分法分解下去，直至每个组中仅有,2,个运动员时为止。,procedure arrangment(K,N:integer);,从,K,号运动员起的共,N,员运动员单循环比赛日程表的过程,begin,if n=2 then ,处理只有,2,名运动员的情况，递归终止条件,begin,AK,0:=K;AK,1:=K+1;,AK+1,0:=K+1; AK+1,1:=K;,end else begin,arrangment(K,N div 2);,arrangment(K + N div 2,N div 2); ,递归分解原问题与求解子问题,for I:=K to K +(N div 2),1 do ,合并子问题的解,构造原问题的解,AI,J,for J:=(N div 2) to N-1 do,AI,J:=AI+(N div 2),J-(N div 2);,for I:=K+(N div 2) to K +N,1 do,for J:=(N div 2) to N-1 do,AI,J:=AI-(N div 2),J-(N div 2);,end;,end;,分治的应用举例,例题,5,：求,“,逆序对,”,。,给定一整数数组,A=(A,1,A,2,A,n,),若,iA,j,则,就为一个逆序对。例如数组（,3,，,1,，,4,，,5,，,2,）的逆序对有,。问题是，输入,n,和,A,数组，统计逆序对数目。,1=naj then c:=c+1;,时间复杂度为,O(n,2,),分析,采用二分法求解,:,记数列,ast,ed,的逆序对数目为,D(st,ed);mid=(st+ed)/2,则有：,D(st,ed)=D(st,mid)+D(mid+1,ed)+F(st.mid,ed).,其中,F(st,mid,ed),表示一个数取自,Ast,mid,令一个数取自,Amid+1,ed,的逆序对数目。,