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

1、根底算法战略长沙市第一中学曹利国第一部分枚举战略枚举战略的根本思想 枚举法，又称穷举法，指在一个有穷的能够的解的集合中，一一枚举出集合中的每一个元素，用标题给定的检验条件来判别该元素能否符合条件，假设满足条件，那么该元素即为问题的一个解；否那么，该元素就不是该问题的解。枚举战略的根本思想 枚举方法也是一种搜索算法，即对问题的一切能够解的形状集合进展一次扫描或遍历。在详细的程序实现过程中，可以经过循环和条件判别语句来完成。枚举法常用于处理“能否存在或“有多少种能够等类型的问题。例如，求解不定方程的问题就可以采用列举法。 虽然枚举法本质上属于搜索战略，但是它与回溯法有所不同。由于适用枚举法求解的问

2、题必需满足两个条件： 可预先确定每个形状的元素个数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 输出问题的解；枚举战略的根本思想 枚举法的特点是算法比较简单，在用枚举法设计算法时，重点留意优化，减少运算任务量。将与问题有关的知识条理化

3、、完备化、系统化，从中找出规律，减少枚举量。 枚举方法的优化枚举算法的时间复杂度：形状总数*单个形状的耗时主要优化方法： 减少形状总数 降低单个形状的调查代价优化过程从以下几个方面思索： 枚举对象的选取 枚举方法确实定 采用部分枚举或引进其他算法枚举算法的运用例题1：二进制数的分类假设将一个正整数转化为二进制数后，0的个数多于1的个数的这类数称为A类数，否那么称为B类数。例如： 1310=11012， 13为B类数； 1010=10102 10为B类数； 2410=110002 24为A类数；程序要求：求出11000之中包括1与1000，全部A、B两类数的个数。 【分析】此题是一道统计类标题。

4、处理统计问题的一个常用方法是枚举法：逐一枚举一切情况，同时进展统计，枚举终了时，统计也完成，得到结果。详细对此题而言，采用枚举法的正确性与可行性是显然的，而此题的数据规模又仅为11000，所以采用逐一枚举方法进展统计的时间复杂度是完全可以接受的。枚举算法的运用例题2：01统计例题4：圆桌骑士IOI试题 在一个8*8的棋盘上，有一个国王和假设干个武士。其中，国王走一字步，骑士走马步。假设国王与骑士相会在同一点上，国王可以选择让骑士背他走。求一个点，使一切的骑士和国王相距在这个点上的所走的步数最少。枚举算法的运用【分析】此题可从3个方面思索： 分治、枚举、数学方法。由于无法将这个问题划分为各自独立

5、的小问题来处理，分治显然是不行的。又因武士和国王位置的不固定性和其走法的差别，推导不出一个数学公式。因此思索运用枚举，需求枚举的三个要点： 1、最后的会聚点。 2、国王与背他的骑士的会聚点。 3、国王与背他的骑士。枚举算法的运用国王最多只会与一个骑士结合，由于骑士的最终目的也是最终会聚点，一旦国王与某个骑士集合后，即马上可与其结合，剩下的只需求将一切的骑士集合就可以了。更没有必要在中途中有将国王拜托给其他的骑士。 这样我们估算一下时间为O8*8*8*8*63=O36*104，完全可以接受。另外，我们需求预先将2点之间走马字步的间隔计算出来。可以运用Floyd或是Bfs。 枚举算法的运用 算法流

6、程： disx1，y1，x2，y2-x1，y1x2，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; E

7、nd; End； Now:= all-mink武士走到集合点的间隔+ mink武士走到会聚点的间隔+ 国王走到会聚点的间隔+从会聚点到集合点的间隔； Best：=minbest，now End；部分枚举例题5：求第一、第二、第三最短路问题部分枚举例题6：新年好 重庆城里有n个车站，m条双向公路衔接其中的某些车站。每两个车站最多用一条公路直接相连，从任何一个车站出发都可以经过一条或多条公路到达其他车站，但不同的途径需求破费的时间能够不同。在一条路上破费的时间等于途径上一切公路需求的时间之和。佳佳的家在车站1，他有五个亲戚，分别住在车站a,b,c,d,e。过年了，他需求从本人的家出发，访问每个亲戚

