单击此处编辑母版标题样式,,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,,,*,,,,,,,,单击此处编辑母版标题样式,,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,,,*,基础算法策略,1,,第一部分,枚举策略,2,,枚举策略的基本思想,,枚举法，又称穷举法，指在一个有穷的可能的解的集合中，一一枚举出集合中的每一个元素，用题目给定的检验条件来判断该元素是否符合条件，若满足条件，则该元素即为问题的一个解；否则，该元素就不是该问题的解3,,枚举策略的基本思想,,枚举方法也是一种搜索算法，即对问题的所有可能解的状态集合进行一次扫描或遍历在具体的程序实现过程中，可以通过循环和条件判断语句来完成枚举法常用于解决,“,是否存在,”,或,“,有多少种可能,”,等类型的问题例如，求解不定方程的问题就可以采用列举法4,,,虽然枚举法本质上属于搜索策略，但是它与回溯法有所不同因为适用枚举法求解的问题必须满足两个条件： ⑴可预先确定每个状态的元素个数,n,；,,⑵状态元素,a,1,，,a,2,，,…,，,a,n,的可能值为一个连续的值域设,,,a,i1,—,状态元素,a,i,的最小值；,a,ik,—,状态元素,a,i,的最大值,(1≤i≤n),，即,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,输出问题的解；,,5,,枚举策略的基本思想,,,枚举法的特点是算法比较简单，在用枚举法设计算法时，重点注意优化，减少运算工作量。
将与问题有关的知识条理化、完备化、系统化，从中找出规律，减少枚举量6,,枚举方法的优化,枚举算法的时间复杂度：状态总数*单个状态的耗时,,主要优化方法：,,⑴ 减少状态总数,,⑵ 降低单个状态的考察代价,,优化过程从以下几个方面考虑：,,⑴ 枚举对象的选取,,⑵ 枚举方法的确定,,,⑶,采用局部枚举或引进其他算法,7,,枚举算法的应用,例题,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,两类数的个数8,,【,分析,】,此题是一道统计类题目解决统计问题的一个常用方法是枚举法：逐一枚举所有情况，同时进行统计，枚举结束时，统计也完成，得到结果具体对本题而言，采用枚举法的正确性与可行性是显然的，而本题的数据规模又仅为,1,～,1000,，所以采用逐一枚举方法进行统计的时间复杂度是完全可以接受的。
枚举算法的应用,9,,例题,2,：,01,统计,10,,例题,4,：圆桌骑士（,IOI,试题）,,在一个,8*8,的棋盘上，有一个国王和若干个武士其中，国王走一字步，骑士走马步若国王与骑士相会在同一点上，国王可以选择让骑士背他走求一个点，使所有的骑士和国王相距在这个点上的所走的步数最少枚举算法的应用,11,,【,分析,】,此题可从,3,个方面考虑：,,分治、枚举、数学方法由于无法将这个问题划分为各自独立的小问题来解决，分治显然是不行的又因武士和国王位置的不固定性和其走法的差异，推导不出一个数学公式因此考虑使用枚举，需要枚举的三个要点：,,,1,、最后的汇聚点2,、国王与背他的骑士的汇聚点3,、国王与背他的骑士枚举算法的应用,12,,国王最多只会与一个骑士结合，因为骑士的最终目标也是最终汇聚点，一旦国王与某个骑士汇合后，即马上可与其结合，剩下的只需要将所有的骑士汇合就可以了更没有必要在中途中有将国王托付给其他的骑士 这样我们估算一下时间为,O,（,8*8*8*8*63,）,=O,（,36*10^4,），完全可以承受另外，我们需要预先将,2,点之间走马字步的距离计算出来可以使用,Floyd,或是,Bfs,。
枚举算法的应用,13,,,算法流程：,,,,dis[x1,，,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 dis[knight[kk].x,knight[kk].y,x,y]
每两个车站最多用一条公路直接相连，从任何一个车站出发都可以经过一条或多条公路到达其他车站，但不同的路径需要花费的时间可能不同在一条路上花费的时间等于路径上所有公路需要的时间之和16,,佳佳的家在车站,1,，他有五个亲戚，分别住在车站,a,b,c,d,e,过年了，他需要从自己的家出发，拜访每个亲戚（顺序任意），给他们送去节日的祝福怎样走，才需要最少的时间？,17,,分析,这一题中的边数远小于,n2,，所以复杂度也只有,nlogn+m,,算法框架是：,,（,1,）用,5,次最短路，计算出,6,个点两两之间的距离,,（,2,）枚举,5,个结点的全排列，找到一个使得总路程长度最短的方案18,,最大子矩阵的求解方法,19,,第二部分,贪心方法,20,,贪心方法的基本思想,,贪心是一种解题策略，也是一种解题思想,,使用贪心方法需要注意局部最优与全局最优的关系，选择当前状态的局部最优并不一定能推导出问题的全局最优,,利用贪心策略解题，需要解决两个问题：,,该题是否适合于用贪心策略求解,,如何选择贪心标准，以得到问题的最优解,,21,,适用于贪心策略求解的问题的特点,,适用于贪心策略求解的问题必须具有最优子结构的性质，但并不是所有,具有,最优子结构的问题都可以用贪心策略求解。
因为贪心往往是盲目的，需要使用更理性的方法,——,动态规划（例如,“,0-1,背包问题,”,与,“,部分背包问题,”,）,,22,,贪心方法的应用,例题,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,23,,贪心方法的应用,例如,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,),24,,贪心方法的应用,【,分析,】,从题意表面上看，本题是一个求最短路径的问题，但题设中的,N,≤,100,，也就是说图中最多有,100,！个节点，采用二维关系的图结构根本无法存贮这众多的状态通过问题的本质分析，可以将问题转化为一个序列的最优转化问题25,,贪心方法的应用,采用,贪心策略,：,,每次让一个节点归位或为下一步工作做准备。
其具体步骤为：,,若序列中第一个点为,A,x,(x,≠,1),，则将第一个点和第,x,个点交换这便完成了让一个点归位的工作；,,若第一个是,A,1,，则任找一个编号与位置不相符的点，并与之交换这样下一步便可让交换到,1,号位置的点归位26,,贪心方法,的应用,(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,),的推演过程：,27,,贪心方法的应用,例题,2,：,d-,规则问题对任意给定的,m(m∈N,+,),和,n(n∈N,+,),，满足,m1,，使得,K,,a∈P,，则修改,P,为：,P=P-{y|y=s,,a,s∈N,+,},,，并称该,d,规则具有分值,a,。
现要求编制一个程序，对输入的,m,n,值，构造相应的初始集合,P,，对,P,每应用一次,d,规则就累加其相应的分值，求能得到最大累加分值的,d,规则序列，输出每次使用,d,规则时的分值和集合,p,的变化过程28,,贪心方法的应用,【,分析,】,,初看这一问题，很容易想到用贪心策略来求解，即选择集合中最大的可以删除的数开始删起，直到不能再删除为止，而且通过一些简单的例子来验证，这一贪心标准似乎也是正确的，例如，当,m=3,，,n=10,时，集合,P,＝,{3,…,10},，运用上述“贪心标准”可以得到这一问题的正确的最优解,d=5,＋,4,＋,3,＝,12,，即其,d-,规则过程如下：,,1.,a=5 P={3,4,6,7,8,9} d=5,,2.,a=4 P={3,6,7,9} d=5+4=9,,3.,a=3 p={7} d=5+4+3=12,29,,贪心方法的应用,但是，如果再仔细地分析一个例子，当,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,分值越多越好因此，本题,不能,采用纯粹的贪心策略求解30,,贪心方法的应用,【,改进,】,,将原算法基础上进行改进下面给出新的算法：,,建立集合,P={m..n},,从,n div 2,到,m,每数构造一个集合,c[i],，包含该数在,P,中的所有倍数（不包括,i,本身）,,从,n div 2,起找到第一个元素个数最少但又不为空的集合,c[i],,在,d,分值中加上,i,,把,i,及,c[i],集合从,P,集中删除，更新所有构造集合的元素,,检查所有构造集合，若还有非空集合，则继续,3,步骤，否则打印、结束,31,,贪心方法的应用,下面看,m=3, n=18,时的推演过程：,,初始,P={3..18},,找到,i=9, c[i]={18}, P={3..8,10..17},,找到,i=8, c[i]={16}, P={3..7,10..15,17},,找到,i=7, c[i]={14}, P={3..6,10..13,15,17},,找到,i=6, c[i]={12}, P={3..5,10,11,13,15,17},,找到,i=3, c[i]={15}, P={4,5,10,11,13,17},,找到,i=5, c[i]={10}, P={4,11,13,17},,到此所有构造集合全部为空，,d=9+8+7+6+3+5=38,32,,贪心方法的应用,,讨论,：,,能否证明此贪心策略是正确的？,,能否找到其他更好的算法？,33,,贪心方法的应用,例题,3,：射击竞赛,,射击的目标是一个由,R,,C(2,≤,R,≤,C,≤,1000),个小方格组成的矩形网格。
每一列恰有,2,个白色的小方格和,R-2,个黑色的小方格行从顶至底编号为,1~R,，列从左至右编号为,1~C,射击者可射击,C,次在连续的,C,次射击中，若每列恰好有一个白色的方格被射中，且不存在无白色方格被射中的行，这样的射击才是正确的如果存在正确的射击方法，则要求找到它34,,贪心方法的应用,,射击的选择有,2,C,种，符合要求的却很少要解决问题，还需从正确的射击方法的特征入手35,,贪心方法的应用,【,方法一,】,网络流算法,,我们将表示列的点编号为,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,小，则问题无解，否则我们可以先根据网络流的结果求出该二分图的具体匹配方案。
36,,贪心方法的应用,红色,的连线流量为,1,,蓝色,的连线流量为,0,,选择的射击格即为：,,(1,3), (2,1), (3,2), (4,4),S,2,1,4,3,2,1,4,3,T,列,:,行,:,源,:,汇,:,37,,贪心方法的应用,网络流算法经过优化，时间复杂度可以达到,O,(,C,,(,n,+,4C,+,4R,)),,,上述网络流算法虽然可以通过全部数据，但编程复杂度很高，而且极易出错，一不小心就会因为一个小错误影响整个程序38,,贪心方法的应用,【,方法二,】,贪心方法,,统计所有行包含的白格数,,从还没有射击格的行中选出一个白格数最少的,,检查所选的行,,若所选行的白格数为,0,，则输出无解；,,否则从所选行的白格中任选一个作为射击格，并将与该格同列的另一个白格所处行的白格数减,1,,返回到第,2,步，直到所有的行都有射击格若还有列没有选射击格，则在该列任选一白格作为射击格即可,39,,贪心方法的应用,上面的贪心方法非常高效：,,时间复杂度为,O,(,R,,C,),，如果在程序中使用堆优化，时间复杂度将降为,O,(,R,,log,2,C,),空间复杂度是线性的，而且非常容易实现。
现在关键的问题就是,——,如何证明它的正确性？,40,,贪心方法的应用,【,证明,】,,用,h[i],表示第,i,行的白格数如果最开始的时候：,,min{h[i]}=0:,第,i,行已经没有办法找到可作为射击格的白格，那么问题只能无解min{h[i]}=1:,那么第,i,行的这一个白格必须要作为射击格，否则将因第,i,行没有射击格而造成问题无解min{h[i]},≥,2:,那么在这一行任选一个白格，顶多只会造成剩余行中有一行,h,值为,1,，再处理那一行，最多也只会再造成剩余行中有一行,h,值为,1,，如此往复，将保持,h,值为,1,的行数不超过,1,行，最后最坏的情况也是造成最后一行的,h,值为,1,，继续下去所有行就都已选取了射击格了因此，如果原问题有解，该贪心方法一定能找到一种正确的方案由此可以证明，此贪心方法是正确的41,,贪心方法的应用,例题,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,个n≤20),+,+,+,+,+,-,-,+,-,42,,贪心方法的应用,一种操作组合：,,((1,1), (2,2), (3,3)),,,((1,2), (2,3), (3,1)),,,((1,1), (2,3), (3,2)),,,((1,3), (2,1), (3,2)),,,,红色,符号为上一次取反操作后的结果,+,-,+,-,+,+,+,+,+,-,-,+,-,-,+,+,+,-,-,-,-,+,-,+,+,-,-,-,-,-,-,-,-,-,-,+,-,+,-,-,-,+,+,-,+,仅剩一个“,+”,43,,贪心方法的应用,,讨论：,,是否可以用贪心法解决此题？,44,,贪心方法的推广,贪心与其它算法结合,,搜索的最优化剪枝（,,生日蛋糕）,,优化动态规划（,Peter,的快餐店）,,贪心方法与解题策略,,最优方法不一定是最好方法,,想不到最优解法就用较优解法,45,,贪心与其它算法结合,例题,5,：,Peter,的快餐店,（贪心与动态规划）,,Peter,最近在,R,市新开了一家快餐店 该快餐店准备推出一种套餐，每套由,A,个汉堡、,B,个薯条和,C,个饮料组成。
为了提高产量，,Peter,引进了,N,条生产线所有生产线都可以生产汉堡、薯条和饮料，由于每条生产线一天能工作的时间是有限的、不同的，而汉堡、薯条和饮料的单位生产时间又不同，,Peter,需要知道，怎样安排才能是一天中生产的套餐量最大假设一天中汉堡、薯条和饮料的产量均不超过,100,个，且生产线总数小于等于,10,46,,贪心与其它算法结合,【,分析,】,用,p1,、,p2,、,p3,分别表示汉堡、薯条和饮料的单位生产时间，,t[i],表示第,i,条生产线每天的生产时间，,p[i,j,k],表示用前,i,条生产线生产,j,个汉堡、,k,个薯条的情况下，最多能生产的饮料数，,r[i,j,k],表示用第,i,条生产线生产,j,个汉堡、,k,个薯条的情况下，最多能生产的饮料数，则,,p[i,j,k]=max{p[i-1,j1,k1]+r[i,j-j1,k-k1]},,((j-j1),,p1+(k-k1),,p2
因为贪心方法的代价很低，这里甚至可以使用多次贪心标准不同的贪心方法，取其最大值在运行动态规划的过程中，也可以每完成一阶段工作便与上限值进行比较，将贪心思想充分融入到动态规划过程中，这样以来，便可望在动态规划完成前提前结束程序48,,贪心方法小结,贪心作为一种解题思路，虽然有时无法证明它的正确性，但在无法找到其他算法的时候，不失为一种好方法并且，贪心与其他算法的结合，可以对其他算法起到优化作用49,,第三部分,归纳策略,50,,归纳法的基本思想,,归纳法的基本思想是通过列举少量的特殊情况，经过分析，最后找出一般的关系从本质上讲，归纳就是通过观察一些简单而特殊的情况，最后总结出有用的结论或解决问题的有效途径51,,归纳法解题,的过程,细心的观察；,,丰富的联想；,,继续尝试；,,总结归纳出结论52,,归纳法解题,的过程,归纳是,—,种抽象，即从特殊现象中找出一般关系由于在归纳的过程中不可能对所有的可能情况进行枚举，因而最后得到的结论还只是一种猜测,(,即归纳假设,),所以，严格说来对于归纳假设还必须加以严格的证明53,,归纳策略解题应注意的问题：,从问题的简单具体状态分析入手，目的是去寻求可以推广的一般性规律，因此应考虑简单状态与一般性状态之间的联系。
从简单状态中分析出来的规律特征应能够被验证是正确的，不能想当然或任意地提出猜想，否则归纳出来的结论是错误的，必然导致整个问题的解是错解54,,归纳策略的应用,例题,1,：,,求前,n,个自然数的平方之和：,,,S=1,2,+2,2,+3,2,+,……,+n,2,,55,,归纳策略的应用,【,分析,】,这本是一道很简单的题目，但如果能找出,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,,,但这只是通过总结归纳而得到的一种猜测，是否正确还需证明，对归纳假设的证明通常采用数学归纳法（证略）56,,归纳策略的应用,例题,2,：若干个正整数之和为,n,，其中：,n<2000,，试求它们乘积的最大值以及该最大值的位数,k,57,,归纳策略的应用,【,分析,】,根据数学规律可知,,,若要使和固定的数的乘积最大，必须使这些数尽可能的多为,3,，于是可推得以下规律：,,,当,N mod 3,＝,1,时，,N,可分解为一个,4,和若干个,3,的和；,,当,N mod 3,＝,2,时，,N,可分解为一个,2,和若干个,3,的和；,,当,N mod 3,＝,0,时，,N,直接分解为若干个,3,的和。
按照这一分解方法，所有因数的乘积必定最大注意,：因,N,的最大值可达,2000,，乘积将超过长整型数据范围，所以需用高精度运算58,,归纳策略的应用,例题,3,：极值问题（最高时限,15s,）,,已知,m,、,n,为整数，且满足下列两个条件：,,①,m,、,n∈1,，,2,，,…,，,K,，（,1≤K≤10,9,）,,②,(n,2,－,mn,－,m,2,),2,＝,1,,编一程序，由键盘输入,K,，求一组满足上述两个条件的,m,、,n,，并且使,m,2,＋,n,2,的值最大例如，若,K,＝,1995,，则,m,＝,987,，,n,＝,1597,，则,m,、,n,满足条件，且可使,m,2,＋,n,2,的值最大59,,归纳策略的应用,【,分析,】,方法一,,从初等数学的角度考虑：,,由条件②（,n,2,－,mn,－,m,2,）,2,＝,1,得出：,,n,2,－,mn,－,m,2,+ 1 = 0,,n,2,－,mn,－,m,2,－,1 = 0,,根据求根公式,,N1,2,＝（,m,＋△,1,2,）,/2 n3,4,＝（,m,－△,1,2,）,/2,,其中：,,△,1,＝,sqrt,（,5*m,2,＋,4,）； △,2,＝,sqrt,（,5*m,2,－,4,）；,60,,归纳策略的应用,【,分析,】,再考虑条件①。
由于,n>1,，因此排除了,n3,和,n4,存在的可能性,.,,又由于,n,和,m,是整数，因此△,1,和△,2,应为整数由于,m,2,＋,n,2,单调递增，从,m,＝,k,出发，按递减方向将,m,值代入,n,的求根公式只要△,1,（或△,2,）为整数、,n1,（或,n2,）为整数且小于,k,，则得出的一组,m,和,n,一定使,m2,＋,n2,的值最大61,,【,算法描述,】,,,m←k,；,,while m≥i do begin,,,求△,1,,if △1,为整数,then begin,,,求,n1,；,,,if (n1,为整数,) and (n1≤k),,Then begin,输出,m,和,n1,；,halt; end,,end;,｛,then,｝,,求△,2,；,,,if △2,为整数,then begin,,,求,n2,；,,,if,（,n2,为整数）,and,（,n2≤k,）,,,then begin,输出,m,和,n2; halt; end,,end;{then},,m←m,－,l;,,end;{while},62,,归纳策略的应用,上述算法从数学意义上来说，是一定可以出得出正确解的。
但是该算法疏漏了一个重要条件 ──,1≤k≤10,9,,如果,K,值超过,10,5,，上述算法不可能在限定的,15,秒内出解63,,归纳策略的应用,【,分析,】,方法二,,分析小数据会发现：,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,64,,归纳策略的应用,【,分析,】,由上述数学变换式可以得出，如果,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,的值最大65,,归纳策略的应用,例题,4,：,“,王,”,棋子遍历问题题目大意：在,n×n,格（,2,＜＝,n<=20,）棋盘上的任一格子中放置一个棋子，棋子每次只能往其上、下、左、右相邻方格移动一步，求一种遍历方法，使得棋子走,n,2,-1,步遍历整个棋盘，每个方格只能被访问一次66,,归纳策略的应用,【,分析,】,此题很容易想到采用搜索回溯的方法去求解，即从起点位置出发，扩展其相邻四个方格的状态节点，生成一个状态树，利用深度搜索的方法求解，但这种纯搜索的方法效率太低，因此可以考虑一些简单的情况时的遍历方法：,67,,归纳策略的应用,【,分析,】,当,n=2,时，该棋盘存在一条回路，所以任意一点作为起点均能遍历整个棋盘，考虑到当,n=4,6,时的情况，进而推广到,n,为偶数时，均可以按规律产生回路，从给定的起点开始沿着该回路均可遍历整个棋盘68,,归纳策略的应用,【,分析,】,再考虑,n,为奇数时的情况，先设定,n=3,时，棋盘可划分成,5,个白格和,4,个黑格，人工可以推出，从任一黑格出发将无法遍历整个棋盘，然后考虑,n=5,时的情况，同样可推出，从棋盘中的任一黑格出发无法遍历整个棋盘。
规律,：,当,n,为奇数时，棋子的起始位置若满足其横坐标和纵坐标之和为奇数时（即图中所示的任一黑格位置），问题将无解69,,归纳策略的应用,,这一规律很容易能够得到验证,,,因为按照规则，从任一黑格出发，必走一白格再走一黑格，所以白格数目与黑格数目应相等，而图中两者数目并不相等，如,n=5,时，图中共有黑格,12,个，白格共有,13,个70,,归纳策略的应用,【,总结,】,通过上述归纳，我们在搜索求解问题时，将会较大地提高算法效率，尤其是在一些问题的无解判定时，运用归纳策略的作用将会十分明显71,,归纳策略的应用,例题,5,：,Kathy,函数,(HNCOI),,Tiger,非常喜欢数学，所以他参加了学校组织的数学课外兴趣小组在兴趣小组的学习当中，老师向,Tiger,介绍了,Kathy,函数，,Kathy,函数是这样定义的：,,,72,,归纳策略的应用,例题,5,：,Kathy,函数,(HNCOI),,Tiger,对,Kathy,函数产生了浓厚的兴趣，他通过研究发现有很多的数,n,都满足,,对于一个给定的数,m,，他希望你求出所有的满足 的自然数,n,的个数，其中,m<=10,100,。
73,,第四部分,递归与分治策略,74,,递归的概念与应用,一个函数、过程、概念或数学结构，如果在其定义或说明内部又直接或间接地出现有其本身的引用，则称它们是递归的或者是递归定义的在程序设计中，过程或函数直接或者间接调用自己，就被称为递归调用75,,递归的概念与应用,递归过程是借助于一个递归工作栈来实现的,,问题向一极推进，这一过程叫做递推；,,而问题逐一解决，最后回到原问题，这一过程叫做回归递归的过程正是由递推和回归两个过程组成76,,递归的概念与应用,采用递归方法编写的问题解决程序具有结构清晰，可读性强等优点，且递归算法的设计比非递归算法的设计往往要容易一些，所以当问题本身是递归定义的，或者问题所涉及到的数据结构是递归定义的，或者是问题的解决方法是递归形式的时候，往往采用递归算法来解决77,,递归的概念与应用,例题,1,：,钢板分割问题设有一块正方形的钢板，现需将它分成,n,个小正方形例如，当：,,n=2,不可能有解n=3,不可能有解n=4,可分成,4,个小正方形钢板n=5,不可能有解n=6,即一个大的加五个小的n=7,即三个较大的加四个小的n=8,即一个大的加七个小的问题为任给,n,，求出分成,n,个小正方形的方法。
78,,递归的概念与应用,【,分析,】,经过分析就可以得出：,,（,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,，,,由此可以得出如下的递归算法：,79,,递归的概念与应用,procedure devide(i:integer);,,Begin,,if n>8 then begin,,,分解成四小块；,,对于其中一块,devide(n-3),,end,,else,,case n of,,6:,按,n=6,分割；,,,7:,按,n=7,分割；,,,8:,按,n=8,分割；,,,end;,,End;,80,,分治思想,如果在将规模为,n,的问题分成,k,个不同子集合的情况下，能得到,k,个不同的可分别求解的子问题，其中,1,＜,k,＜,=n,，而且在求出了这些子问题的解之后，还可找到适当的方法把它们合并成整个问题的解，那么，具备上述特性的问题可考虑使用分治策略设计求解。
这种设计求解的思想就是将整个问题分成若干个小问题后分而治之81,,分治思想,分治,(divide-and-conquer),就是,“,分而治之,”,的意思，其实质就是将原问题分成,n,个规模较小而结构与原问题相似的子问题；然后递归地解这些子问题，最后合并其结果就得到原问题的解其三个步骤如下；,,分解,(Divide),：将原问题分成一系列子问题解决,(Conquer),：递归地解各子问题若子问题足够小，则可直接求解合并,(combine),；将子问题的结果合并成原问题的解82,,分治思想,问题,S,问题,S,问题,S,S,的解,问题,S1,……,问题,S,2,问题,S,i,问题,Sn,……,S,1,的解,……,S,2,的解,S,i,的解,S,n,的解,……,问题的分解,子集解的合并,子问题求解,83,,分治思想,由分治法所得到的子问题与原问题具有相同的类型如果得到的子问题相对来说还太大，则可反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生出不用进一步细分就可求解的子问题分治求解可用一个递归过程来表示要使分治算法效率高，关键在于如何分割？一般地，出于一种平衡原则，总是把大问题分成,K,个规模尽可能相等的子问题，但也有例外，如求表的最大最小元问题的算法，当,n,＝,6,时，等分定量成两个规模为,3,的子表,L1,和,L2,不是最佳分割。
84,,分治的应用举例,例题,2,：,一元三次方程求解,,有形如：,ax3+bx2+cx+d=0,这样的一个一元三次方程给出该方程中各项的系数,(a,，,b,，,c,，,d,均为实数,),，并约定该方程存在三个不同实根,(,根的范围在,-100,至,100,之间,),，且根与根之差的绝对值,>=1,要求由小到大依次在同一行输出这三个实根,(,根与根之间留有空格,),，并精确到小数点后,4,位提示：记方程,f(x)=ax3+bx2+cx+d,，若存在,2,个数,x1,和,x2,，且,x1
加上本题的提示给我们以启迪：采用二分法逐渐缩小根的范围，从而得到根的某精度的数值具体方法如下：,86,,分治的应用举例,A,、当已知区间,(a,b),内有一个根时，用二分法求根，若区间,(a,b),内有根，则必有,f(a),·,f(b)<0,重复执行如下的过程：,,,(1),若,a+0.0001>b,或,f((a+b)/2)=0,，则可确定根为,(a+b)/2,并退出过程；,,,(2),若,f(a)* f((a+b)/2)<0,，则由题目给出的定理可知根在区间,(a,(a+b)/2),中，故对区间重复该过程；,,,(3),若,f(a)* f((a+b)/2)>0,，则必然有,f((a+b)/2)* f(b)<0,，根在,((a+b)/2,b),中，对此区间重复该过程执行完毕，就可以得到精确到,0.0001,的根87,,分治的应用举例,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,中所述的二分法迅速出找出解如此可求出方程的所有的解88,,分治的应用举例,例题,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,（该数据表示最小费用）,89,,分析,,首先找到,(,从后向前,),油价最低的加油站，显然车至该站油箱应为空，这样就可将起点至该站与该站至终点作为两段独立考虑，分别求其最小费用，二者之和即为总费用，这样一直分下去，若某段只有起点与终点两个加油站时无需再分，如某一段油价最低的加油站即为起点，则如能一次加油即到达该段终点则最好，若不能，则加满油再考虑油箱有油情况下的二分法，考虑起点之外所有的加油站中从后往前油价最低的加油站，若该加油站位于起点加满油后不能到达之处，则到达该站时油箱应该为空，以该站为界将全程分为两个独立段考虑，前半段为有油情况，后半段为无油情况。
90,,第二种情况，若该加油站处于起点加满油后能到达之处，则将该段总路程缩短为该加油站至终点的情况，该加油站在该段路程中最便宜，若从该站加满油仍不能到达终点，则继续分治即可，程序被设计成一个递归函数,money,，形式参数,start,表示起点站，形式参数,stop,表示终点站，形式参数,rest,表示到达加油站,start,时汽车油箱余下的油的容量，,money,函数最终计算出从加油站,start,到,stop,区间内的最小费用91,,function money (start,，,stop:longint,；,rest:real):real,；,,Var k,：,longint,；,,begin,,if stop-starl=1,,then money:=((d[stop]-d[star1])/d2-rest)*p[start],,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 d[stop]-d[start]<=d2*c {,在起点加满油能直接到达该段终点,},,then money:=((d[stop]-d[start])/d2-rest) * p[start],,else begin,,k:=minp(start+1 , stop-1) ;,,if d[k] - d[start] <= d2 * c then {,在起点加满油能到达加油站,k},,money:=(c-rest) * p[start] + money(k, stop, c-(d[k] - d[start])/d2),,else,,money := money(start, k, rest) + money( k, stop, O),,end,,end,,end;,92,,分治的应用举例,例题,4,：赛程问题。
有,n,个编号为,1,到,n,的运动员参加某项运动的单循环比赛，即每个运动员要和所有其他运动员进行一次比赛试为这,n,个运动员安排一个比赛日程，使得每个运动员每天只进行一场比赛，且整个比赛在,n-1,天内结束输入运动员人数,n,（,n<=10000,），输出一个,n,阶方阵,A[1..N,0..N-1],，当,J,＞,0,时，,A[I,J],表示第,I,名运动员在第,J,天的比赛对手93,,,由于,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,个运动员，即若有,A[I,J]=K,，则,A[K,，,J]=I,因此原问题的解,(,一个,N,阶方阵,),可以由分解后的两个子问题的解，合并起来。
同时每一个子问题又可以按照上述的二分法分解下去，直至每个组中仅有,2,个运动员时为止94,,procedure arrangment(K,N:integer);,,{,从,K,号运动员起的共,N,员运动员单循环比赛日程表的过程,},,begin,,if n=2 then {,处理只有,2,名运动员的情况，递归终止条件,},,begin,,A[K,0]:=K;A[K,1]:=K+1;,,A[K+1,0]:=K+1; A[K+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 {,合并子问题的解,,,构造原问题的解,A[I,J]},,for J:=(N div 2) to N-1 do,,A[I,J]:=A[I+(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,,A[I,J]:=A[I-(N div 2),J-(N div 2)];,,end;,,end;,95,,分治的应用举例,例题,5,：求,“,逆序对,”,。
给定一整数数组,A=(A,1,,A,2,,,…,A,n,),,若,iA,j,,,则,,就为一个逆序对例如数组（,3,，,1,，,4,，,5,，,2,）的逆序对有,,,,,问题是，输入,n,和,A,数组，统计逆序对数目1<=n<=30000,96,,分析,原始的解决方案,（,双重循环）,,C:=0;,,For i:=1 to n -1 do,,for j:=i+1 to n do,,if a[i]>a[j] then c:=c+1;,,时间复杂度为,O(n,2,),97,,分析,采用二分法求解,:,,记数列,a[st,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),表示一个数取自,A[st,mid],,令一个数取自,A[mid+1,ed],的逆序对数目98,,分析,若要求计算,d,值的同时数列,A,已排序，设,I,j,指针分别已排序的,A[st,med),和,A(mid+1,ed),中的一个元素，若满足：,,A[mid+1],,…,A[j-1],均小于,A[i],,但,A[j]>A[i],,则,j-mid-1,必须计入,F,，顺序移动,I,j,指针即可完成合并。