《算法设计与分析递归与分治(第二章)课件.ppt》由会员分享，可在线阅读，更多相关《算法设计与分析递归与分治(第二章)课件.ppt（75页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第二章递归与分治1/10/20231计算机算法设计与分析递归的思想递归(Recursion)就是通过把复杂问题分解为较简单的同一问题来求解。递归求解问题的方法通常有两步：第一步是考虑最简单的情况下该问题如何求解。第二步是考虑该问题的较复杂情况是如何由较简单的所构成的。由此得出该问题求解的方法。1/10/20232计算机算法设计与分析Hanoi塔问题Hanoi塔问题：有A、B、C三根柱子。A上有n个圆盘，自下而上由大到小地叠在一起。现要将A上的全部圆盘移到B上，并要求：(1)每次只能移动一个圆盘；(2)任何时刻都不允许将较大的圆盘压在较小的圆盘上；(3)圆盘只能在A、B、C三个柱子间移动。如何解
2、决此如何解决此问题呢？问题呢？ABC1/10/20233计算机算法设计与分析Hanoi塔问题让我们先考虑最简单的情况：1、若没有盘子(n=0)，自然不需要做任何事情。ABC2、若只有一个盘子，也很容易。直接把它移到B盘即可。不妨设操作Move(X,Y)将X柱上的一个盘子(最顶上的)移到Y柱上。1/10/20234计算机算法设计与分析Hanoi塔问题让我们先考虑最简单的情况：1、若没有盘子(n=0)，自然不需要做任何事情。ABC2、若只有一个盘子，也很容易。直接把它移到B盘即可。不妨设操作Move(X,Y)将X柱上的一个盘子(最顶上的)移到Y柱上。即通过操作Move(A,B)即可实现。1/10/
3、20235计算机算法设计与分析Hanoi塔问题现在来考虑复杂的情况，即n 1的情况。ABC怎样将它变成怎样将它变成A柱柱上只有一个盘子，上只有一个盘子，即即n=1，呢？，呢？显然应该先将显然应该先将A柱柱上的上的n 1个盘子，个盘子，移到移到C柱上去。柱上去。1/10/20236计算机算法设计与分析Hanoi塔问题于是我们有了解决n 1的的策略：ABC1/10/20237计算机算法设计与分析Hanoi塔问题于是我们有了解决n 1的的策略：ABC(1)先将A上面n1个盘子移至C。1/10/20238计算机算法设计与分析Hanoi塔问题于是我们有了解决n 1的的策略：ABC(1)先将A上面n1个盘
4、子移至C。(2)再将A上面的1个盘子移至B。1/10/20239计算机算法设计与分析Hanoi塔问题于是我们有了解决n 1的的策略：ABC(1)先将A上面n1个盘子移至C。(2)再将A上面的1个盘子移至B。(3)最后将C上面n1个盘子移至B。第一步和第三步的移动都必第一步和第三步的移动都必须遵守须遵守Hanoi塔移动的规则。塔移动的规则。1/10/202310计算机算法设计与分析Hanoi塔问题我们用Fr、To和As分别表示源柱、目标柱和辅助柱，解Hanoi塔可以描写为这样的递归过程：1、若n=0，什么也不做；最简单最简单的情况的情况2、若n 0，则用Hanoi的方法将Fr柱上的 n 1个盘子
5、移到As柱上，用To柱做辅助柱；将剩下的一个盘子从Fr移到To；用Hanoi的方法将As柱上的 n 1个盘子移到To柱上，用Fr柱做辅助柱。1/10/202311计算机算法设计与分析Hanoi塔问题若写成java语言，解Hanoi塔可以描写为这样的递归过程：void Hanoi(int n,int Fr,int To,int As)if (n 0)Hanoi(n1,Fr,As,To);Move(Fr,To);Hanoi(n1,As,To,Fr)；当当n 0时，时，递归终止。递归终止。1/10/202312计算机算法设计与分析Hanoi塔问题Hanoi(3,A,B,C)Hanoi(2,A,C,B
6、);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);1/10/202313计算机算法设计与分析Hanoi塔问题的时间复杂性不难证明Hanoi塔问题的时间复杂性为O(2n)。证明：对n归纳证明移动次数move(n)=2n 1。归纳基础：当n=1，move(1)=1=21 1。归纳假设：当n k，move(
7、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。1/10/202314计算机算法设计与分析递归元递归思想是将对较大规模的对象的操作归结为对较小规模的对象实施同样的操作。这种规模的变化体现在递归的参数表中的一类(一个或几个)变元上，这类变元被称之为递归元。在递归定义中递归元的变化应导致递归计算终止，即逐步变化为最简单规模的计算。在递归算法的设计中递归元是非常重要的。1/10/202315计算机算法设计与分析常见的递归形式除基本的递归形式外，其它常见的递归形式有四种，
8、它们是：多变元递归；多步递归；嵌套递归；联立递归1/10/202316计算机算法设计与分析多变元递归多变元递归就是递归元多于一个的递归。例如，求最大公约数的辗转相除法：GCD(x,y)=y,x=0 x,y=0GCD(x y,y),x yGCD(x,y x),x 1Fibonacci函数是一个两步的递归函数。1/10/202318计算机算法设计与分析嵌套递归所谓嵌套递归是指递归调用中又含有递归调用，又称为多重递归。例如Ackermann函数：y+1 x=0 A(x,y)=A(x1,1)y=0 A(x1,A(x,y1)x,y 0Ackermann函数是一个双重的递归函数。同时它也是个二元递归。1/
9、10/202319计算机算法设计与分析联立递归联立递归是同时定义几个函数，它们彼此相互调用，从而形成递归，又称间接递归。例如Hilbert图案，下面为H1，H2和H3：H1H2H31/10/202320计算机算法设计与分析Hilbert图案将Hi记为Ai，将Hi旋转90,180和270后的图形分别记为Bi，Ci和Di，其中一、二级曲线如下所示：A1B1C1D1A2D1A1A1B1B2C1B1B1A1C2B1C1C1D1D2A1D1D1C11/10/202321计算机算法设计与分析Hilbert图案于是得出这些子曲线逐级间的关系如下：Ai+1：DiAiAiBiBi+1：CiBiBiAiCi+1：
10、BiCiCiDiDi+1：AiDiDiCi其中，箭头表示曲线移动的方向，于是便可写出画这些曲线的递归子程序。可将可将0级的级的Hilbert曲曲线视为一线视为一个点。个点。1/10/202322计算机算法设计与分析Hilbert图案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之前还应有一些初始化的工作，
11、如计算h，移动画笔至起点等。Ai+1：DiAiAiBi依据 有画A的子程序：1/10/202323计算机算法设计与分析递归方法小结递归方法是将复杂问题分解为较为简单的子问题的组合，且子问题与原问题相似。递归算法中必有一个或几个最简情况的计算(非递归分支)，若缺少或者不完备将造成递归不终止。递归算法中递归元必须随递归的进程变化到最简情况，保证导致非递归分支的计算。递归算法具有层次性，低层的解组合成高层的解。各层间最好通过参数传递来交流信息，如使用全局量，则要注意全局量的及时修订。1/10/202324计算机算法设计与分析递归复杂性的一般形式一般的，递归复杂性可描述为递归方程：1 n=1 af(n
12、 b)+D(n)n1f(n)=其中，a是子问题个数，表示递减方式，b是递减步长，D(n)是合成子问题的开销。显然影响f(n)的因素有：递减方式、子问题个数a，步长b、以及合成开销D(n)。我们先来看看递减方式这个因素。1/10/202325计算机算法设计与分析递归复杂性的一般形式一般的，递归复杂性可描述为递归方程：1 n=1 af(n b)+D(n)n1f(n)=其中，a是子问题个数，表示递减方式，b是递减步长，D(n)是合成子问题的开销。通常，递归元的递减方式有两种：1、除法，即n/b，的形式；2、减法，即n b，的形式。分治法分治法递推法递推法1/10/202326计算机算法设计与分析分治
13、法的时间复杂性分析分治法，即用除法递减，的递归方程的一般情形，可得其时间复杂性函数为：f(n)=O(nk)当a D(b)时。其中，p=log ba，D(n)=nk。合并开销函数合并开销函数D(n)是是k阶的阶的。影响复杂性的主要因素：影响复杂性的主要因素：当当a D(b)时是子时是子问题个数，问题个数，当当a D(b)时是合并开销函数。时是合并开销函数。1/10/202327计算机算法设计与分析分治法的基本思想将一个规模为n的问题分解为a个规模较小的子问题，这些子问题互相独立并且与原问题相同。递归地求解这些子问题问题。然后将各个子问题的解合并在一起，从而得到原问题的解。影响其时间复杂性的因素是
14、子问题的个数和合并开销函数，其中较大者起主要作用。1/10/202328计算机算法设计与分析分治法的一般模式Divide-and-Conquer(P)if(|P|=n0)return Adhoc(P);/若P的规模不超过阈值n0可直接求解并结束递归/divide P into smaller subinstants P1,.,Pa;for(i=1;i=a;i+)/逐个求子问题解yi/yi=Divide-and-Conquer(Pi);return Merge(y1,ya);/返回P的解/Merge(y1,ya)将子问题解合成P的解/1/10/202329计算机算法设计与分析最接近点对问题给定平
15、面上n个点，在n个点组成的所有点对中，找出其中相互距离的最小一对点。此问题的简单解法是，算出每个点与其它n1 个点之间距离，再找出其中距离最小的一对点。这样做的时间复杂性为O(n2)。用分治法构造一个复杂性为O(nlogn)的算法。为此我们先考虑一维的情况：1/10/202330计算机算法设计与分析一维最接近点对设集合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|。mS1S2p1p2q1q21/10/202331计算机算法
16、设计与分析一维最接近点对设集合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。p3q31/10/202332计算机算法设计与分析一维最接近点对算法float Cpair1(S)n=|S|;if(n m/d1=Cpair1(S1);/求S1的最接近点对/d2=Cpair1(S2);/求S2的最接近点对/p=maxS1;q=minS2;d=mind1,d2,qp;return(d);最简单情况是最简单情况
17、是S中有中有0个或个或1个点个点。注。注意这时取其最接近点对距离为意这时取其最接近点对距离为。1/10/202333计算机算法设计与分析一维最接近点对算法复杂性如果对S的分割不平衡的话，最坏情况是S1仅含一个点，这时算法复杂性为O(n2)。所以要采用中位数m来分割S。算法的分割步骤和合并步骤总共耗时O(n)，因此算法耗时满足递归方程f(n)=O(1)n42f(n/2)+O(n)n4因为a=2=D(b)，可知f(n)=O(nlogn)。1/10/202334计算机算法设计与分析平面最接近点对对于二维的情况，即求平面最接近点对，可采用同样二分分治的思想。设平面集合S有n个点，求S中最接近点对。与一
18、维的做法相同，将集合S分成两个部分。过x轴上某点m做直线L，划分S为S1和S2：S1=xS|xm，S2=xS|xm。1/10/202335计算机算法设计与分析平面最接近点对LS1S2d1d2x=m做直线L：x=m，显然m应取所有点的x坐标的中位数。分别求得S1和S2中最小距离d1和d2，令d=mind1,d2。现在需要考察S1和S2之间的最接近点对距离。如果考察S1和S2之间每个点对，其时间复杂性仍然为O(n2/4)。1/10/202336计算机算法设计与分析平面最接近点对但是实际上S1和S2之间的最接近点对距离却只需考察S1和S2 在L两侧距离不超过d的区域P1和P2间的点对。LS1S2d1
19、d2x=mddP1P2如果考察P1和P2间的所有点对，仍可能有n2/4个。那么，对P1中任意一点p，是否要考察它与P2中所有的点的距离呢？不需要！不需要！1/10/202337计算机算法设计与分析平面最接近点对考虑P1中的任意一点p，它若与P2中点q构成最接近点对，则其距离必定小于d。这样的点必定落在一个d2d的矩形R内。Lx=mdP1P2那么矩形R中会有多少个点呢？是否仍有n/2个点呢？似乎不会有那么多个点吧？Why？pddR实际上最多只能有6个点！1/10/202338计算机算法设计与分析平面最接近点对考虑P1中的任意一点p，它若与P2中点q构成最接近点对，则其距离必定小于d。这样的点必定
20、落在一个d2d的矩形R内。Lx=mdP1P2将R分成6个(d/2)(2d/3)的小矩形，每个小矩形里最多只能有一个点。Why？pddR1/10/202339计算机算法设计与分析平面最接近点对考虑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。矛盾。1/10/202340计算机算法设计与分析平面最接近点对由于R中至多有6个点，即对P1中的每个点至多只需要考察P2中
21、的6个点就可以了。Lx=mdP1P2pddR分别将P1和P2中的点按y坐标排序；再对P1中的每个点p，考察P2中y坐标在y(p)d范围内的点(最多6个)。1/10/202341计算机算法设计与分析平面最接近点对的算法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
22、=p|x(p)m S2=q|mx(q)P1=p|mdm x(p)m P2=q|mx(q)m+dm1/10/202342计算机算法设计与分析合并函数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)。1/10/202343计算机算法设计与分析算法中合并函数
23、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)。怎么办？怎么办？1/10/202344计算机算法设计与分析算法中合并函数D的复杂性在算法中合并函数D(n)由以下运算构成：计算中位数m和最小值dm，需时为O(1)。将S分割为S1和S2
24、，需时为O(n)。对P1和P2中的元素排序，在最坏情况下需时O(nlogn)。在P1和P2中找最小距离dl，需时O(n)。由此可知D(n)的时间复杂性为O(nlogn)。在在D(n)中，中，唯一时间复杂性超唯一时间复杂性超过过O(n)的运算就是排序的运算就是排序。1/10/202345计算机算法设计与分析算法中合并函数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)
25、。在递归过程中，在递归过程中，P1和和P2中的元素的顺中的元素的顺序是不变的，因此可以把排序放在递归序是不变的，因此可以把排序放在递归计算之前，而不放在递归的过程中计算之前，而不放在递归的过程中。在整个算法开始之前对各点的在整个算法开始之前对各点的y y坐标进行坐标进行一次预排序，则递归中就无须再排序。一次预排序，则递归中就无须再排序。1/10/202346计算机算法设计与分析平面最接近点对的算法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,
26、d2)构造P1和P2；将P1和P2中的点按y坐标值排序；依次扫描P1中点u并计算u与P2中y(u)dm范 围内的点；设dl是其中的最小距离；d=min(dm,dl);return(d)删去递归中的排序删去递归中的排序运算，把它拿到递运算，把它拿到递归的外面去！归的外面去！1/10/202347计算机算法设计与分析平面最接近点对的算法float Cpair2(S)n=|S|;if(n0时，将2k2k棋盘分割成4个2k12k1的子棋盘，如右下图所示：2k12k12k12k12k12k12k12k1特殊方格必定位于4个子棋盘之一中。而这四个子棋盘却不一致。递归求解是将问题归结到较小规模的同一问题，这
27、就需要将三个正常子棋盘也转化成特殊棋盘。1/10/202353计算机算法设计与分析棋盘覆盖问题的分析当k0时，将2k2k棋盘分割成4个2k12k1的子棋盘，如右下图所示：2k12k12k12k12k12k12k12k1特殊方格必定位于4个子棋盘之一中。为此，可用一个L型骨牌覆盖三个正常子棋盘的会合处，如左图所示。这次覆盖后四个子棋盘都是特殊棋盘了。1/10/202354计算机算法设计与分析棋盘覆盖的算法棋盘覆盖(参数表)如果是单个格子，则返回；将棋盘划分成尺寸为一半的子棋盘；判断特殊方格在哪个子棋盘中，再用相应L型骨牌覆盖相应结合部，即不含特殊方格的部分在结合部的三个方格；并记下它们的位置，作
28、为各部分的特殊方格；依次对左上角、右上角、右下角和左下角四个子棋盘进行棋盘覆盖；1/10/202355计算机算法设计与分析棋盘覆盖算法中的参数算法的形参表中需要的参数有：递归元：棋盘尺寸为2n。每轮递归时将n减 1，则棋盘尺寸减半；当n为0时递归终止。棋盘位置：棋盘左上角方格的行列号tr和tc。特殊方格位置：特殊方格的行列号dr和dc。参数表中应有哪些参数呢？参数表中应有哪些参数呢？递归元定义为int n棋盘位置定义为int tr,tc。特殊方格位置定义为int dr,dc。1/10/202356计算机算法设计与分析棋盘覆盖算法中其它变量除了形参表中的那些参数外，棋盘覆盖程序中还需要如下的变量
29、：表示棋盘的变量。表示L型骨牌覆盖顺序的变量。棋盘尺寸的变量。各子棋盘在结合部的方格位置。各子棋盘的特殊方格的位置。除形参外，算法中还应除形参外，算法中还应有哪些变量呢？有哪些变量呢？内部变量全局变量为什么要设这为什么要设这个变量呢？个变量呢？1/10/202357计算机算法设计与分析棋盘覆盖算法中其它变量棋盘定义为int Board2n2n，初值为全0。覆盖顺序变量定义为int tile，其初值为0。棋盘尺寸的变量定义为int s，其初值为2n。不设此变量也可以。但因不设此变量也可以。但因s=2n，则每轮递，则每轮递归中都要做求归中都要做求2n的幂运算。设变量的幂运算。设变量s后，只后，只需
30、初始时计算一次需初始时计算一次s=2n，以后只要做，以后只要做s=s/2即可。这样降低了递归中的运算强度。即可。这样降低了递归中的运算强度。1/10/202358计算机算法设计与分析棋盘覆盖算法中其它变量棋盘定义为int Board2n2n，初值为全0。覆盖顺序变量定义为int tile，其初值为0。棋盘尺寸的变量定义为int s，其初值为2n。0132四个子棋盘的排序为四个子棋盘的排序为结合部的方格位置定义为int jr4,jc4。各子棋盘的特殊方格的位置定义为int Sr4,Sc4。1/10/202359计算机算法设计与分析棋盘覆盖算法中其它变量棋盘定义为int Board2n2n，初值为
31、全0。覆盖顺序变量定义为int tile，其初值为0。棋盘尺寸的变量定义为int s。结合部的方格位置定义为int jr4,jc4。各子棋盘的特殊方格的位置定义为int Sr4,Sc4。将棋盘覆盖程序取名为CoverBoard；1/10/202360计算机算法设计与分析棋盘覆盖的算法void 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,tc+s,sr1,sc1)；CoverBoard(n,tr+s,tc+s,sr2
32、,sc2)CoverBoard(n,tr+s,tc,sr3,sc3)若只有一个若只有一个格子，则终格子，则终止递归。止递归。注意递归元的递减是在注意递归元的递减是在这里做的。这里做的。s s是减半后是减半后的子棋盘尺寸。的子棋盘尺寸。在对结合部覆盖之前在对结合部覆盖之前将覆盖序号将覆盖序号tiletile加一。加一。1/10/202361计算机算法设计与分析棋盘覆盖的算法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);CoverBoa
33、rd(n,tr,tc+s,sr1,sc1)；CoverBoard(n,tr+s,tc+s,sr2,sc2)CoverBoard(n,tr+s,tc,sr3,sc3)Coverjoin完成以下功能：完成以下功能：1、计算结合部的方格的、计算结合部的方格的位置；位置；2、判断特殊方格位置；、判断特殊方格位置；3、覆盖子棋盘结合部并、覆盖子棋盘结合部并将四个特殊方格的位置写将四个特殊方格的位置写入入sr 和和sc。依次对四个子棋依次对四个子棋盘进行覆盖。盘进行覆盖。覆盖左上角覆盖左上角的子棋盘。的子棋盘。覆盖右上角覆盖右上角的子棋盘。的子棋盘。覆盖右下角覆盖右下角的子棋盘。的子棋盘。覆盖左下角覆盖左
34、下角的子棋盘。的子棋盘。1/10/202362计算机算法设计与分析Coverjoin的实现计算结合部方格位置：判断特殊方格(dr,dc)落在那个子棋盘：覆盖结合部并确定各子棋盘特殊方格位置。1/10/202363计算机算法设计与分析Coverjoin的实现计算结合部方格位置：tr是0区和1区的首行，tc是0区和3区的首列;tr+s是3区和2区的首行;tc+s是1区和2区的首列0312trtcss1/10/202364计算机算法设计与分析Coverjoin的实现计算结合部方格位置：0312trtcssjr0=tr+s1;jc0=tc+s1;jr1=tr+s1;jc1=tc+s;jr2=tr+s;
35、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+s11/10/202365计算机算法设计与分析Coverjoin的实现计算结合部方格位置：判断特殊方格(dr,dc)落在那个子棋盘：我们可以依据结合部方格的行号和列号来判断特殊方格落在哪个子棋盘中。0132trtcssjr0=tr+s1;jc0=tc+s1;jr1=tr+s;jc1=tc+s1;jr2=tr+s;jc2=tc+s;jr3=tr+s1;jc3=tc+s;1/10/202366计算机算法设
36、计与分析Coverjoin的实现计算结合部方格位置：判断特殊方格(dr,dc)落在那个子棋盘：覆盖结合部并确定各子棋盘特殊方格位置。if(dr=jr0&dc=jc0)r=0else if(dr=jc1)r=1else if(dr=jr2&dc=jc2)r=2else 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号子号子棋盘中。其余类似。棋盘中
37、。其余类似。r指明指明了这点。了这点。1/10/202367计算机算法设计与分析Coverjoin的实现覆盖结合部并确定各子棋盘特殊方格位置：if(r=0)sr0=dr;sc0=dc;Boardjrkjck=tile;srk=jrk;sck=jck;k=1,2,3 elseif(r=1)sr1=dr;sc1=dc;Boardjrkjck=tile;srk=jrk;sck=jck;k=0,2,3 elseif(r=2)sr2=dr;sc2=dc;Boardjrkjck=tile;srk=jrk;sck=jck;k=0,1,3 elseif(r=3)sr1=dr;sc1=dc;Boardjrkjc
38、k=tile;srk=jrk;sck=jck;k=0,1,2;注意：此处由于幻灯片篇幅的原因，简写注意：此处由于幻灯片篇幅的原因，简写成这样，实际表示对于成这样，实际表示对于k=1,2,3，执行，执行Boardjrkjck=tile;srk=jrk;sck=jck;，即覆盖相应格子，并将其即覆盖相应格子，并将其作为对应子棋盘的特殊方格。下面亦如此。作为对应子棋盘的特殊方格。下面亦如此。1/10/202368计算机算法设计与分析Coverjoin的实现覆盖结合部并确定各子棋盘特殊方格位置也可以用如下的语句来实现：srr=dr;scr=dc;for(k=0,k 4,i+)if(kr)Boardjr
39、kjck=tile;srk=jrk;sck=jck;特殊子棋盘的特殊方特殊子棋盘的特殊方格还是原来的。格还是原来的。对每个非特殊子棋盘，则覆盖其结合部的方对每个非特殊子棋盘，则覆盖其结合部的方格并将其作为该子棋盘的特殊方格。格并将其作为该子棋盘的特殊方格。由于这个操作可以用此简单表示，所以才在由于这个操作可以用此简单表示，所以才在上一张幻灯片上采用了简记的方式。上一张幻灯片上采用了简记的方式。1/10/202369计算机算法设计与分析棋盘覆盖算法的主程序main(int n,int dr,int dc)int s=2n int Boardss=0;int tile=0;CoverBoard(n
40、,0,0,dr,dc);请同学们自己编程来请同学们自己编程来具体实现这个程序。具体实现这个程序。1/10/202370计算机算法设计与分析棋盘覆盖算法的正确性要证明一个算法的正确性，需要证明两点：(1)算法的部分正确性；(2)算法的终止性。下面我们用归纳法证明棋盘覆盖算法的部分正确性：1/10/202371计算机算法设计与分析棋盘覆盖算法的部分正确性归纳基础：k=0时，特殊棋盘仅含一个特殊方格，显然已经正确覆盖。假设对2k1的特殊棋盘均可正确覆盖。对2k的特殊棋盘，算法划分为四个2k1的子棋盘。用一块L型骨牌覆盖三个正常子棋盘的结合处后，恰形成四个2k1的特殊棋盘。由归纳假设，它们均可被正确覆
41、盖。因而也正确覆盖了2k的特殊棋盘。由归纳法可知，棋盘覆盖算法是部分正确。1/10/202372计算机算法设计与分析棋盘覆盖算法的终止性算法的终止性：递归终止条件为递归元size为1时递归终止。递归元size的初值为2k。每次递归时递归元减半，即size=size/2；因此，必然在有穷步内递减为1。所以此算法必定终止。由部分正确性和终止性可知，此算法是完全正确的。1/10/202373计算机算法设计与分析棋盘覆盖算法的复杂性设f(k)是棋盘覆盖算法覆盖2k2k的棋盘所需要的时间，则f(k)满足如下递归方程：f(k)=O(1)k=0 4f(k1)+O(1)k0其递归元递减方式是减法，故为递推关系。1/10/202374计算机算法设计与分析棋盘覆盖算法的复杂性设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型骨牌，故此算法是一个在渐进意义下最优的算法。1/10/202375计算机算法设计与分析