8、顺序恣意，给他们送去节日的祝愿。怎样走，才需求最少的时间？分析这一题中的边数远小于n2，所以复杂度也只需nlogn+m算法框架是：1用5次最短路，计算出6个点两两之间的间隔2枚举5个结点的全陈列，找到一个使得总路程长度最短的方案。最大子矩阵的求解方法第二部分贪婪方法贪婪方法的根本思想 贪婪是一种解题战略，也是一种解题思想运用贪婪方法需求留意部分最优与全局最优的关系，选择当前形状的部分最优并不一定能推导出问题的全局最优利用贪婪战略解题，需求处理两个问题：该题能否适宜于用贪婪战略求解如何选择贪婪规范，以得到问题的最优解 适用于贪婪战略求解的问题的特点 适用于贪婪战略求解的问题必需具有最优子构造的性

9、质，但并不是一切具有最优子构造的问题都可以用贪婪战略求解。由于贪婪往往是盲目的，需求运用更理性的方法动态规划例如“0-1背包问题与“部分背包问题 贪婪方法的运用例题1：节点网络。现有一个N！个节点的网络，每个节点的编号都是编号A1A2A3AN序列的一个置换。对于恣意两个节点S和T，假设T的编号是由S编号的首位与除首位外的编号中任一位交换所得 ，那么S和T之间有一条边，求从给定节点S走到节点A1A2A3AN所需经过的最少边数。其中，n100。 贪婪方法的运用例如n=3的情况：(A1A2A3)(A1A3A2)(A2A3A1)(A2A1A3)(A3A1A2)(A3A2A1)贪婪方法的运用【分析】从题

10、不测表上看，此题是一个求最短途径的问题，但题设中的N100，也就是说图中最多有100！个节点，采用二维关系的图构造根本无法存贮这众多的形状。经过问题的本质分析，可以将问题转化为一个序列的最优转化问题。贪婪方法的运用采用贪婪战略：每次让一个节点归位或为下一步任务做预备。其详细步骤为：假设序列中第一个点为Ax (x1)，那么将第一个点和第x个点交换。这便完成了让一个点归位的任务；假设第一个是A1，那么任找一个编号与位置不相符的点，并与之交换。这样下一步便可让交换到1号位置的点归位。贪婪方法的运用(A3A4A1A2)(A1A4A3A2)第一个点A1已归位，但第二个点为A4A2，将第2个点 A4与A1

11、交换第一个点为A3A1，将第3个点A1与A3交换(A4A1A3A2)第一个点为A4A1，将第4个点A2与A4交换(A2A1A3A4)第一个点为A2A1，将第2个点A1与A2交换(A1A2A3A4)曾经符合要求了一共经过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规那么序列，输

12、出每次运用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时，假设还是运用上述“贪婪规范，那么得到问

13、题的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集中删除，更新一

14、切构造集合的元素检查一切构造集合，假设还有非空集合，那么继续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贪婪方法的运用讨论：能否证明此贪婪战略是

15、正确的？能否找到其他更好的算法？贪婪方法的运用例题3：射击竞赛射击的目的是一个由RC(2RC1000)个小方格组成的矩形网格。每一列恰有2个白色的小方格和R-2个黑色的小方格。行从顶至底编号为1R，列从左至右编号为1C。射击者可射击C次。在延续的C次射击中，假设每列恰好有一个白色的方格被射中，且不存在无白色方格被射中的行，这样的射击才是正确的。假设存在正确的射击方法，那么要求找到它。贪婪方法的运用射击的选择有2C种，符合要求的却很少。要处理问题，还需从正确的射击方法的特征入手。贪婪方法的运用【方法一】网络流算法我们将表示列的点编号为1到C，表示行的点编号为C+1到C+R，假设一个白色方格处在第

16、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)S21432143T列:行:源:汇:贪婪方法的运用网络流算法经过优化

