基础法枚举贪心分治策略

1、第一部分枚举策略的基本思想 n枚举法，又称穷举法，指在一个有枚举法，又称穷举法，指在一个有穷的可能的解的集合中，一一枚举穷的可能的解的集合中，一一枚举出集合中的每一个元素，用题目给出集合中的每一个元素，用题目给定的检验条件来判断该元素是否符定的检验条件来判断该元素是否符合条件，若满足条件，则该元素即合条件，若满足条件，则该元素即为问题的一个解；否则，该元素就为问题的一个解；否则，该元素就不是该问题的解。不是该问题的解。枚举策略的基本思想 n枚举方法也是一种搜索算法，即对问题枚举方法也是一种搜索算法，即对问题的所有可能解的状态集合进行一次扫描的所有可能解的状态集合进行一次扫描或遍历。在具体的程序

2、实现过程中，可或遍历。在具体的程序实现过程中，可以通过循环和条件判断语句来完成。以通过循环和条件判断语句来完成。n枚举法常用于解决枚举法常用于解决“是否存在是否存在”或或“有有多少种可能多少种可能”等类型的问题。例如，求等类型的问题。例如，求解不定方程的问题就可以采用列举法。解不定方程的问题就可以采用列举法。 虽然枚举法本质上属于搜索策略，但是它与回溯法有所不同。因为适用虽然枚举法本质上属于搜索策略，但是它与回溯法有所不同。因为适用枚举法求解的问题必须满足两个条件：枚举法求解的问题必须满足两个条件： 可预先确定每个状态的元素个数可预先确定每个状态的元素个数n； 状态元素状态元素a1，a2，an

3、的可能值为一个连续的值域。的可能值为一个连续的值域。设设 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 输出问题的解；输出问题的解；枚举策略的基本思想 n 枚举法的特点是算法比较简单，在用枚枚举法的特点是算法比较简单，在用枚举法设计算法时，

4、重点注意优化，减少举法设计算法时，重点注意优化，减少运算工作量。将与问题有关的知识条理运算工作量。将与问题有关的知识条理化、完备化、系统化，从中找出规律，化、完备化、系统化，从中找出规律，减少枚举量。减少枚举量。 枚举方法的优化枚举算法的时间复杂度：状态总数枚举算法的时间复杂度：状态总数*单个状态的耗单个状态的耗时时n主要优化方法：主要优化方法： 减少状态总数减少状态总数 降低单个状态的考察代价降低单个状态的考察代价n优化过程从以下几个方面考虑：优化过程从以下几个方面考虑： 枚举对象的选取枚举对象的选取 枚举方法的确定枚举方法的确定 采用局部枚举或引进其他算法采用局部枚举或引进其他算法枚举算法

5、的应用：二进制数的分类：二进制数的分类若将一个正整数转化为二进制数后，若将一个正整数转化为二进制数后，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两类数的个数。两类数的个数。 此题是一道统计类题目。解决此题是一道统计类题目。解决统计问题的一个常用方法是枚举法：逐一统计

6、问题的一个常用方法是枚举法：逐一枚举所有情况，同时进行统计，枚举结束枚举所有情况，同时进行统计，枚举结束时，统计也完成，得到结果。时，统计也完成，得到结果。n具体对本题而言，采用枚举法的正确性与具体对本题而言，采用枚举法的正确性与可行性是显然的，而本题的数据规模又仅可行性是显然的，而本题的数据规模又仅为为11000，所以采用逐一枚举方法进行，所以采用逐一枚举方法进行统计的时间复杂度是完全可以接受的。统计的时间复杂度是完全可以接受的。枚举算法的应用例题2：01统计例题例题4：圆桌骑士（：圆桌骑士（ioi试题）试题） 在一个在一个8*8的棋盘上，有一个国王和若干的棋盘上，有一个国王和若干个武士。其

7、中，国王走一字步，骑士走个武士。其中，国王走一字步，骑士走马步。若国王与骑士相会在同一点上，马步。若国王与骑士相会在同一点上，国王可以选择让骑士背他走。求一个点，国王可以选择让骑士背他走。求一个点，使所有的骑士和国王相距在这个点上的使所有的骑士和国王相距在这个点上的所走的步数最少。所走的步数最少。枚举算法的应用此题可从3个方面考虑： 分治、枚举、数学方法。n由于无法将这个问题划分为各自独立的小问题来解决，分治显然是不行的。又因武士和国王位置的不固定性和其走法的差异，推导不出一个数学公式。因此考虑使用枚举，需要枚举的三个要点： 1、最后的汇聚点。 2、国王与背他的骑士的汇聚点。 3、国王与背他的

