基础算法枚举贪心分治策略.ppt

基础算法策略,长沙市第一中学曹利国,第一部分,枚举策略,枚举策略的基本思想,枚举法，又称穷举法，指在一个有穷的可能的解的集合中，一一枚举出集合中的每一个元素，用题目给定的检验条件来判断该元素是否符合条件，若满足条件，则该元素即为问题的一个解；否则，该元素就不是该问题的解。,枚举策略的基本思想,枚举方法也是一种搜索算法，即对问题的所有可能解的状态集合进行一次扫描或遍历。在具体的程序实现过程中，可以通过循环和条件判断语句来完成。枚举法常用于解决“是否存在”或“有多少种可能”等类型的问题。例如，求解不定方程的问题就可以采用列举法。,虽然枚举法本质上属于搜索策略，但是它与回溯法有所不同。因为适用枚举法求解的问题必须满足两个条件：可预先确定每个状态的元素个数n；状态元素a1，a2，an的可能值为一个连续的值域。设 ai1状态元素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 输出问题的解；,枚举策略的基本思想,枚举法的特点是算法比较简单，在用枚举法设计算法时，重点注意优化，减少运算工作量。将与问题有关的知识条理化、完备化、系统化，从中找出规律，减少枚举量。,枚举方法的优化,枚举算法的时间复杂度：状态总数*单个状态的耗时主要优化方法：减少状态总数 降低单个状态的考察代价优化过程从以下几个方面考虑：枚举对象的选取 枚举方法的确定 采用局部枚举或引进其他算法,枚举算法的应用,例题1：二进制数的分类若将一个正整数转化为二进制数后，0的个数多于1的个数的这类数称为A类数，否则称为B类数。例如：（13）10=（1101）2，13为B类数；（10）10=（1010）2 10为B类数；（24）10=（11000）2 24为A类数；程序要求：求出11000之中（包括1与1000），全部A、B两类数的个数。,【分析】此题是一道统计类题目。解决统计问题的一个常用方法是枚举法：逐一枚举所有情况，同时进行统计，枚举结束时，统计也完成，得到结果。具体对本题而言，采用枚举法的正确性与可行性是显然的，而本题的数据规模又仅为11000，所以采用逐一枚举方法进行统计的时间复杂度是完全可以接受的。,枚举算法的应用,例题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！个节点的网络，每个节点的编号都是编号（A1A2A3AN）序列的一个置换。对于任意两个节点S和T，如果T的编号是由S编号的首位与除首位外的编号中任一位交换所得，则S和T之间有一条边，求从给定节点S走到节点（A1A2A3AN）所需经过的最少边数。其中，n100。,贪心方法的应用,例如n=3的情况：,贪心方法的应用,【分析】从题意表面上看，本题是一个求最短路径的问题，但题设中的N100，也就是说图中最多有100！个节点，采用二维关系的图结构根本无法存贮这众多的状态。通过问题的本质分析，可以将问题转化为一个序列的最优转化问题。,贪心方法的应用,采用贪心策略：每次让一个节点归位或为下一步工作做准备。其具体步骤为：若序列中第一个点为Ax(x1)，则将第一个点和第x个点交换。这便完成了让一个点归位的工作；若第一个是A1，则任找一个编号与位置不相符的点，并与之交换。这样下一步便可让交换到1号位置的点归位。,贪心方法的应用,一共经过4步完成。,下面看一个n=4，初始序列为(A3A4A1A2)的推演过程：,贪心方法的应用,例题2：d-规则问题。对任意给定的m(mN+)和n(nN+)，满足m1，使得KaP，则修改P为：P=P-y|y=sa,sN+，并称该d规则具有分值a。现要求编制一个程序，对输入的m,n值，构造相应的初始集合P，对P每应用一次d规则就累加其相应的分值，求能得到最大累加分值的d规则序列，输出每次使用d规则时的分值和集合p的变化过程。,贪心方法的应用,【分析】初看这一问题，很容易想到用贪心策略来求解，即选择集合中最大的可以删除的数开始删起，直到不能再删除为止，而且通过一些简单的例子来验证，这一贪心标准似乎也是正确的，例如，当m=3，n=10时，集合P3,10，运用上述“贪心标准”可以得到这一问题的正确的最优解d=54312，即其d-规则过程如下：1.a=5 P=3,4,6,7,8,9d=52.a=4 P=3,6,7,9d=5+4=93.a=3 p=7 d=5+4+3=12,贪心方法的应用,但是，如果再仔细地分析一个例子，当m=3，n18时，如果还是使用上述“贪心标准”，则得到问题的d-规则总分为d=35，其d-规则序列为（9,8,7,6,5），而实际上可以得到最大d-规则总分为d38，其对应的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：射击竞赛射击的目标是一个由RC(2RC1000)个小方格组成的矩形网格。每一列恰有2个白色的小方格和R-2个黑色的小方格。行从顶至底编号为1R，列从左至右编号为1C。射击者可射击C次。在连续的C次射击中，若每列恰好有一个白色的方格被射中，且不存在无白色方格被射中的行，这样的射击才是正确的。如果存在正确的射击方法，则要求找到它。,贪心方法的应用,射击的选择有2C种，符合要求的却很少。要解决问题，还需从正确的射击方法的特征入手。,贪心方法的应用,【方法一】网络流算法我们将表示列的点编号为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),贪心方法的应用,网络流算法经过优化，时间复杂度可以达到O(C(n+4C+4R)上述网络流算法虽然可以通过全部数据，但编程复杂度很高，而且极易出错，一不小心就会因为一个小错误影响整个程序。,贪心方法的应用,【方法二】贪心方法统计所有行包含的白格数从还没有射击格的行中选出一个白格数最少的检查所选的行若所选行的白格数为0，则输出无解；否则从所选行的白格中任选一个作为射击格，并将与该格同列的另一个白格所处行的白格数减1返回到第2步，直到所有的行都有射击格。若还有列没有选射击格，则在该列任选一白格作为射击格即可,贪心方法的应用,上面的贪心方法非常高效：时间复杂度为O(RC)，如果在程序中使用堆优化，时间复杂度将降为O(Rlog2C)。空间复杂度是线性的，而且非常容易实现。现在关键的问题就是如何证明它的正确性？,贪心方法的应用,【证明】用hi表示第i行的白格数。如果最开始的时候：minhi=0:第i行已经没有办法找到可作为射击格的白格，那么问题只能无解。minhi=1:那么第i行的这一个白格必须要作为射击格，否则将因第i行没有射击格而造成问题无解。minhi2:那么在这一行任选一个白格，顶多只会造成剩余行中有一行h值为1，再处理那一行，最多也只会再造成剩余行中有一行h值为1，如此往复，将保持h值为1的行数不超过1行，最后最坏的情况也是造成最后一行的h值为1，继续下去所有行就都已选取了射击格了。因此，如果原问题有解，该贪心方法一定能找到一种正确的方案。由此可以证明，此贪心方法是正确的。,贪心方法的应用,例题4：Transversal 有一个(2n+1)(2n+1)的矩阵，每个单元格中有符号“+”或“-”。定义一种取反操作：将1至2n+1这2n+1个整数任意排列，得到序列A1,A2,A2n+1，然后将(1,A1),(2,A2),(2n+1,A2n+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)通过对该算法的时间复杂度分析，最坏的情况下时间复杂度将达到109，是相当费时的。,贪心与其它算法结合,现在加入贪心方法，用贪心方法作预处理：首先计算出一天生产套数的上限值：min100 div A,100 div B,100 div C接着，用贪心方法计算出这N条生产线可以生产的套数，并与上限比较，大于或等于则输出上限值并退出，否则再调用动态规划。因为贪心方法的代价很低，这里甚至可以使用多次贪心标准不同的贪心方法，取其最大值。在运行动态规划的过程中，也可以每完成一阶段工作便与上限值进行比较，将贪心思想充分融入到动态规划过程中，这样以来，便可望在动态规划完成前提前结束程序。,贪心方法小结,贪心作为一种解题思路，虽然有时无法证明它的正确性，但在无法找到其他算法的时候，不失为一种好方法。并且，贪心与其他算法的结合，可以对其他算法起到优化作用。,第三部分,归纳策略,归纳法的基本思想,归纳法的基本思想是通过列举少量的特殊情况，经过分析，最后找出一般的关系。从本质上讲，归纳就是通过观察一些简单而特殊的情况，最后总结出有用的结论或解决问题的有效途径。,归纳法解题的过程,细心的观察；丰富的联想；继续尝试；总结归纳出结论。,归纳法解题的过程,归纳是种抽象，即从特殊现象中找出一般关系。由于在归纳的过程中不可能对所有的可能情况进行枚举，因而最后得到的结论还只是一种猜测(即归纳假设)。所以，严格说来对于归纳假设还必须加以严格的证明。,归纳策略解题应注意的问题：,从问题的简单具体状态分析入手，目的是去寻求可以推广的一般性规律，因此应考虑简单状态与一般性状态之间的联系。从简单状态中分析出来的规律特征应能够被验证是正确的，不能想当然或任意地提出猜想，否则归纳出来的结论是错误的，必然导致整个问题的解是错解。,归纳策略的应用,例题1：求前n个自然数的平方之和：S=12+22+32+n2,归纳策略的应用,【分析】这本是一道很简单的题目，但如果能找出S值与n的关系，则此题将更进一步得到简化，由数学证明得知：(12+22+32+n2)/(1+2+3+n)=(2n+1)/3又由于 1+2+3+n=n(n+1)/2，因此得到：12+22+32+n2=n(n+1)(2n+1)/6 但这只是通过总结归纳而得到的一种猜测，是否正确还需证明，对归纳假设的证明通常采用数学归纳法（证略）。,归纳策略的应用,例题2：若干个正整数之和为n，其中：n2000，试求它们乘积的最大值以及该最大值的位数k。,归纳策略的应用,【分析】根据数学规律可知,若要使和固定的数的乘积最大，必须使这些数尽可能的多为3，于是可推得以下规律：当N mod 31 时，N可分解为一个4和若干个3的和；当N mod 32 时，N 可分解为一个2和若干个3的和；当N mod 30 时，N 直接分解为若干个3的和。按照这一分解方法，所有因数的乘积必定最大。注意：因N 的最大值可达2000，乘积将超过长整型数据范围，所以需用高精度运算。,归纳策略的应用,例题3：极值问题（最高时限15s）已知m、n为整数，且满足下列两个条件：m、n1，2，K，（1K109）(n 2mnm2)21编一程序，由键盘输入K，求一组满足上述两个条件的m、n，并且使m2n2的值最大。例如，若K1995，则m987，n1597，则m、n满足条件，且可使m2n2的值最大。,归纳策略的应用,【分析】方法一从初等数学的角度考虑：由条件（n 2mnm2）21得出：n 2mnm2+1=0n 2mnm21=0根据求根公式N1,2（m1,2）/2 n3,4（m1,2）/2其中：1sqrt（5*m24）；2sqrt（5*m24）；,归纳策略的应用,【分析】再考虑条件。由于n1，因此排除了n3和n4存在的可能性.又由于n和m是整数，因此1和2应为整数。由于m2n2单调递增，从mk出发，按递减方向将m值代入n的求根公式。只要1（或2）为整数、n1（或n2）为整数且小于k，则得出的一组m和n一定使 m2n2的值最大。,【算法描述】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 mml;end;while,归纳策略的应用,上述算法从数学意义上来说，是一定可以出得出正确解的。但是该算法疏漏了一个重要条件 1k109。如果K值超过105，上述算法不可能在限定的15秒内出解。,归纳策略的应用,【分析】方法二分析小数据会发现：m,n是Fibonacci数列的相邻两项。因为：（n 2mnm2）2 1故：（m2+mn n 2）2 1又：m 2mnn2(mn)2mn2n2(mn)2(mn)nn2 故：（m2mnn2）2(mn)2(mn)nn22 即：（n2mnm2）2(mn)2(mn)nn22,归纳策略的应用,【分析】由上述数学变换式可以得出，如果m和n为一组满足条件和条件的解，设nmn，m n那么n，m 也是一组满足条件和条件的一组解。将所有满足条件和条件的m和n 按递增顺序排成一个Fibomacci数列 1，1，2，3，5，8，数列中小于k的最大两个相邻数即为试题所要求的一组m和n。算法：利用Fibomacci数列顺推m,n，求出在条件范围内的m,n最大值，此时m2n2的值最大。,归纳策略的应用,例题4：“王”棋子遍历问题。题目大意：在nn格（2n=20）棋盘上的任一格子中放置一个棋子，棋子每次只能往其上、下、左、右相邻方格移动一步，求一种遍历方法，使得棋子走n2-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的个数，其中m=10100。,第四部分,递归与分治策略,递归的概念与应用,一个函数、过程、概念或数学结构，如果在其定义或说明内部又直接或间接地出现有其本身的引用，则称它们是递归的或者是递归定义的。在程序设计中，过程或函数直接或者间接调用自己，就被称为递归调用。,递归的概念与应用,递归过程是借助于一个递归工作栈来实现的问题向一极推进，这一过程叫做递推；而问题逐一解决，最后回到原问题，这一过程叫做回归。递归的过程正是由递推和回归两个过程组成。,递归的概念与应用,采用递归方法编写的问题解决程序具有结构清晰，可读性强等优点，且递归算法的设计比非递归算法的设计往往要容易一些，所以当问题本身是递归定义的，或者问题所涉及到的数据结构是递归定义的，或者是问题的解决方法是递归形式的时候，往往采用递归算法来解决。,递归的概念与应用,例题1：钢板分割问题。设有一块正方形的钢板，现需将它分成n个小正方形。例如，当：n=2 不可能有解。n=3 不可能有解。n=4 可分成4个小正方形钢板。n=5 不可能有解。n=6 即一个大的加五个小的。n=7 即三个较大的加四个小的。n=8 即一个大的加七个小的。问题为任给n，求出分成n个小正方形的方法。,递归的概念与应用,【分析】经过分析就可以得出：（1）按n=4的方法将1个小正方形分成4个，则增加了3个正方形。（2）以n=6为基础，由（1）可以得出n=9，12，15，。（3）以n=7为基础，由（1）可以得出n=10，13，16，。（4）以n=8为基础，由（1）可以得出n=11，14，17，。由此可以得出如下的递归算法：,递归的概念与应用,procedure devide(i:integer);Begin if n8 then begin 分解成四小块；对于其中一块devide(n-3)end else case n of 6:按n=6分割；7:按n=7分割；8:按n=8分割；end;End;,分治思想,如果在将规模为n的问题分成k个不同子集合的情况下，能得到k个不同的可分别求解的子问题，其中1k=n，而且在求出了这些子问题的解之后，还可找到适当的方法把它们合并成整个问题的解，那么，具备上述特性的问题可考虑使用分治策略设计求解。这种设计求解的思想就是将整个问题分成若干个小问题后分而治之。,分治思想,分治(divide-and-conquer)就是“分而治之”的意思，其实质就是将原问题分成n个规模较小而结构与原问题相似的子问题；然后递归地解这些子问题，最后合并其结果就得到原问题的解。其三个步骤如下；分解(Divide)：将原问题分成一系列子问题。解决(Conquer)：递归地解各子问题。若子问题足够小，则可直接求解。合并(combine)；将子问题的结果合并成原问题的解。,分治思想,分治思想,由分治法所得到的子问题与原问题具有相同的类型。如果得到的子问题相对来说还太大，则可反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生出不用进一步细分就可求解的子问题。分治求解可用一个递归过程来表示。要使分治算法效率高，关键在于如何分割？一般地，出于一种平衡原则，总是把大问题分成K个规模尽可能相等的子问题，但也有例外，如求表的最大最小元问题的算法，当n6时，等分定量成两个规模为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)0，根在(a+b)/2,b)中，对此区间重复该过程。执行完毕，就可以得到精确到0.0001的根。,分治的应用举例,B、求方程的所有三个实根所有的根的范围都在-100至100之间，且根与根之差的绝对值=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（il，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；beginif stop-starl=1 then money:=(dstop-dstar1)/d2-rest)*pstartelse 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 endend;,分治的应用举例,例题4：赛程问题。有n个编号为1到n 的运动员参加某项运动的单循环比赛，即每个运动员要和所有其他运动员进行一次比赛。试为这n个运动员安排一个比赛日程，使得每个运动员每天只进行一场比赛，且整个比赛在n-1天内结束。输入运动员人数n（n=10000），输出一个n阶方阵A1.N,0.N-1，当J0时，AI,J表示第I名运动员在第J天的比赛对手。,由于N个运动员要进行单循环比赛，且在N-1天内要结束全部比赛，经过分析，当且仅当N为2的整次幂时，问题才有解，当然解是不唯一的。这样可以将运动员分成两组：1,2,N2 和 N21,N22,N。给第一组运动员安排一个比赛日程，得到一个N2阶的方阵A1；同时给第二组的运动员安排一个比赛日程，同样会得到一个N2阶的一个方阵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=(A1,A2,An),若iAj,则就为一个逆序对。例如数组（3，1，4，5，2）的逆序对有,。问题是，输入n和A数组，统计逆序对数目。1=n=30000。,分析,原始的解决方案（双重循环）C:=0;For i:=1 to n-1 do for j:=i+1 to n do if aiaj then c:=c+1;时间复杂度为O(n2),分析,采用二分法求解:记数列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的逆序对数目。,分析,若要求计算d值的同时数列A已排序，设I,j指针分别已排序的Ast,med)和A(mid+1,ed)中的一个元素，若满足：Amid+1,Aj-1均小于Ai,但AjAi则j-mid-1必须计入F，顺序移动I,j指针即可完成合并。,