17、，时间复杂度可以到达O(C(n+4C+4R) 上述网络流算法虽然可以经过全部数据，但编程复杂度很高，而且极易出错，一不小心就会由于一个小错误影响整个程序。贪婪方法的运用【方法二】贪婪方法统计一切行包含的白格数从还没有射击格的行中选出一个白格数最少的检查所选的行假设所选行的白格数为0，那么输出无解；否那么从所选行的白格中任选一个作为射击格，并将与该格同列的另一个白格所处行的白格数减1前往到第2步，直到一切的行都有射击格。假设还有列没有选射击格，那么在该列任选一白格作为射击格即可贪婪方法的运用上面的贪婪方法非常高效：时间复杂度为O(RC)，假设在程序中运用堆优化，时间复杂度将降为O(Rlog2C)

18、。空间复杂度是线性的，而且非常容易实现。如今关键的问题就是如何证明它的正确性？贪婪方法的运用【证明】用hi表示第i行的白格数。假设最开场的时候：minhi=0: 第i行曾经没有方法找到可作为射击格的白格，那么问题只能无解。minhi=1: 那么第i行的这一个白格必需求作为射击格，否那么将因第i行没有射击格而呵斥问题无解。minhi2: 那么在这一行任选一个白格，顶多只会呵斥剩余行中有一行h值为1，再处置那一行，最多也只会再呵斥剩余行中有一行h值为1，如此往复，将坚持h值为1的行数不超越1行，最后最坏的情况也是呵斥最后一行的h值为1，继续下去一切行就都已选取了射击格了。因此，假设原问题有解，该贪

19、婪方法一定能找到一种正确的方案。由此可以证明，此贪婪方法是正确的。贪婪方法的运用例题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),(

20、1,3), (2,1), (3,2),红色符号为上一次取反操作后的结果+-+-+-+-+-+-+-+-+-+-+仅剩一个“+。贪婪方法的运用讨论：能否可以用贪婪法处理此题？贪婪方法的推行贪婪与其它算法结合搜索的最优化剪枝 生日蛋糕优化动态规划 Peter的快餐店贪婪方法与解题战略最优方法不一定是最好方法想不到最优解法就用较优解法贪婪与其它算法结合例题5：Peter的快餐店贪婪与动态规划Peter最近在R市新开了一家快餐店。 该快餐店预备推出一种套餐，每套由A个汉堡、B个薯条和C个饮料组成。为了提高产量，Peter引进了N条消费线。一切消费线都可以消费汉堡、薯条和饮料，由于每条消费线一天能任务的

21、时间是有限的、不同的，而汉堡、薯条和饮料的单位消费时间又不同，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)经过对该

22、算法的时间复杂度分析，最坏的情况下时间复杂度将到达109，是相当费时的。贪婪与其它算法结合如今参与贪婪方法，用贪婪方法作预处置 ：首先计算出一天消费套数的上限值：min100 div A,100 div B,100 div C接着，用贪婪方法计算出这N条消费线可以消费的套数，并与上限比较，大于或等于那么输出上限值并退出，否那么再调用动态规划。由于贪婪方法的代价很低，这里甚至可以运用多次贪婪规范不同的贪婪方法，取其最大值。在运转动态规划的过程中，也可以每完成一阶段任务便与上限值进展比较，将贪婪思想充分融入到动态规划过程中，这样以来，便可望在动态规划完成前提早终了程序。贪婪方法小结贪婪作为一种解题

23、思绪，虽然有时无法证明它的正确性，但在无法找到其他算法的时候，不失为一种好方法。并且，贪婪与其他算法的结合，可以对其他算法起到优化作用。第三部分归纳战略归纳法的根本思想 归纳法的根本思想是经过列举少量的特殊情况，经过分析，最后找出普通的关系。从本质上讲，归纳就是经过察看一些简单而特殊的情况，最后总结出有用的结论或处理问题的有效途径。 归纳法解题的过程细心的察看；丰富的联想；继续尝试；总结归纳出结论。归纳法解题的过程归纳是种笼统，即从特殊景象中找出普通关系。由于在归纳的过程中不能够对一切的能够情况进展枚举，因此最后得到的结论还只是一种猜测(即归纳假设)。所以，严厉说来对于归纳假设还必需加以严厉的

24、证明。归纳战略解题应留意的问题：从问题的简单详细形状分析入手，目的是去寻求可以推行的普通性规律，因此应思索简单形状与普通性形状之间的联络。从简单形状中分析出来的规律特征应可以被验证是正确的，不能想当然或恣意地提出猜测，否那么归纳出来的结论是错误的，必然导致整个问题的解是错解。归纳战略的运用例题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+

25、22+32+n2=n(n+1) (2n+1)/6 但这只是经过总结归纳而得到的一种猜测，能否正确还需证明，对归纳假设的证明通常采用数学归纳法证略。归纳战略的运用例题2：假设干个正整数之和为n，其中：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 b

26、egin 输出m和n1；halt; end end; then 求2； if 2为整数 then begin 求n2； ifn2为整数andn2k then begin 输出m和n2; halt; end end;then mml; end;while归纳战略的运用上述算法从数学意义上来说，是一定可以出得出正确解的。但是该算法疏漏了一个重要条件 1k109 。假设K值超越105，上述算法不能够在限定的15秒内出解。归纳战略的运用【分析】方法二分析小数据会发现：m,n是Fibonacci数列的相邻两项。由于： n 2mnm22 1故： m2 + mn n 2 2 1又： m 2mnn2(mn)2