8、骑士。枚举算法的应用n国王最多只会与一个骑士结合，因为骑士的最终目标也是最终汇聚点，一旦国王与某个骑士汇合后，即马上可与其结合，剩下的只需要将所有的骑士汇合就可以了。更没有必要在中途中有将国王托付给其他的骑士。 这样我们估算一下时间为o（8*8*8*8*63）=o（36*104），完全可以承受。n另外，我们需要预先将2点之间走马字步的距离计算出来。可以使用floyd或是bfs。 枚举算法的应用局部枚举例题例题5：求第一、第二、第三最短路问题：求第一、第二、第三最短路问题局部枚举例题例题6：新年好：新年好 重庆城里有重庆城里有n个车站，个车站，m条双向公路连接其条双向公路连接其中的某些车站。每两

9、个车站最多用一条公路中的某些车站。每两个车站最多用一条公路直接相连，从任何一个车站出发都可以经过直接相连，从任何一个车站出发都可以经过一条或多条公路到达其他车站，但不同的路一条或多条公路到达其他车站，但不同的路径需要花费的时间可能不同。在一条路上花径需要花费的时间可能不同。在一条路上花费的时间等于路径上所有公路需要的时间之费的时间等于路径上所有公路需要的时间之和。和。n佳佳的家在车站佳佳的家在车站1，他有五个亲戚，分别，他有五个亲戚，分别住在车站住在车站a,b,c,d,e。过年了，他需要从。过年了，他需要从自己的家出发，拜访每个亲戚（顺序任自己的家出发，拜访每个亲戚（顺序任意），给他们送去节日

10、的祝福。怎样走，意），给他们送去节日的祝福。怎样走，才需要最少的时间？才需要最少的时间？分析这一题中的边数远小于这一题中的边数远小于n2，所以复杂度也，所以复杂度也只有只有nlogn+m算法框架是：算法框架是：（1）用）用5次最短路，计算出次最短路，计算出6个点两两之个点两两之间的距离间的距离（2）枚举）枚举5个结点的全排列，找到一个使个结点的全排列，找到一个使得总路程长度最短的方案。得总路程长度最短的方案。最大子矩阵的求解方法第二部分贪心方法的基本思想 n贪心是一种解题策略，也是一种解题思想n使用贪心方法需要注意局部最优与全局最优的关系，选择当前状态的局部最优并不一定能推导出问题的全局最优n

11、利用贪心策略解题，需要解决两个问题：n该题是否适合于用贪心策略求解n如何选择贪心标准，以得到问题的最优解 适用于贪心策略求解的问题的特点 适用于贪心策略求解的问题必须具有最优子结构的性质，但并不是所有具有最优子结构的问题都可以用贪心策略求解。因为贪心往往是盲目的，需要使用更理性的方法动态规划（例如“0-1背包问题”与“部分背包问题”） 贪心方法的应用：节点网络。现有一个n！个节点的网络，每个节点的编号都是编号（a1a2a3an）序列的一个置换。对于任意两个节点s和t，如果t的编号是由s编号的首位与除首位外的编号中任一位交换所得 ，则s和t之间有一条边，求从给定节点s走到节点（a1a2a3an）

12、所需经过的最少边数。其中，n100。 贪心方法的应用例如n=3的情况：(a1a2a3)(a1a3a2)(a2a3a1)(a2a1a3)(a3a1a2)(a3a2a1)贪心方法的应用从题意表面上看，本题是一个求最短路径的问题，但题设中的n100，也就是说图中最多有100！个节点，采用二维关系的图结构根本无法存贮这众多的状态。通过问题的本质分析，可以将问题转化为一个序列的最优转化问题。贪心方法的应用采用：每次让一个节点归位或为下一步工作做准备。其具体步骤为：n若序列中第一个点为ax (x1)，则将第一个点和第x个点交换。这便完成了让一个点归位的工作；n若第一个是a1，则任找一个编号与位置不相符的点

