工学算法设计与分析第二章

2022-10-7计算机算法设计与分析1第二章递归与分治2022-10-7计算机算法设计与分析2递归的思想 递归(Recursion)就是通过把复杂问题分解为较简单的同一问题来求解。递归求解问题的方法通常有两步：第一步是考虑最简单的情况下该问题如何求解。第二步是考虑该问题的较复杂情况是如何由较简单的所构成的。由此得出该问题求解的方法。2022-10-7计算机算法设计与分析3Hanoi塔问题 Hanoi塔问题：有A、B、C三根柱子。A上有n个圆盘，自下而上由大到小地叠在一起。现要将A上的全部圆盘移到B上，并要求：(1)每次只能移动一个圆盘；(2)任何时刻都不允许将较大的圆盘压在较小的圆盘上；(3)圆盘只能在A、B、C三个柱子间移动。如何解决此如何解决此问题呢？问题呢？ABC2022-10-7计算机算法设计与分析4Hanoi塔问题 让我们先考虑最简单的情况：1、若没有盘子(n=0)，自然不需要做任何事情。ABC 2、若只有一个盘子，也很容易。直接把它移到B盘即可。不妨设操作Move(X,Y)将X柱上的一个盘子(最顶上的)移到Y柱上。2022-10-7计算机算法设计与分析5Hanoi塔问题 让我们先考虑最简单的情况：1、若没有盘子(n=0)，自然不需要做任何事情。ABC 2、若只有一个盘子，也很容易。直接把它移到B盘即可。不妨设操作Move(X,Y)将X柱上的一个盘子(最顶上的)移到Y柱上。即通过操作Move(A,B)即可实现。2022-10-7计算机算法设计与分析6Hanoi塔问题 现在来考虑复杂的情况，即n 1的情况。ABC 怎样将它变成怎样将它变成A柱柱上只有一个盘子，上只有一个盘子，即即n=1，呢？，呢？显然应该先将显然应该先将A柱柱上的上的n 1个盘子，个盘子，移到移到C柱上去。柱上去。2022-10-7计算机算法设计与分析7Hanoi塔问题 于是我们有了解决n 1的的策略：ABC2022-10-7计算机算法设计与分析8Hanoi塔问题 于是我们有了解决n 1的的策略：ABC(1)先将A上面n1个盘子移至C。2022-10-7计算机算法设计与分析9Hanoi塔问题 于是我们有了解决n 1的的策略：ABC(1)先将A上面n1个盘子移至C。(2)再将A上面的1个盘子移至B。2022-10-7计算机算法设计与分析10Hanoi塔问题 于是我们有了解决n 1的的策略：ABC(1)先将A上面n1个盘子移至C。(2)再将A上面的1个盘子移至B。(3)最后将C上面n1个盘子移至B。第一步和第三步的移动都必第一步和第三步的移动都必须遵守须遵守Hanoi塔移动的规则。塔移动的规则。2022-10-7计算机算法设计与分析11Hanoi塔问题 我们用Fr、To和As分别表示源柱、目标柱和辅助柱，解Hanoi塔可以描写为这样的递归过程：1、若n=0，什么也不做；最简单最简单的情况的情况 2、若n 0，则 用Hanoi的方法将Fr柱上的 n 1个盘子移到As柱上，用To柱做辅助柱；将剩下的一个盘子从Fr移到To；用Hanoi的方法将As柱上的 n 1个盘子移到To柱上，用Fr柱做辅助柱。2022-10-7计算机算法设计与分析12Hanoi塔问题 若写成C语言，解Hanoi塔可以描写为这样的递归过程：void Hanoi(int n,int Fr,int To,int As)if (n 0)Hanoi(n1,Fro,Ass,To);Move(Fro,To);Hanoi(n1,Ass,To,Fro)；当当n 0时，时，递归终止，递归终止，程序相当于程序相当于Skip语句。语句。2022-10-7计算机算法设计与分析13Hanoi塔问题 Hanoi(3,A,B,C)Hanoi(2,A,C,B);Move(A,B);Hanoi(2,C,B,A)Hanoi(1,A,B,C);Move(A,C);Hanoi(1,B,C,A)Move(A,B);Move(B,C);Hanoi(1,C,A,B);Move(C,B);Hanoi(1,A,B,C)Move(C,A);Move(A,B);Move(A,C);Move(A,B);Move(C,B);2022-10-7计算机算法设计与分析14Hanoi塔问题的时间复杂性 不难证明Hanoi塔问题的时间复杂性为O(2n)。证明：对n归纳证明移动次数move(n)=2n 1。归纳基础：当n=1，move(1)=1=21 1。归纳假设：当n k，move(n)=2n 1。归纳步骤：当n=k+1，移动次数为 move(k+1)=2(move(k)+1=2(2k 1)+1 =2k+1 1 由归纳法可知对任意的n有move(n)=2n 1。2022-10-7计算机算法设计与分析15递归的概念 简单地说，递归就是用自己来定义自己。一般地说，一个递归过程P可以表示为基语句S(不含P)和P自身的组合：P (S,P)。这样的表示包含了过程不终止的可能，因此递归算法应更准确地表述为P if B then Q else(S,P)，其中Q也不包含P，B为递归终止条件。2022-10-7计算机算法设计与分析16递归元 递归思想是将对较大规模的对象的操作归结为对较小规模的对象实施同样的操作。这种规模的变化体现在递归的参数表中的一类(一个或几个)变元上，这类变元被称之为递归元。在递归定义中递归元的变化应导致递归计算终止，即逐步变化为最简单规模的计算。在递归算法的设计中递归元是非常重要的。2022-10-7计算机算法设计与分析17常见的递归形式 除基本的递归形式外，其它常见的递归形式有四种，它们是：多变元递归；多步递归；嵌套递归；联立递归2022-10-7计算机算法设计与分析18多变元递归 多变元递归就是递归元多于一个的递归。例如，求最大公约数的辗转相除法：GCD(x,y)=y,x=0 x,y=0GCD(x y,y),x yGCD(x,y x),x 1 Fibonacci函数是一个两步的递归函数。2022-10-7计算机算法设计与分析20嵌套递归 所谓嵌套递归是指递归调用中又含有递归调用，又称为多重递归。例如Ackermann函数：y+1 x=0 A(x,y)=A(x1,1)y=0 A(x1,A(x,y1)x,y 0 Ackermann函数是一个双重的递归函数。同时它也是个二元递归。2022-10-7计算机算法设计与分析21联立递归 联立递归是同时定义几个函数，它们彼此相互调用，从而形成递归，又称间接递归。例如Hilbert图案，下面为H1，H2和H3：H1H2H32022-10-7计算机算法设计与分析22Hilbert图案 将Hi记为Ai，将Hi旋转90,180和270后的图形分别记为Bi，Ci和Di，其中一、二级曲线如下所示：A1B1C1D1A2D1A1A1B1B2C1B1B1A1C2B1C1C1D1D2A1D1D1C12022-10-7计算机算法设计与分析23Hilbert图案 于是得出这些子曲线逐级间的关系如下：Ai+1：DiAiAiBiBi+1：CiBiBiAiCi+1：BiCiCiDiDi+1：AiDiDiCi其中，箭头表示曲线移动的方向，于是便可写出画这些曲线的递归子程序。可将可将0级级的的Hilbert曲线视为曲线视为一个点。一个点。2022-10-7计算机算法设计与分析24Hilbert图案A(i)if (i 0)D(i 1);x=x h;ploting(x,y);A(i 1);y=y h;ploting(x,y);A(i 1);x=x+h;ploting(x,y);B(i 1);/*ploting(x,y)是从画笔现行坐标到坐标(x,y)画条直线。*/类似地可以写出画B、C和D的曲线的子程序。画Hilbert曲线的程序在调用A之前还应有一些初始化的工作，如计算h，移动画笔至起点等。Ai+1：DiAiAiBi 依据 有画A的子程序：2022-10-7计算机算法设计与分析25递归方法小结 递归方法是将复杂问题分解为较为简单的子问题的组合，且子问题与原问题相似。递归算法中必有一个或几个最简情况的计算(非递归分支)，若缺少或者不完备将造成递归不终止。递归算法中递归元必须随递归的进程变化到最简情况，保证导致非递归分支的计算。递归算法具有层次性，低层的解组合成高层的解。各层间最好通过参数传递来交流信息，如使用全局量，则要注意全局量的及时修订。2022-10-7计算机算法设计与分析26递归复杂性的一般形式 一般的，递归复杂性可描述为递归方程：1 n=1 af(n b)+D(n)n1f(n)=其中，a是子问题个数，表示递减方式，b是递减步长，D(n)是合成子问题的开销。显然影响f(n)的因素有：递减方式、子问题个数a，步长b、以及合成开销D(n)。我们先来看看递减方式这个因素。2022-10-7计算机算法设计与分析27递归复杂性的一般形式 一般的，递归复杂性可描述为递归方程：1 n=1 af(n b)+D(n)n1f(n)=其中，a是子问题个数，表示递减方式，b是递减步长，D(n)是合成子问题的开销。通常，递归元的递减方式有两种：1、除法，即n/b，的形式；2、减法，即n b，的形式。分治法分治法递推法递推法2022-10-7计算机算法设计与分析28分治法的时间复杂性 分析分治法，即用除法递减，的递归方程的一般情形，可得其时间复杂性函数为：f(n)=O(nk)当a D(b)时。其中，p=log ba，D(n)=nk。合并开销函数合并开销函数D(n)是是k阶的阶的。影响复杂性的主要因素：当影响复杂性的主要因素：当a D(b)时是子时是子问题个数，当问题个数，当a D(b)时是合并开销函数。时是合并开销函数。2022-10-7计算机算法设计与分析29分治法的基本思想 将一个规模为n的问题分解为a个规模较小的子问题，这些子问题互相独立并且与原问题相同。递归地求解这些子问题问题。然后将各个子问题的解合并在一起，从而得到原问题的解。影响其时间复杂性的因素是子问题的个数和合并开销函数，其中较大者起主要作用。2022-10-7计算机算法设计与分析30分治法的一般模式 Divide-and-Conquer(P)if(|P|=n0)return Adhoc(P);/若P的规模不超过阈值n0可直接求解并结束递归/divide P into smaller subinstants P1,.,Pa;for(i=1;i D(b)=2，所以有：f(n)=O(nlog24)=O(n2)。无效果！无效果！2022-10-7计算机算法设计与分析34大整数的乘法 那么我们如何去寻找效率更高的算法呢？让我们来考虑能否减少让我们来考虑能否减少子问题数目子问题数目a。我们考虑的主要途径有：1、减少子问题数目a；2、增加步长b。2022-10-7计算机算法设计与分析35大整数的乘法 设X和Y都是n位二进制整数。如果用常规的乘法计算乘积XY，其时间复杂性为O(n2)。将X和Y都分成2段，即 X=A2n/2+B,Y=C2n/2+D 将XY=AC2n+(AD+BC)2n/2+BD改成：XY=AC2n+(AB)(DC)+AC+BD)2n/2+BD 这里增加了减法和加法的运算，但是乘法运算却由4个减少为3个，即a=3了。2022-10-7计算机算法设计与分析36大整数的乘法 设X和Y都是n位二进制整数。如果用常规的乘法计算乘积XY，其时间复杂性为O(n2)。将X和Y都分成2段，即 X=A2n/2+B,Y=C2n/2+D 将XY=AC2n+(AD+BC)2n/2+BD改成：XY=AC2n+(AB)(DC)+AC+BD)2n/2+BD 这样有：f(n)=3f(n/2)+O(n)=O(nlog23)=O(n1.59)。2022-10-7计算机算法设计与分析37最接近点对问题 给定平面上n个点，在n个点组成的所有点对中，找出其中相互距离的最小一对点。此问题的简单解法是，算出每个点与其它n1 个点之间距离，再找出其中距离最小的一对点。这样做的时间复杂性为O(n2)。用分治法构造复杂性为O(nlogn)的算法。为此我们先考虑一维的情况：2022-10-7计算机算法设计与分析38一维最接近点对 设集合S为x轴上n个点，求S中最接近点对。假设用x轴上某个点m划分S为S1和S2，使得S1=xS|xm，S2=xS|xm。递归地在S1和S2中找出其最接近点对p1,p2和q1,q2，并设d=min|p2 p1|,|q2 q1|。mS1S2p1p2q1q22022-10-7计算机算法设计与分析39一维最接近点对 设集合S为x轴上n个点，求S中最接近点对。假设用x轴上某个点m划分S为S1和S2，使得S1=xS|xm，S2=xS|xm。mS1S2p1p2q1q2 易知，S中最接近点对是p1,p2或q1,q2，或 p3,q3，这里p3=maxS1，q3=minS2。p3q32022-10-7计算机算法设计与分析40一维最接近点对算法 float Cpair1(S)n=|S|;if(n m/d1=Cpair1(S1,);/求S1的最接近点对/d2=Cpair1(S2,);/求S2的最接近点对/p=maxS1;q=minS2;d=mimd1,d2,qp;return(d);最简单情况是最简单情况是S中有中有0个或个或1个点。注个点。注意这时取其最接近点对距离为意这时取其最接近点对距离为。2022-10-7计算机算法设计与分析41一维最接近点对算法复杂性 如果对S的分割不平衡的话，最坏情况是S1仅含一个点，这时算法复杂性为O(n2)。所以要采用中位数m来分割S。算法的分割步骤和合并步骤总共耗时O(n)，因此算法耗时满足递归方程f(n)=O(1)n02f(n/2)+O(n)n4 因为a=2=D(b)，可知f(n)=O(nlogn)。2022-10-7计算机算法设计与分析42平面最接近点对 对于二维的情况，即求平面最接近点对，可采用同样二分分治的思想。设平面集合S有n个点，求S中最接近点对。与一维的做法相同，将集合S分成两个部分。过x轴上某点m做直线L，划分S为S1和S2：S1=xS|xm，S2=xS|xm。2022-10-7计算机算法设计与分析43平面最接近点对LS1S2d1d2x=m 做直线L：x=m，显然m应取所有点的x坐标的中位数。分别求得S1和S2中最小距离d1和d2，令d=mind1,d2。现在需要考察S1和S2之间的最接近点对距离。如果考察S1和S2之间每个点对，其时间复杂性仍然为O(n2/4)。2022-10-7计算机算法设计与分析44平面最接近点对 但是实际上S1和S2之间的最接近点对距离却只需考察S1和S2 在L两侧距离不超过d的区域P1和P2间的点对。LS1S2d1d2x=mddP1P2 如果考察P1和P2间的所有点对，仍可能有n2/4个。那么，对P1中任意一点p，是否要考察它与P2中所有的点的距离呢？不需要！不需要！2022-10-7计算机算法设计与分析45平面最接近点对 考虑P1中的任意一点p，它若与P2中点q构成最接近点对，则其距离必定小于d。这样的点必定落在一个d2d的矩形R内。Lx=mdP1P2 那么矩形R中会有多少个点呢？是否仍有n/2个点呢？似乎不会有那么多个点吧？Why？pddR 实际上最多只能有6个点！2022-10-7计算机算法设计与分析46平面最接近点对 考虑P1中的任意一点p，它若与P2中点q构成最接近点对，则其距离必定小于d。这样的点必定落在一个d2d的矩形R内。Lx=mdP1P2 将R分成6个(d/2)(2d/3)的小矩形，每个小矩形里最多只能有一个点。Why？pddR2022-10-7计算机算法设计与分析47平面最接近点对 考虑P1中的任意一点p，它若与P2中点q构成最接近点对，则其距离必定小于d。这样的点必定落在一个d2d的矩形R内。Lx=mdP1P2 每个小矩形对角线长为5d/6。(d/2)2+(2d/3)2=25d2/36)pddR 若R中有6个以上点，则必有两点u、v在同一小矩形内，则|uv|5d/6。矛盾。2022-10-7计算机算法设计与分析48平面最接近点对 由于R中至多有6个点，即对P1中的每个点至多只需要考察P2中的6个点就可以了。Lx=mdP1P2pddR 分别将P1和P2中的点按y坐标排序；再对P1中的每个点p，考察P2中y坐标在y(p)d范围内的点(最多6个)。2022-10-7计算机算法设计与分析49平面最接近点对的算法 float Cpair2(S)n=|S|;if(n2)d=;return(d)m=S中各点x坐标中位数；构造S1和S2；d1=Cpair2(S1);d2=Cpair2(S2);dm=min(d1,d2)构造P1和P2；将P1和P2中的点按y坐标值排序；依次扫描P1中点u并计算u与P2中y(u)dm范围内的点；设dl是其中的最小距离；d=min(dm,dl);return(d);S1=p|x(p)m S2=q|mx(q)P1=p|mdm x(p)m P2=q|mx(q)m+dm2022-10-7计算机算法设计与分析50合并函数D(n)的复杂性 在算法中合并函数D(n)由以下运算构成：计算中位数m和最小值dm，需时为O(1)。将S分割为S1和S2，需时为O(n)。对P1和P2中的元素排序，在最坏情况下需时O(nlogn)。在P1和P2中找最小距离dl，需时O(n)。由此可知D(n)的时间复杂性为O(nlogn)。显然由此构造的平面最显然由此构造的平面最接近点对算法的复杂性接近点对算法的复杂性要大于要大于O(nlogn)。2022-10-7计算机算法设计与分析51算法中合并函数D的复杂性 在算法中合并函数D(n)由以下运算构成：计算中位数m和最小值dm，需时为O(1)。将S分割为S1和S2，需时为O(n)。对P1和P2中的元素排序，在最坏情况下需时O(nlogn)。在P1和P2中找最小距离dl，需时O(n)。由此可知D(n)的时间复杂性为O(nlogn)。若要将算法的时间复杂性降若要将算法的时间复杂性降到到O(nlogn)，需要将，需要将D(n)的的时间复杂性降到时间复杂性降到O(n)。怎么办？怎么办？2022-10-7计算机算法设计与分析52算法中合并函数D的复杂性 在算法中合并函数D(n)由以下运算构成：计算中位数m和最小值dm，需时为O(1)。将S分割为S1和S2，需时为O(n)。对P1和P2中的元素排序，在最坏情况下需时O(nlogn)。在P1和P2中找最小距离dl，需时O(n)。由此可知D(n)的时间复杂性为O(nlogn)。在在D(n)中，中，唯一时间复杂性超唯一时间复杂性超过过O(n)的运算就是排序的运算就是排序。2022-10-7计算机算法设计与分析53算法中合并函数D的复杂性 在算法中合并函数D(n)由以下运算构成：计算中位数m和最小值dm，需时为O(1)。将S分割为S1和S2，需时为O(n)。对P1和P2中的元素排序，在最坏情况下需时O(nlogn)。在P1和P2中找最小距离dl，需时O(n)。由此可知D(n)的时间复杂性为O(nlogn)。在在递归过程中，递归过程中，P1和和P2中的元素的顺中的元素的顺序是不变的，因此可以把序是不变的，因此可以把排序放在递归排序放在递归计算之前，而不放在递归的过程中计算之前，而不放在递归的过程中。在整个算法开始之前对各点的在整个算法开始之前对各点的y y坐标进行坐标进行一次预排序，则递归中就无须再排序。一次预排序，则递归中就无须再排序。2022-10-7计算机算法设计与分析54平面最接近点对的算法 float Cpair2(S,d)n=|S|;if(n2)d=;return(d)m=S中各点x坐标中位数；构造S1和S2；Cpair2(S1,d1);Cpair2(S2,d2);dm=min(d1,d2)构造P1和P2；将P1和P2中的点按y坐标值排序；依次扫描P1中点u并计算u与P2中y(u)dm范 围内的点；设dl是其中的最小距离；d=min(dm,dl);return(d)删去递归中的排序删去递归中的排序运算，把它拿到递运算，把它拿到递归的外面去！归的外面去！2022-10-7计算机算法设计与分析55平面最接近点对的算法 float Cpair2(S)n=|S|;if(n0时，将2k2k棋盘分割成4个2k12k1的子棋盘，如右下图所示：2k12k12k12k12k12k12k12k1 特殊方格必定位于4个子棋盘之一中。而这四个子棋盘却不一致。递归求解是将问题归结到较小规模的同一问题，这就需要将三个正常子棋盘也转化成特殊棋盘。2022-10-7计算机算法设计与分析64棋盘覆盖问题的分析 当k0时，将2k2k棋盘分割成4个2k12k1的子棋盘，如右下图所示：2k12k12k12k12k12k12k12k1 特殊方格必定位于4个子棋盘之一中。为此，可用一个L型骨牌覆盖三个正常子棋盘的会合处，如左图所示。这次覆盖后四个子棋盘都是特殊棋盘了。2022-10-7计算机算法设计与分析65棋盘覆盖的算法 棋盘覆盖(参数表)如果是单个格子，则返回；将棋盘划分成尺寸为一半的子棋盘；判断特殊方格在哪个子棋盘中，再用相应L型骨牌覆盖相应结合部，即不含特殊方格的部分在结合部的三个方格；并记下它们的位置，作为各部分的特殊方格；依次对左上角、右上角、右下角和左下角四个子棋盘进行棋盘覆盖；2022-10-7计算机算法设计与分析66棋盘覆盖算法中的参数 算法的形参表中需要的参数有：递归元：棋盘尺寸为2n。每轮递归时将n减 1，则棋盘尺寸减半；当n为0时递归终止。棋盘位置：棋盘左上角方格的行列号tr和tc。特殊方格位置：特殊方格的行列号dr和dc。参数表中应有哪些参数呢？参数表中应有哪些参数呢？递归元定义为int n 棋盘位置定义为int tr,tc。特殊方格位置定义为int dr,dc。2022-10-7计算机算法设计与分析67棋盘覆盖算法中其它变量 除了形参表中的那些参数外，棋盘覆盖程序中还需要如下的变量：表示棋盘的变量。表示L型骨牌覆盖顺序的变量。棋盘尺寸的变量。各子棋盘在结合部的方格位置。各子棋盘的特殊方格的位置。除形参外，算法中还应除形参外，算法中还应有哪些变量呢？有哪些变量呢？内部变量全局变量为什么要设这为什么要设这个变量呢？个变量呢？2022-10-7计算机算法设计与分析68棋盘覆盖算法中其它变量 棋盘定义为int Board2n2n，初值为全0。覆盖顺序变量定义为int tile，其初值为0。棋盘尺寸的变量定义为int s，其初值为2n。不设此变量也可以。但因不设此变量也可以。但因s=2n，则每轮递，则每轮递归中都要做求归中都要做求2n的幂运算。设变量的幂运算。设变量s后，只后，只需初始时计算一次需初始时计算一次s=2n，以后只要做，以后只要做s=s/2即可。这样降低了递归中的运算强度。即可。这样降低了递归中的运算强度。2022-10-7计算机算法设计与分析69棋盘覆盖算法中其它变量 棋盘定义为int Board2n2n，初值为全0。覆盖顺序变量定义为int tile，其初值为0。棋盘尺寸的变量定义为int s，其初值为2n。0132四个子棋盘的排序为四个子棋盘的排序为 结合部的方格位置定义为int jr4,jc4。各子棋盘的特殊方格的位置定义为int Sr4,Sc4。2022-10-7计算机算法设计与分析70棋盘覆盖算法中其它变量 棋盘定义为int Board2n2n，初值为全0。覆盖顺序变量定义为int tile，其初值为0。棋盘尺寸的变量定义为int s。结合部的方格位置定义为int jr4,jc4。各子棋盘的特殊方格的位置定义为int Sr4,Sc4。将棋盘覆盖程序取名为CoverBoard；2022-10-7计算机算法设计与分析71棋盘覆盖的算法 voice CoverBoard(n,tr,tc,dr,dc)if(n=0)return;n=n 1;s=s/2;tile+;Coverjoin;CoverBoard(n,tr,tc,sr0,sc0);CoverBoard(n,tr+s,tc,sr1,sc1)；CoverBoard(n,tr+s,tc+s,sr2,sc2)CoverBoard(n,tr,tc+s,sr3,sc3)若只有一个若只有一个格子，则终格子，则终止递归。止递归。注意递归元的递减是注意递归元的递减是在这里做的。在这里做的。s s是减半是减半后的子棋盘尺寸。后的子棋盘尺寸。在对结合部覆盖之前在对结合部覆盖之前将覆盖序号将覆盖序号tiletile加一。加一。2022-10-7计算机算法设计与分析72棋盘覆盖的算法 voice CoverBoard(n,tr,tc,dr,dc)if(n=0)return();n=n 1;s=s/2;tile+;Coverjoin;CoverBoard(n,tr,tc,sr0,sc0);CoverBoard(n,tr+s,tc,sr1,sc1)；CoverBoard(n,tr+s,tc+s,sr2,sc2)CoverBoard(n,tr,tc+s,sr3,sc3)Coverjoin完成以下功能：完成以下功能：1、计算结合部的方格的、计算结合部的方格的位置；位置；2、判断特殊方格位置；、判断特殊方格位置；3、覆盖子棋盘结合部并、覆盖子棋盘结合部并将四个特殊方格的位置写将四个特殊方格的位置写入入sr 和和sc。依次对四个子棋依次对四个子棋盘进行覆盖。盘进行覆盖。覆盖左上角覆盖左上角的子棋盘。的子棋盘。覆盖右上角覆盖右上角的子棋盘。的子棋盘。覆盖右下角覆盖右下角的子棋盘。的子棋盘。覆盖左下角覆盖左下角的子棋盘。的子棋盘。2022-10-7计算机算法设计与分析73棋盘覆盖的算法 voice CoverBoard(n,tr,tc,dr,dc)if(n=0)return();n=n 1;s=s/2;tile+;Coverjoin;CoverBoard(n,tr,tc,sr0,sc0);CoverBoard(n,tr+s,tc,sr1,sc1)；CoverBoard(n,tr+s,tc+s,sr2,sc2)CoverBoard(n,tr,tc+s,sr3,sc3)依次对四个子棋依次对四个子棋盘进行覆盖。盘进行覆盖。覆盖左上角覆盖左上角的的0号子棋盘。号子棋盘。覆盖右上角覆盖右上角的的1 1号子棋盘。号子棋盘。覆盖右下角覆盖右下角的的2 2号子棋盘。号子棋盘。覆盖左下角覆盖左下角的的3 3号子棋盘。号子棋盘。2022-10-7计算机算法设计与分析74Coverjoin的实现 计算结合部方格位置：判断特殊方格(dr,dc)落在那个子棋盘：覆盖结合部并确定各子棋盘特殊方格位置。2022-10-7计算机算法设计与分析75Coverjoin的实现 计算结合部方格位置：tr是0区和1区的首行，tc是0区和3区的首列;tr+s是3区和2区的首行;tc+s是1区和2区的首列0312trtcss2022-10-7计算机算法设计与分析76Coverjoin的实现 计算结合部方格位置：0312trtcss jr0=tr+s1;jc0=tc+s1;jr1=tr+s1;jc1=tc+s;jr2=tr+s;jc2=tc+s;jr3=tr+s;jc3=tc+s1;jr0=tr+s1;jc0=tc+s1jr1=tr+s1;jc1=tc+sjr2=tr+s;jc2=tc+sjr3=tr+s;jc3=tc+s12022-10-7计算机算法设计与分析77Coverjoin的实现 计算结合部方格位置：判断特殊方格(dr,dc)落在那个子棋盘：我们可以依据结合部方格的行号和列号来判断特殊方格落在哪个子棋盘中。0132trtcss jr0=tr+s1;jc0=tc+s1;jr1=tr+s;jc1=tc+s1;jr2=tr+s;jc2=tc+s;jr3=tr+s1;jc3=tc+s;2022-10-7计算机算法设计与分析78Coverjoin的实现 计算结合部方格位置：判断特殊方格(dr,dc)落在那个子棋盘：覆盖结合部并确定各子棋盘特殊方格位置。if(dr=jr0&dc=jc0)r=0 else if(dr=jc1)r=1 else if(dr=jr2&dc=jc2)r=2 else if(dr=jr3&dc=jc3)r=3;jr0=tr+s1;jc0=tc+s1;jr1=tr+s;jc1=tc+s1;jr2=tr+s;jc2=tc+s;jr3=tr+s1;jc3=tc+s;若特殊方格的行标若特殊方格的行标dr=jr0且列标且列标dc=jc0，则特殊，则特殊方格位于在方格位于在0号子棋盘中。号子棋盘中。其余类似。其余类似。r指明了这点。指明了这点。2022-10-7计算机算法设计与分析79Coverjoin的实现 覆盖结合部并确定各子棋盘特殊方格位置：if(r=0)sr0=dr;sc0=dc;Boardjrkjck=tile;srk=jrk;sck=jck;k=1,2,3 else if(r=1)sr1=dr;sc1=dc;Boardjrkjck=tile;srk=jrk;sck=jck;k=0,2,3 else if(r=2)sr2=dr;sc2=dc;Boardjrkjck=tile;srk=jrk;sck=jck;k=0,1,3 else if(r=3)sr1=dr;sc1=dc;Boardjrkjck=tile;srk=jrk;sck=jck;k=0,1,2;注意：此处由于幻灯片篇幅的原因，简写注意：此处由于幻灯片篇幅的原因，简写成这样，实际表示对于成这样，实际表示对于k=1,2,3，执行，执行Boardjrkjck=tile;srk=jrk;sck=jck;，即覆盖相应格子，并将其作为即覆盖相应格子，并将其作为对应子棋盘的特殊方格。下面亦如此。对应子棋盘的特殊方格。下面亦如此。2022-10-7计算机算法设计与分析80Coverjoin的实现 覆盖结合部并确定各子棋盘特殊方格位置也可以用如下的语句来实现：srr=dr;scr=dc;for(k=0,k 4,i+)if(kr)Boardjrkjck=tile;srk=jrk;sck=jck;特殊子棋盘的特殊方特殊子棋盘的特殊方格还是原来的。格还是原来的。对每个非特殊子棋盘，则覆盖其结合部的方对每个非特殊子棋盘，则覆盖其结合部的方格并将其作为该子棋盘的特殊方格。格并将其作为该子棋盘的特殊方格。由于这个操作可以用此简单表示，所以才在由于这个操作可以用此简单表示，所以才在上一张幻灯片上采用了简记的方式。上一张幻灯片上采用了简记的方式。2022-10-7计算机算法设计与分析81棋盘覆盖算法的主程序 main(int n,int dr,int dc)int s=2n int Boardss=0;int tile=0;CoverBoard(n,0,0,dr,dc);请同学们自己编程来请同学们自己编程来具体实现这个程序。具体实现这个程序。2022-10-7计算机算法设计与分析82棋盘覆盖算法的正确性 要证明一个算法的正确性，需要证明两点：(1)算法的部分正确性；(2)算法的终止性。下面我们用归纳法证明棋盘覆盖算法的部分正确性：2022-10-7计算机算法设计与分析83棋盘覆盖算法的部分正确性 归纳基础：k=0时，特殊棋盘仅含一个特殊方格，显然已经正确覆盖。假设对2k1的特殊棋盘均可正确覆盖。对2k的特殊棋盘，算法划分为四个2k1的子棋盘。用一块L型骨牌覆盖三个正常子棋盘的结合处后，恰形成四个2k1的特殊棋盘。由归纳假设，它们均可被正确覆盖。因而也正确覆盖了2k的特殊棋盘。由归纳法可知，棋盘覆盖算法是部分正确。2022-10-7计算机算法设计与分析84棋盘覆盖算法的终止性 算法的终止性：递归终止条件为递归元size为1时递归终止。递归元size的初值为2k。每次递归时递归元减半，即size=size/2；因此，必然在有穷步内递减为1。所以此算法必定终止。由部分正确性和终止性可知，此算法是完全正确的。2022-10-7计算机算法设计与分析85棋盘覆盖算法的复杂性 设f(k)是棋盘覆盖算法覆盖2k2k的棋盘所需要的时间，则f(k)满足如下递归方程：f(k)=O(1)k=0 4f(k1)+O(1)k0 其递归元递减方式是减法，故为递推关系。2022-10-7计算机算法设计与分析86递推递归的时间复杂性 k1 i=0=akf(1)+ai D(n ib)这里k=n/b。若递归元递减的运算为减法，即n b，则：f(n)=af(n b)+D(n)=a(af(n 2b)+D(n b)+D(n)=k1 i=0=ak+ai D(n ib)2022-10-7计算机算法设计与分析87递推递归的时间复杂性 若递归元递减的运算为减法，即n b，则：f(n)这里k=n/b。an/b=an/ab=Can，C=ab。b仅影响复杂性中的常数因子，故可忽略。若设D(n)也为常数，则有f(n)=O(an)。若D(n)不是常数，则f(n)=O(anD(n)。由此可看到D(n)对算法复杂性的影响。k1 i=0=ak+ai D(n ib)在通常情况下递推递归算法的复在通常情况下递推递归算法的复杂性视为子任务数杂性视为子任务数a的指数函数。的指数函数。2022-10-7计算机算法设计与分析88棋盘覆盖算法的复杂性 设f(k)是棋盘覆盖算法覆盖2k2k的棋盘所需要的时间，则T(k)满足如下递归方程：f(k)=O(1)k=0 4f(k1)+O(1)k0 其递归元递减方式是减法，故为递推关系。由a=4可知f(k)=O(4k)。覆盖2k2k的棋盘要用(4k1)/3个L型骨牌，故此算法是一个在渐进意义下最优的算法。2022-10-7计算机算法设计与分析89通信信道上允许传输的单词 已知在通信信道上传输的单词只能由a、b和c三个字母组成并且其中不得有两个字母a连续出现。请编写一个程序生成所有在通信信道上允许传输的长度为n的单词。将这样的单词称为长将这样的单词称为长度为度为n的合法单词。的合法单词。我们该如何来考虑编写这个程序呢？我们该如何来考虑编写这个程序呢？1、先分析最简单情况的解。2、再分析复杂情况如何由较简情况组成。2022-10-7计算机算法设计与分析90通信信道上允许传输的单词 应该是长度n=1的单词。此问题中最简单的情况是什么？此问题中最简单的情况是什么？长度为1的合法单词只有三个，即a、b和c。下面我们再考虑长度为n(n 1)的合法单词是如何由长度n 1的合法单词构成的。2022-10-7计算机算法设计与分析91通信信道上允许传输的单词 把长度为n 合法单词w去掉最前面的一个符号后所剩下的就是长度为n 1的单词w。显然w仍然应该是合法单词。如何考虑用长度如何考虑用长度n 1n 1的合法单词来构的合法单词来构成长度成长度n n的合法单词呢？的合法单词呢？于是有：w=a+wb+wc+w这里用符号+表示符号串的连接运算。2022-10-7计算机算法设计与分析92通信信道上允许传输的单词 先考虑w=a+w的情况：于是有：w=a+b+wa+c+w 因为通信信道上的合法单词中不允许出现连续的a，所以w只能以b或者c开头。于是w=b+w或者w=c+w。这里w为任意的长度为n 2的合法单词。将长度为将长度为n的合法单词命名为的合法单词命名为Legal(n)。2022-10-7计算机算法设计与分析93通信信道上允许传输的单词 先考虑w=a+w的情况：于是有：Legal(n)=a+b+Legal(n 2)a+c+Legal(n 2)因为通信信道上的合法单词中不允许出现连续的a，所以w只能以b或者c开头。于是w=b+w或者w=c+w。这里w为任意的长度为n 2的合法单词。2022-10-7计算机算法设计与分析94通信信道上允许传输的单词 再考虑w=b+w和w=c+w的情况：于是有：Legal(n)=b+Legal(n 1)c+Legal(n 1)这里的w可以为任意的长度为n 1的合法单词。2022-10-7计算机算法设计与分析95通信信道上允许传输的单词 综合起来可以得到长度为n的合法单词与长度较短的合法单词之间有如下的关系：Legal(n)=a+b+Legal(n 2)a+c+Legal(n 2)b+Legal(n 1)c+Legal(n 1)现在发生了一个新的情况！现在发生了一个新的情况！什么情况？什么情况？2022-10-7计算机算法设计与分析96通信信道上允许传输的单词 综合起来可以得到长度为n的合法单词与长度较短的合法单词之间有如下的关系：Legal(n)=a+b+Legal(n 2)a+c+Legal(n 2)b+Legal(n 1)c+Legal(n 1)这是个两步递归！可是我们只考虑了n=1这一种最简单情况！要增加要增加n=0的情况。的情况。2022-10-7计算机算法设计与分析97通信信道上允许传输的单词 综合起来可以得到长度为n的合法单词与长度较短的合法单词之间有如下的关系：Legal(n)=a+b+Legal(n 2)a+c+Legal(n 2)b+Legal(n 1)c+Legal(n 1)我们令当n=0时的合法单词为空串，即 Legal(0)=。2022-10-7计算机算法设计与分析98通信信道上允许传输的单词 综合n 为 0和1的最简单情况后，有：Legal(n)=n=0b n=1c n=1a n=1a+b+Legal(n 2)n 1a+c+Legal(n 2)n 1b+Legal(n 1)n 1c+Legal(n 1)n 12022-10-7计算机算法设计与分析99程序设计的思考 现在就让我们来设计这个程序吧！现在就让我们来设计这个程序吧！这个程序要打印出所有在通信信道上传输的长度为n的合法单词。现在你头脑里想象的打印现在你头脑里想象的打印 过程该是什么样子的呢？过程该是什么样子的呢？2022-10-7计算机算法设计与分析100程序设计的思考 现在就让我们来设计这个程序吧！现在就让我们来设计这个程序吧！这个程序要打印出所有在通信信道上传输的长度为n的合法单词。我想：这个程序应该是从左向右逐个符号地生成每一个长度为n的合法单词。每生成一个合法单词，就把它打印出去。2022-10-7计算机算法设计与分析101程序设计的思考 现在就让我们来设计这个程序吧！现在就让我们来设计这个程序吧！这个程序要打印出所有在通信信道上传输的长度为n的合法单词。我想：那么，这个程序就应该有个存放这个长度为n的合法单词的变量，就叫它wn吧。干脆把这个程序叫做Legal(w,n)好了。2022-10-7计算机算法设计与分析102程序设计的思考 现在就让我们来设计这个程序吧！现在就让我们来设计这个程序吧！这个程序要打印出所有在通信信道上传输的长度为n的合法单词。我想：那么，什么时候就该打印合法单词wn呢？那不就是n=0的时候吗？2022-10-7计算机算法设计与分析103程序设计的思考 现在就让我们来设计这个程序吧！现在就让我们来设计这个程序吧！这个程序要打印出所有在通信信道上传输的长度为n的合法单词。aha!I got it!按照递归规则，从n开始，就是从左至右，将合法的符号放进w；每放一个符号，n就减一。当n个符号全都放进去了，就是n=0了，就把w打印出去。2022-10-7计算机算法设计与分析104打印合法单词的程序 Legal(wn,int k)if(k=0)print w else if(k=1)Legal(w+a,k1);Legal(w+b,k1);Legal(w+c,k1)else Legal(w+a+b,k2);Legal(w+a+c,k2);Legal(w+b,k1);Legal(w+c,k1)main(int n)int wn=0;Legal(wn,n)考虑运算考虑运算w+x。2022-10-7计算机算法设计与分析105打印合法单词的程序 Legal(wn,int k)if(k=0)print w else if(k=1)Legal(w+a,k1);Legal(w+b,k1);Legal(w+c,k1)else Legal(w+a+b,k2);Legal(w+a+c,k2);Legal(w+b,k1);Legal(w+c,k1)main(int n)int wn=0;Legal(wn,n)w+x就是就是wnk=x。w+x+y就是就是wnk=x;wnk+1=y。2022-10-7计算机算法设计与分析106打印合法单词的程序 我们让递归元的初值为0，终止值为n，而递归元的递减方式改成加法，即n+1。于是这个程序还可改写成下面的样子：考虑到运算考虑到运算w+x的方便我们的方便我们可以改变递归的方向。可以改变递归的方向。2022-10-7计算机算法设计与分析107打印合法单词的程序 Legal(wn,int k)if(k=n)print w else if(k=n1)Legal(w+a,k+1);Legal(w+b,k+1);Legal(w+c,k+1)else Legal(w+a+b,k+2);Legal(w+a+c,k+2);Legal(w+b,k+1);Legal(w+c,k+1)main(int n)int wn=0;Legal(wn,0)k=n时递归时递归终止。终止。递归元用加递归元用加法来递减。法来递减。直接将数组直接将数组w的第的第k个分量赋值为个分量赋值为a。递归元的初递归元的初值赋为值赋为0。请同学们自己编程来请同学们自己编程来具体实现这个程序。具体实现这个程序。2022-10-7计算机算法设计与分析108打印合法单词的程序 打印长度为3的合法单词：Legal(w3,0)Legal(wab,2);Legal(wac,2);Legal(wb,1);Legal(wc,1)Legal(waba,3);Legal(wabb,3);Legal(wabc,3);aba;abb;abc;2022-10-7计算机算法设计与分析109打印合法单词的程序 打印长度为3的合法单词：Legal(w3,0)Legal(wac,2);Legal(wb,1);Legal(wc,1)Legal(waca,3);Legal(wacb,3);Legal(wacc,3);aba;abb;abc;aca;acb;acc;2022-10-7计算机算法设计与分析110打印合法单词的程序 打印长度为3的合法单词：Legal(w3,0)Legal(wb,1);Legal(wc,1)aba;abb;abc;aca;acb;acc;bab;bac;Legal(wbab,3);Legal(wbac,3);Legal(wbb,2);Legal(wbc,2);2022-10-7计算机算法设计与分析111打印合法单词的程序 打印长度为3的合法单词：Legal(w3,0)Legal(wb,1);Legal(wc,1)aba;abb;abc;aca;acb;acc;bab;bac;bba;bbb;bbc;Legal(wbb,2);Legal(wbc,2);Legal(wbba,3);Legal(wbbb,3);Legal(wbbc,3);2022-10-7计算机算法设计与分析112打印合法单词的程序 打印长度为3的合法单词：Legal(w3,0)Legal(wb,1);Legal(wc,1)aba;abb;abc;aca;acb;acc;bab;bac;bba;bbb;bbc;Legal(wbc,2);Legal(wbca,3);Legal(wbcb,3);Legal(wbcc,3);bca;bcb;bcc;2022-10-7计算机算法设计与分析113打印合法单词的程序 打印长度为3的合法单词：Legal(w3,0)Legal(wc,1)aba;abb;abc;aca;acb;acc;bab;bac;bba;bbb;bbc;bca;bcb;bcc;Legal(wcab,3);Legal(wcac,3);Legal(wcb,2);Legal(wcc,2);cab;cac;2022-10-7计算机算法设计与分析114打印合法单词的程序 打印长度为3的合法单词：Legal(w3,0)Legal(wc,1)aba;abb;abc;aca;acb;acc;bab;bac;bba;bbb;bbc;bca;bcb;bcc;Legal(wcb,2);Legal(wcc,2);cab;cac;Legal(wcba,3);Legal(wcbb,3);Legal(wcbc,3);cba;cbb;cbc;2022-10-7计算机算法设计与分析115打印合法单词的程序 打印长度为3的合法单词：Legal(w3,0)Legal(wc,1)aba;abb;abc;aca;acb;acc;bab;bac;bba;bbb;bbc;bca;bcb;bcc;Legal(wcc,2);cab;cac;Legal(wcca,3);Legal(wccb,3);Legal(wccc,3);cba;cbb;cbc;cca;ccb;ccc;程序执行完毕，上面打印的就是所有长度为3的合法单词。2022-10-7计算机算法设计与分析116算法的时间复杂性 这个算法是一个递推的递归式，并且是一个两步递归。由前面的基本分析可以断定其复杂性应该是指数的，即f(n)=O(an)。这个算法中的子任务为2，因此它的时间复杂性应该不会低于O(2n)。这个程序的时间复杂性是O(n(1+3)n)，其中打印一个单词的时间复杂性为O(n)。它的复杂性实际上取决于合法单词的数量。2022-10-7计算机算法设计与分析117通信信道上允许传输的单词 计算通信信道上允许传输的合法单词个数。解：令h(n)为的长度n的合法单词个数。由前面的讨论我们有：最简单情况时h(0)=1，h(1)=3。当n2时：h(n)=2 h(n1)+2 h(n2)求解这个递归方程可得：(2+3)23(1+3)n+h(n)=(2+3)23(13)n这个递归函数也是著这个递归函数也是著名的斐波拉契函数。名的斐波拉契函数。有趣的是，对于任意的有趣的是，对于任意的n，这，这个无理式的结果都是整数。个无理式的结果都是整数。2022-10-7计算机算法设计与分析118递归分治法总结 分治法的基本做法是：(1)考虑该问题的最简单情况的解。(2)将规模为n的原问题分解为k个规模较小的子问题。这些子问题相互独立且与原问题相同。分析子问题与原问题之间关系。(3)递归地求解这些子问题。(4)将子问题的解合并得到原问题的解。2022-10-7计算机算法设计与分析119分治递归的时间复杂性 若递归元用除法递减，则为分治递归。子问题个数a、递减步长b和合并开销函数D(n)=nk 共同影响其时间复杂性。若a D(b)，算法复杂性为O(np)，p=logba。减少子任务数量可减少算法复杂性。若a=D(b)，算法复杂性为O(np logbn)。若D(b)a，算法复杂性为D(n)=nk，降低D(n)的复杂性可降低算法的复杂性。2022-10-7计算机算法设计与分析120递推递归的算法复杂性 若递归元用减法递减，则为递推递归。递减步长b对复杂性影响很小。其复杂性子取决于子任务个数a和合并开销函数D(n)。递推算法复杂性一般为f(n)=O(anD(n)。因为an已经是指数函数了。故一般都认为递推算法复杂性为O(an)。合并开销函数D(n)会增大递推算法复杂性。2022-10-7计算机算法设计与分析121降低递归算法复杂性 降低递归算法复杂性的方法有：1、降低子任务的数量a；2、降低合并开销函数D(n)。降低合并开销函数D(n)的方法通常有：把所有递归中不变的运算都提到递归之外进行；尽可能降低递归中的运算的强度。