27、mn2n2 (mn)2(mn)nn2 故： m2mnn22(mn)2(mn)nn22 即： n2mnm22(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棋盘

28、上的任一格子中放置一个棋子，棋子每次只能往其上、下、左、右相邻方格挪动一步，求一种遍历方法，使得棋子走n2-1步遍历整个棋盘，每个方格只能被访问一次。归纳战略的运用【分析】此题很容易想到采用搜索回溯的方法去求解，即从起点位置出发，扩展其相邻四个方格的形状节点，生成一个形状树，利用深度搜索的方法求解，但这种纯搜索的方法效率太低，因此可以思索一些简单的情况时的遍历方法：归纳战略的运用【分析】当n=2时，该棋盘存在一条回路，所以恣意一点作为起点均能遍历整个棋盘，思索到当n=4,6时的情况，进而推行到n为偶数时，均可以按规律产生回路，从给定的起点开场沿着该回路均可遍历整个棋盘。归纳战略的运用【分析】再

29、思索n为奇数时的情况，先设定n=3时，棋盘可划分成5个白格和4个黑格，人工可以推出，从任一黑格出发将无法遍历整个棋盘，然后思索n=5时的情况，同样可推出，从棋盘中的任一黑格出发无法遍历整个棋盘。规律：当n为奇数时，棋子的起始位置假设满足其横坐标和纵坐标之和为奇数时即图中所示的任一黑格位置，问题将无解。归纳战略的运用 这一规律很容易可以得到验证,由于按照规那么，从任一黑格出发，必走一白格再走一黑格，所以白格数目与黑格数目应相等，而图中两者数目并不相等，如n=5时，图中共有黑格12个，白格共有13个。归纳战略的运用【总结】经过上述归纳，我们在搜索求解问题时，将会较大地提高算法效率，尤其是在一些问题

30、的无解断定时，运用归纳战略的作用将会十清楚显。归纳战略的运用例题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分割

31、； 8: 按n=8分割； end;End;分治思想假设在将规模为n的问题分成k个不同子集合的情况下，能得到k个不同的可分别求解的子问题，其中1k=n，而且在求出了这些子问题的解之后，还可找到适当的方法把它们合并成整个问题的解，那么，具备上述特性的问题可思索运用分治战略设计求解。这种设计求解的思想就是将整个问题分成假设干个小问题后分而治之。 分治思想分治(divide-and-conquer)就是“分而治之的意思，其本质就是将原问题分成n个规模较小而构造与原问题类似的子问题；然后递归地解这些子问题，最后合并其结果就得到原问题的解。其三个步骤如下；分解(Divide)：将原问题分成一系列子问题。处

32、理(Conquer)：递归地解各子问题。假设子问题足够小，那么可直接求解。合并(combine)；将子问题的结果合并成原问题的解。 分治思想问题S问题S问题SS的解问题S1问题S2问题Si问题SnS1的解S2的解Si的解Sn的解问题的分解子集解的合并子问题求解分治思想由分治法所得到的子问题与原问题具有一样的类型。假设得到的子问题相对来说还太大，那么可反复运用分治战略将这些子问题分成更小的同类型子问题，直至产生出不用进一步细分就可求解的子问题。分治求解可用一个递归过程来表示。要使分治算法效率高，关键在于如何分割？普通地，出于一种平衡原那么，总是把大问题分成K个规模尽能够相等的子问题，但也有例外，

33、如求表的最大最小元问题的算法，当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

34、输出：-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并退出过程；

35、 (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、

36、汽车油箱的容量C以升为单位每升汽油能行驶的间隔D2、出发点每升汽油价钱P和沿途油站数NN可以为零，油站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该数据表示最小费用分析 首先找到(从后向前)油价最低的加油站，显然车至该站油箱应为空，这样就可将起点至该站与该站至终点作为两段独立思索，分别求其

37、最小费用，二者之和即为总费用，这样不断分下去，假设某段只需起点与终点两个加油站时无需再分，如某一段油价最低的加油站即为起点，那么如能一次加油即到达该段终点那么最好，假设不能，那么加满油再思索油箱有油情况下的二分法，思索起点之外一切的加油站中从后往前油价最低的加油站，假设该加油站位于起点加满油后不能到达之处，那么到达该站时油箱应该为空，以该站为界将全程分为两个独立段思索，前半段为有油情况，后半段为无油情况。 第二种情况，假设该加油站处于起点加满油后能到达之处，那么将该段总路程缩短为该加油站至终点的情况，该加油站在该段路程中最廉价，假设从该站加满油仍不能到达终点，那么继续分治即可，程序被设计成一个

38、递归函数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站到

39、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：赛程问题。有