13、，并与之交换。这样下一步便可让交换到1号位置的点归位。贪心方法的应用(a3a4a1a2)(a1a4a3a2) 第一个点a1已归位，但第二个点为a4a2，将第2个点 a4与a1交换第一个点为a3a1，将第3个点a1与a3交换(a4a1a3a2) 第一个点为a4a1，将第4个点a2与a4交换(a2a1a3a4) 第一个点为a2a1，将第2个点a1与a2交换(a1a2a3a4)已经符合要求了一共经过4步完成。下面看一个n=4，初始序列为(a3a4a1a2)的推演过程：贪心方法的应用：d-规则问题。对任意给定的m(mn+)和n(nn+)，满足m1，使得kap，则修改p为：p=p-y|y=sa,sn+

14、，并称该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,9 d=52. a=4 p=3,6,7,9d=5

15、+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分值越多越好。因此，本题不能不能采用纯粹的贪心策略求解。贪心方法的应用将原算法基础上进行改进。下面给出新的算法：1.建立集合p=m.n2.从n div 2到m每数构造一个

16、集合ci，包含该数在p中的所有倍数（不包括i本身）3.从n div 2起找到第一个元素个数最少但又不为空的集合ci4.在d分值中加上i5.把i及ci集合从p集中删除，更新所有构造集合的元素6.检查所有构造集合，若还有非空集合，则继续3步骤，否则打印、结束贪心方法的应用下面看m=3, n=18时的推演过程：1.初始p=3.182.找到i=9, ci=18, p=3.8,10.173.找到i=8, ci=16, p=3.7,10.15,174.找到i=7, ci=14, p=3.6,10.13,15,175.找到i=6, ci=12, p=3.5,10,11,13,15,176.找到i=3, ci

17、=15, p=4,5,10,11,13,177.找到i=5, ci=10, p=4,11,13,17到此所有构造集合全部为空，d=9+8+7+6+3+5=38贪心方法的应用：n能否证明此贪心策略是正确的？n能否找到其他更好的算法？贪心方法的应用：射击竞赛射击的目标是一个由rc(2rc1000)个小方格组成的矩形网格。每一列恰有2个白色的小方格和r-2个黑色的小方格。行从顶至底编号为1r，列从左至右编号为1c。射击者可射击c次。在连续的c次射击中，若每列恰好有一个白色的方格被射中，且不存在无白色方格被射中的行，这样的射击才是正确的。如果存在正确的射击方法，则要求找到它。贪心方法的应用射击的选择有

18、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小，则问题无解，否则我们可以先根据网络流的结果求出该二分图的具体匹配方案。贪心方法的应用的连线流量为

19、1的连线流量为0选择的射击格即为：(1,3), (2,1), (3,2), (4,4)s21432143t贪心方法的应用网络流算法经过优化，时间复杂度可以达到o(c(n+4c+4r) 上述网络流算法虽然可以通过全部数据，但编程复杂度很高，而且极易出错，一不小心就会因为一个小错误影响整个程序。贪心方法的应用1.统计所有行包含的白格数2.从还没有射击格的行中选出一个白格数最少的3.检查所选的行1.若所选行的白格数为0，则输出无解；2.否则从所选行的白格中任选一个作为射击格，并将与该格同列的另一个白格所处行的白格数减14.返回到第2步，直到所有的行都有射击格。5.若还有列没有选射击格，则在该列任选一

20、白格作为射击格即可贪心方法的应用上面的贪心方法非常高效：时间复杂度为o(rc)，如果在程序中使用堆优化，时间复杂度将降为o(rlog2c)。空间复杂度是线性的，而且非常容易实现。现在关键的问题就是如何证明它的正确性？贪心方法的应用用hi表示第i行的白格数。如果最开始的时候：nminhi=0: 第i行已经没有办法找到可作为射击格的白格，那么问题只能无解。nminhi=1: 那么第i行的这一个白格必须要作为射击格，否则将因第i行没有射击格而造成问题无解。nminhi2: 那么在这一行任选一个白格，顶多只会造成剩余行中有一行h值为1，再处理那一行，最多也只会再造成剩余行中有一行h值为1，如此往复，将

21、保持h值为1的行数不超过1行，最后最坏的情况也是造成最后一行的h值为1，继续下去所有行就都已选取了射击格了。因此，如果原问题有解，该贪心方法一定能找到一种正确的方案。由此可以证明，此贪心方法是正确的。贪心方法的应用：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)+ + + + - +

22、-贪心方法的应用一种操作组合：(1,1), (2,2), (3,3),(1,2), (2,3), (3,1),(1,1), (2,3), (3,2),(1,3), (2,1), (3,2),符号为上一次取反操作后的结果+-+-+-+-+-+-+-+-+-+-+仅剩仅剩一个一个“+”。贪心方法的应用是否可以用贪心法解决此题？贪心方法的推广n贪心与其它算法结合n搜索的最优化剪枝（ 生日蛋糕）n优化动态规划（ peter的快餐店）n贪心方法与解题策略n最优方法不一定是最好方法n想不到最优解法就用较优解法贪心与其它算法结合：peter的快餐店peter最近在r市新开了一家快餐店。 该快餐店准备推出一种

23、套餐，每套由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个薯条的情况

24、下，最多能生产的饮料数，则pi,j,k=maxpi-1,j1,k1+ri,j-j1,k-k1 (j-j1)p1+(k-k1)p2ti)通过对该算法的时间复杂度分析，最坏的情况下时间复杂度将达到109，是相当费时的。贪心与其它算法结合现在加入，用贪心方法作预处理 ：n首先计算出一天生产套数的上限值：min100 div a,100 div b,100 div cn接着，用贪心方法计算出这n条生产线可以生产的套数，并与上限比较，大于或等于则输出上限值并退出，否则再调用动态规划。因为贪心方法的代价很低，这里甚至可以使用多次贪心标准不同的贪心方法，取其最大值。n在运行动态规划的过程中，也可以每完成一阶

25、段工作便与上限值进行比较，将贪心思想充分融入到动态规划过程中，这样以来，便可望在动态规划完成前提前结束程序。贪心方法小结贪心作为一种解题思路，虽然有时无法证明它的正确性，但在无法找到其他算法的时候，不失为一种好方法。并且，贪心与其他算法的结合，可以对其他算法起到优化作用。第三部分归纳法的基本思想 n归纳法的基本思想是通过列举少量的特殊情况，经过分析，最后找出一般的关系。从本质上讲，归纳就是通过观察一些简单而特殊的情况，最后总结出有用的结论或解决问题的有效途径。 归纳法解题的过程1.细心的观察；2.丰富的联想；3.继续尝试；4.总结归纳出结论。归纳法解题的过程n归纳是种抽象，即从特殊现象中找出一

26、般关系。由于在归纳的过程中不可能对所有的可能情况进行枚举，因而最后得到的结论还只是一种猜测(即归纳假设)。所以，严格说来对于归纳假设还必须加以严格的证明。归纳策略解题应注意的问题：1.从问题的简单具体状态分析入手，目的是去寻求可以推广的一般性规律，因此应考虑简单状态与一般性状态之间的联系。2.从简单状态中分析出来的规律特征应能够被验证是正确的，不能想当然或任意地提出猜想，否则归纳出来的结论是错误的，必然导致整个问题的解是错解。归纳策略的应用： 求前n个自然数的平方之和： s=12+22+32+n2 归纳策略的应用这本是一道很简单的题目，但如果能找出s值与n的关系，则此题将更进一步得到简化，由数

27、学证明得知：(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 但这只是通过总结归纳而得到的一种猜测，是否正确还需证明，对归纳假设的证明通常采用数学归纳法（证略）。归纳策略的应用：若干个正整数之和为n，其中：n1，因此排除了n3和n4存在的可能性.又由于n和m是整数，因此1和2应为整数。由于m2n2单调递增，从mk出发，按递减方向将m值代入n的求根公式。只要1（或2）为整数、n1（或n2）为整数且小于k，则得出的一组m和n一定使 m2n2的值最大。算法描述算法描述 mk；

28、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秒内出解。归纳策略的应用方法二方法二分析

29、小数据会发现：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。算法算法：

30、利用fibomacci数列顺推m,n，求出在条件范围内的m,n最大值，此时m2n2的值最大。归纳策略的应用：“王”棋子遍历问题。题目大意：在nn格（2n=20）棋盘上的任一格子中放置一个棋子，棋子每次只能往其上、下、左、右相邻方格移动一步，求一种遍历方法，使得棋子走n2-1步遍历整个棋盘，每个方格只能被访问一次。归纳策略的应用归纳策略的应用当n=2时，该棋盘存在一条回路，所以任意一点作为起点均能遍历整个棋盘，考虑到当n=4,6时的情况，进而推广到n为偶数时，均可以按规律产生回路，从给定的起点开始沿着该回路均可遍历整个棋盘。归纳策略的应用再考虑n为奇数时的情况，先设定n=3时，棋盘可划分成5个白

31、格和4个黑格，人工可以推出，从任一黑格出发将无法遍历整个棋盘，然后考虑n=5时的情况，同样可推出，从棋盘中的任一黑格出发无法遍历整个棋盘。规律规律：当当n为奇数时，棋子的起始位置若满足其为奇数时，棋子的起始位置若满足其横坐标和纵坐标之和为奇数时（即图中所示的任横坐标和纵坐标之和为奇数时（即图中所示的任一黑格位置），问题将无解。一黑格位置），问题将无解。归纳策略的应用 这一规律很容易能够得到验证,因为按照规则，从任一黑格出发，必走一白格再走一黑格，所以白格数目与黑格数目应相等，而图中两者数目并不相等，如n=5时，图中共有黑格12个，白格共有13个。归纳策略的应用通过上述归纳，我们在搜索求解问题时

32、，将会较大地提高算法效率，尤其是在一些问题的无解判定时，运用归纳策略的作用将会十分明显。归纳策略的应用：kathy函数函数(hncoi) tiger非常喜欢数学，所以他参加了学校组织的数学课外兴趣小组。在兴趣小组的学习当中，老师向tiger介绍了kathy函数，kathy函数是这样定义的：n)(2) 12(3)34()() 12(2) 14()()2(3)3(1) 1 (nfnfnfnfnfnfnfnfff归纳策略的应用：kathy函数函数(hncoi)ntiger对kathy函数产生了浓厚的兴趣，他通过研究发现有很多的数n都满足n对于一个给定的数m，他希望你求出所有的满足 的自然数n的个数，

33、其中m8 then begin 分解成四小块； 对于其中一块devide(n-3) end else case n of 6: 按n=6分割； 7: 按n=7分割； 8: 按n=8分割； end;end;分治思想分治思想n如果在将规模为n的问题分成k个不同子集合的情况下，能得到k个不同的可分别求解的子问题，其中1k=n，而且在求出了这些子问题的解之后，还可找到适当的方法把它们合并成整个问题的解，那么，具备上述特性的问题可考虑使用分治策略设计求解。这种设计求解的思想就是将整个问题分成若干个小问题后分而治之。 分治思想分治思想n分治(divide-and-conquer)就是“分而治之”的意思，其

34、实质就是将原问题分成n个规模较小而结构与原问题相似的子问题；然后递归地解这些子问题，最后合并其结果就得到原问题的解。其三个步骤如下；1.分解(divide)：将原问题分成一系列子问题。2.解决(conquer)：递归地解各子问题。若子问题足够小，则可直接求解。3.合并(combine)；将子问题的结果合并成原问题的解。 分治思想分治思想问题s问题s问题ss的解问题s1问题s2问题si问题sns1的解s2的解si的解sn的解问题的分解子集解的合并子问题求解分治思想分治思想n由分治法所得到的子问题与原问题具有相同的类型。如果得到的子问题相对来说还太大，则可反复使用分治策略将这些子问题分成更小的同类

35、型子问题，直至产生出不用进一步细分就可求解的子问题。分治求解可用一个递归过程来表示。n要使分治算法效率高，关键在于如何分割？一般地，出于一种平衡原则，总是把大问题分成k个规模尽可能相等的子问题，但也有例外，如求表的最大最小元问题的算法，当n6时，等分定量成两个规模为3的子表l1和l2不是最佳分割。分治的应用举例分治的应用举例例题例题2： 一元三次方程求解 有形如：ax3+bx2+cx+d=0这样的一个一元三次方程。给出该方程中各项的系数(a，b，c，d均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值=1。要求由小到大依次在同一行输出这三个实根(根

36、与根之间留有空格)，并精确到小数点后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分治的应用举例分治的应用举例n如果精确到小数点后两位，可用简单的枚举法：将x从-100.00 到100.00（步长0.01） 逐一枚举，得到20000个 f(x)，取其值与0最接近的三个f(x)，对应的x即为答案。而题目已改成精度为小数点后4位，枚举算法时间复杂度将达不到要求。n直接使用求根公式，极为复杂。加上本题的提示给我们以启迪：采用二分法

37、逐渐缩小根的范围，从而得到根的某精度的数值。n具体方法如下：分治的应用举例分治的应用举例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 ，解即

38、为a；若f(a)f(a+1)0 ，则可以利用a中所述的二分法迅速出找出解。n如此可求出方程的所有的解。分治的应用举例分治的应用举例例题例题3： 旅行家的预算 一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离d1、汽车油箱的容量c（以升为单位）每升汽油能行驶的距离d2、出发点每升汽油价格p和沿途油站数n（n可以为零），油站i离出发点的距离di、每升汽油价格 pi（ il，2，.n）。 计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“no solution”。样例：n input ( d1 c d2 p n)n 275.6 11.9

39、 27.4 2.8 2n油站号i 离出发点的距离di 每升汽油价格 n 1 102.0 2.9n 2 220.0 2.2n outputn 26.95（该数据表示最小费用）分析 首先找到(从后向前)油价最低的加油站，显然车至该站油箱应为空，这样就可将起点至该站与该站至终点作为两段独立考虑，分别求其最小费用，二者之和即为总费用，这样一直分下去，若某段只有起点与终点两个加油站时无需再分，如某一段油价最低的加油站即为起点，则如能一次加油即到达该段终点则最好，若不能，则加满油再考虑油箱有油情况下的二分法，考虑起点之外所有的加油站中从后往前油价最低的加油站，若该加油站位于起点加满油后不能到达之处，则到达

40、该站时油箱应该为空，以该站为界将全程分为两个独立段考虑，前半段为有油情况，后半段为无油情况。 n第二种情况，若该加油站处于起点加满油后能到达之处，则将该段总路程缩短为该加油站至终点的情况，该加油站在该段路程中最便宜，若从该站加满油仍不能到达终点，则继续分治即可，程序被设计成一个递归函数money，形式参数start表示起点站，形式参数stop表示终点站，形式参数rest表示到达加油站start时汽车油箱余下的油的容量，money函数最终计算出从加油站start到stop区间内的最小费用。 nfunction money (start，stop:longint；rest:real):real；n

41、var k：longint；nbeginnif stop-starl=1n then money:=(dstop-dstar1)/d2-rest)*pstartnelse beginn k:=minp(start，stop-1)； minp(b，e:longint):longint；在；在b站到站到e n 站之间从后往前找油价最低的站站之间从后往前找油价最低的站 if kstart 油价最低的加油站不是起点站油价最低的加油站不是起点站 n then money:=money(start，k，rest)+money(k，stop，0)n else if dstop-dstart=d2*c 在起点

42、加满油能直接到达该在起点加满油能直接到达该段终点段终点n then money:=(dstop-dstart)/d2-rest) * pstartn else beginn k:=minp(start+1 , stop-1) ;n if dk - dstart = d2 * c then 在起点加满油能到达在起点加满油能到达加油站加油站k money:=(c-rest) * pstart + money(k, stop, c-(dk - dstart)/d2)n elsen money := money(start, k, rest) + money( k, stop, o)n endn en

43、dnend;分治的应用举例分治的应用举例n例题例题4：赛程问题。有：赛程问题。有n个编号为个编号为1到到n 的运动的运动员参加某项运动的单循环比赛，即每个运动员员参加某项运动的单循环比赛，即每个运动员要和所有其他运动员进行一次比赛。试为这要和所有其他运动员进行一次比赛。试为这n个运动员安排一个比赛日程，使得每个运动员个运动员安排一个比赛日程，使得每个运动员每天只进行一场比赛，且整个比赛在每天只进行一场比赛，且整个比赛在n-1天内天内结束。输入运动员人数结束。输入运动员人数n（n=10000），输），输出一个出一个n阶方阵阶方阵a1.n,0.n-1，当，当j0时，时，ai,j表示第表示第i名运动员在第名运动员在第j天的比赛对手。天的比赛对手。n 由于由于n个运动员要