[工学]算法设计与分析第二章.ppt

2019/4/14,计算机算法设计与分析,1,第二章 递归与分治,2019/4/14,计算机算法设计与分析,2,递归的思想,递归(Recursion)就是通过把复杂问题分解为较简单的同一问题来求解。 递归求解问题的方法通常有两步： 第一步是考虑最简单的情况下该问题如何求解。 第二步是考虑该问题的较复杂情况是如何由较简单的所构成的。 由此得出该问题求解的方法。,2019/4/14,计算机算法设计与分析,3,Hanoi塔问题,Hanoi塔问题：有A、B、C三根柱子。A上有n个圆盘，自下而上由大到小地叠在一起。,现要将A上的全部圆盘移到B上，并要求： (1)每次只能移动一个圆盘； (2)任何时刻都不允许将较大的圆盘压在较小的圆盘上； (3)圆盘只能在A、B、C三个柱子间移动。,如何解决此问题呢？,2019/4/14,计算机算法设计与分析,4,Hanoi塔问题,让我们先考虑最简单的情况： 1、若没有盘子(n = 0)，自然不需要做任何事情。,2、若只有一个盘子，也很容易。直接把它移到B盘即可。,不妨设操作Move(X, Y)将X柱上的一个盘子(最顶上的)移到Y柱上。,2019/4/14,计算机算法设计与分析,5,Hanoi塔问题,让我们先考虑最简单的情况： 1、若没有盘子(n=0)，自然不需要做任何事情。,2、若只有一个盘子，也很容易。直接把它移到B盘即可。,不妨设操作Move(X, Y)将X柱上的一个盘子(最顶上的)移到Y柱上。,即通过操作Move(A, B)即可实现。,2019/4/14,计算机算法设计与分析,6,Hanoi塔问题,现在来考虑复杂的情况，即n 1的情况。,怎样将它变成A柱上只有一个盘子，即n = 1，呢？,显然应该先将A柱上的n 1个盘子，移到C柱上去。,2019/4/14,计算机算法设计与分析,7,Hanoi塔问题,于是我们有了解决n 1的的策略：,2019/4/14,计算机算法设计与分析,8,Hanoi塔问题,于是我们有了解决n 1的的策略：,(1)先将A上面n1个盘子移至C。,2019/4/14,计算机算法设计与分析,9,Hanoi塔问题,于是我们有了解决n 1的的策略：,(1)先将A上面n1个盘子移至C。,(2)再将A上面的1个盘子移至B。,2019/4/14,计算机算法设计与分析,10,Hanoi塔问题,于是我们有了解决n 1的的策略：,(1)先将A上面n1个盘子移至C。,(2)再将A上面的1个盘子移至B。,(3)最后将C上面n1个盘子移至B。,2019/4/14,计算机算法设计与分析,11,Hanoi塔问题,我们用Fr、To和As分别表示源柱、目标柱和辅助柱，解Hanoi塔可以描写为这样的递归过程： 1、若n = 0，什么也不做；,最简单的情况,2、若n 0，则 用Hanoi的方法将Fr柱上的 n 1个盘子移到As柱上，用To柱做辅助柱； 将剩下的一个盘子从Fr移到To； 用Hanoi的方法将As柱上的 n 1个盘子移到To柱上，用Fr柱做辅助柱。,2019/4/14,计算机算法设计与分析,12,Hanoi塔问题,若写成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语句。,2019/4/14,计算机算法设计与分析,13,Hanoi塔问题,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);,2019/4/14,计算机算法设计与分析,14,Hanoi塔问题的时间复杂性,不难证明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。,2019/4/14,计算机算法设计与分析,15,递归的概念,简单地说，递归就是用自己来定义自己。,一般地说，一个递归过程P可以表示为基语句S(不含P)和P自身的组合： P (S, P)。,这样的表示包含了过程不终止的可能，因此递归算法应更准确地表述为 P if B then Q else (S, P)， 其中Q也不包含P，B为递归终止条件。,2019/4/14,计算机算法设计与分析,16,递归元,递归思想是将对较大规模的对象的操作归结为对较小规模的对象实施同样的操作。 这种规模的变化体现在递归的参数表中的一类(一个或几个)变元上，这类变元被称之为递归元。 在递归定义中递归元的变化应导致递归计算终止，即逐步变化为最简单规模的计算。 在递归算法的设计中递归元是非常重要的。,2019/4/14,计算机算法设计与分析,17,常见的递归形式,除基本的递归形式外，其它常见的递归形式有四种，它们是：,多变元递归； 多步递归； 嵌套递归； 联立递归,2019/4/14,计算机算法设计与分析,18,多变元递归,多变元递归就是递归元多于一个的递归。 例如，求最大公约数的辗转相除法：,其中x和y都是递归元。,最简单的情况有两种,2019/4/14,计算机算法设计与分析,19,多步递归,若递归函数f(x, y)，其中y是递归元，不仅与f(x, y1)有关，而且与f(x, y2)，乃至f(x, 0)有关，则称为多步递归。 例如Fibonacci函数：,Fibonacci函数是一个两步的递归函数。,2019/4/14,计算机算法设计与分析,20,嵌套递归,所谓嵌套递归是指递归调用中又含有递归调用，又称为多重递归。 例如Ackermann函数：,Ackermann函数是一个双重的递归函数。同时它也是个二元递归。,2019/4/14,计算机算法设计与分析,21,联立递归,联立递归是同时定义几个函数，它们彼此相互调用，从而形成递归，又称间接递归。 例如Hilbert图案，下面为H1，H2和H3：,2019/4/14,计算机算法设计与分析,22,Hilbert图案,将Hi记为Ai，将Hi旋转90, 180和270后的图形分别记为Bi，Ci和Di，其中一、二级曲线如下所示：,A1,B1,C1,D1,A2,D1,A1,A1,B1,B2,C1,B1,B1,A1,C2,B1,C1,C1,D1,D2,A1,D1,D1,C1,2019/4/14,计算机算法设计与分析,23,Hilbert图案,于是得出这些子曲线逐级间的关系如下：,其中，箭头表示曲线移动的方向，,于是便可写出画这些曲线的递归子程序。,可将0级的Hilbert曲线视为一个点。,2019/4/14,计算机算法设计与分析,24,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之前还应有一些初始化的工作，如计算h，移动画笔至起点等。,2019/4/14,计算机算法设计与分析,25,递归方法小结,递归方法是将复杂问题分解为较为简单的子问题的组合，且子问题与原问题相似。 递归算法中必有一个或几个最简情况的计算(非递归分支)，若缺少或者不完备将造成递归不终止。 递归算法中递归元必须随递归的进程变化到最简情况，保证导致非递归分支的计算。 递归算法具有层次性，低层的解组合成高层的解。各层间最好通过参数传递来交流信息，如使用全局量，则要注意全局量的及时修订。,2019/4/14,计算机算法设计与分析,26,递归复杂性的一般形式,一般的，递归复杂性可描述为递归方程：,其中，a是子问题个数， 表示递减方式， b是递减步长， D(n)是合成子问题的开销。,显然影响f(n)的因素有：递减方式、子问题个数a ，步长b、以及合成开销D(n) 。 我们先来看看递减方式这个因素。,2019/4/14,计算机算法设计与分析,27,递归复杂性的一般形式,一般的，递归复杂性可描述为递归方程：,其中，a是子问题个数， 表示递减方式， b是递减步长， D(n)是合成子问题的开销。,通常，递归元的递减方式有两种：,1、除法，即n / b，的形式； 2、减法，即n b，的形式。,分治法,递推法,2019/4/14,计算机算法设计与分析,28,分治法的时间复杂性,分析分治法，即用除法递减，的递归方程的一般情形，可得其时间复杂性函数为：,合并开销函数D(n)是k阶的 。,影响复杂性的主要因素：当a D(b)时是子问题个数，当a D(b)时是合并开销函数。,2019/4/14,计算机算法设计与分析,29,分治法的基本思想,将一个规模为n的问题分解为a个规模较小的子问题，这些子问题互相独立并且与原问题相同。 递归地求解这些子问题问题。 然后将各个子问题的解合并在一起，从而得到原问题的解。 影响其时间复杂性的因素是子问题的个数和合并开销函数，其中较大者起主要作用。,2019/4/14,计算机算法设计与分析,30,分治法的一般模式,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的解/,2019/4/14,计算机算法设计与分析,31,大整数的乘法,大整数是指至少数百位以上的数字。这种数字的计算无法直接用程序设计语言中的基本数据类型来表示，也无法用程序设计语言中的运算来实现。 对于大整数的运算需要用另外的数据结构来表示，需要用专门的运算程序来实现。 大整数的运算有着很重要的用途，特别是在密码学中是必不可少的。,2019/4/14,计算机算法设计与分析,32,大整数的乘法,设X和Y都是n位二进制整数。如果用常规的乘法计算乘积XY，其时间复杂性为O(n2)。,将X和Y都分成2段，即 X = A2n/2 + B, Y = C2n/2 + D,于是: XY = (A2n/2 + B)(C2n/2 + D) = AC2n +(AD+BC)2n/2 + BD,这样子问题数a = 4，步长b =2，于是有： f(n) = 4f(n/2) + O(n)。,2019/4/14,计算机算法设计与分析,33,大整数的乘法,设X和Y都是n位的二进制整数。若用常规的乘法计算乘积XY，其时间复杂性为O(n2)。,将X和Y都分成2段，即 X = A2n/2 + B, Y = C2n/2 + D,于是: XY = (A2n/2 + B)(C2n/2 + D) = AC2n +(AD+BC)2n/2 + BD,因为a = 4 D(b) = 2，所以有： f(n) = O(nlog24) = O(n2)。,无效果！,2019/4/14,计算机算法设计与分析,34,大整数的乘法,那么我们如何去寻找效率更高的算法呢？,让我们来考虑能否减少子问题数目a。,我们考虑的主要途径有： 1、减少子问题数目a； 2、增加步长b。,2019/4/14,计算机算法设计与分析,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了。,2019/4/14,计算机算法设计与分析,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)。,2019/4/14,计算机算法设计与分析,37,最接近点对问题,给定平面上n个点，在n个点组成的所有点对中，找出其中相互距离的最小一对点。 此问题的简单解法是，算出每个点与其它n1 个点之间距离，再找出其中距离最小的一对点。这样做的时间复杂性为O(n2)。 用分治法构造复杂性为O(nlogn)的算法。 为此我们先考虑一维的情况：,2019/4/14,计算机算法设计与分析,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|。,2019/4/14,计算机算法设计与分析,39,一维最接近点对,设集合S为x轴上n个点，求S中最接近点对。 假设用x轴上某个点m划分S为S1和S2，使得S1=xS | xm，S2=xS | xm。,易知，S中最接近点对是p1, p2或q1, q2，或 p3, q3，这里p3=maxS1，q3 =minS2。,2019/4/14,计算机算法设计与分析,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个点。注意这时取其最接近点对距离为。,2019/4/14,计算机算法设计与分析,41,一维最接近点对算法复杂性,如果对S的分割不平衡的话，最坏情况是S1仅含一个点，这时算法复杂性为O(n2)。 所以要采用中位数m来分割S。 算法的分割步骤和合并步骤总共耗时O(n)，因此算法耗时满足递归方程,因为a = 2 = D(b)，可知f(n) = O(nlogn)。,2019/4/14,计算机算法设计与分析,42,平面最接近点对,对于二维的情况，即求平面最接近点对，可采用同样二分分治的思想。,设平面集合S有n个点，求S中最接近点对。 与一维的做法相同，将集合S分成两个部分。 过x轴上某点m做直线L，划分S为S1和S2：S1=xS | xm，S2=xS | xm。,2019/4/14,计算机算法设计与分析,43,平面最接近点对,L,S1,S2,x=m,做直线L：x = m，显然m应取所有点的x坐标的中位数。分别求得S1和S2中最小距离d1和d2，令d = mind1, d2。,现在需要考察S1和S2之间的最接近点对距离。,如果考察S1和S2之间每个点对，其时间复杂性仍然为O(n2/4)。,2019/4/14,计算机算法设计与分析,44,平面最接近点对,但是实际上S1和S2之间的最接近点对距离却只需考察S1和S2 在L两侧距离不超过d的区域P1和P2间的点对。,L,S1,S2,x=m,d,d,P1,P2,如果考察P1和P2间的所有点对，仍可能有n2/4个。,那么，对P1中任意一点p，是否要考察它与P2中所有的点的距离呢？,不需要！,2019/4/14,计算机算法设计与分析,45,平面最接近点对,考虑P1中的任意一点p，它若与P2中点q构成最接近点对，则其距离必定小于d。这样的点必定落在一个d2d的矩形R内。,L,x=m,d,P1,P2,那么矩形R中会有多少个点呢？是否仍有n/2个点呢？,似乎不会有那么多个点吧？,Why？,p,d,d,R,实际上最多只能有6个点！,2019/4/14,计算机算法设计与分析,46,平面最接近点对,考虑P1中的任意一点p，它若与P2中点q构成最接近点对，则其距离必定小于d。这样的点必定落在一个d2d的矩形R内。,L,x=m,d,P1,P2,将R分成6个(d/2)(2d/3)的小矩形，每个小矩形里最多只能有一个点。,Why？,p,d,d,R,2019/4/14,计算机算法设计与分析,47,平面最接近点对,考虑P1中的任意一点p，它若与P2中点q构成最接近点对，则其距离必定小于d。这样的点必定落在一个d2d的矩形R内。,L,x=m,d,P1,P2,每个小矩形对角线长为5d/6。(d/2)2+(2d/3)2=25d2/36),p,d,d,R,若R中有6个以上点，则必有两点u、v在同一小矩形内， 则|uv|5d/6。矛盾。,2019/4/14,计算机算法设计与分析,48,平面最接近点对,由于R中至多有6个点，即对P1中的每个点至多只需要考察P2中的6个点就可以了。,L,x=m,d,P1,P2,p,d,d,R,分别将P1和P2中的点按y坐标排序；再对P1中的每个点p，考察P2中y坐标在y(p)d范围内的点(最多6个)。,2019/4/14,计算机算法设计与分析,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|mdmx(p)m P2=q|mx(q)m+dm,2019/4/14,计算机算法设计与分析,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)。,2019/4/14,计算机算法设计与分析,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)。,怎么办？,2019/4/14,计算机算法设计与分析,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)的运算就是排序。,2019/4/14,计算机算法设计与分析,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坐标进行一次预排序，则递归中就无须再排序。,2019/4/14,计算机算法设计与分析,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),删去递归中的排序运算，把它拿到递归的外面去！,2019/4/14,计算机算法设计与分析,55,平面最接近点对的算法,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中点u并计算u与P2中y(u)dm范 围内的点；设dl是其中的最小距离； d = min(dm, dl); return(d),这个递归中没有排序运算了。为此需要增加一个主程序。在主程序中来完成对点按y坐标的排序。,2019/4/14,计算机算法设计与分析,56,平面最接近点对的算法,为此，构造主程序： float Nearestpair(S) Sort-by-y(S); d = Cpair2(S); ruturn(d); ,主程序中先对S中的点按照y坐标进行预排序，然后调用递归程序Cpair2(S) 。这样在递归程序中就无需排序了。,对S中点按y坐标进行排序。,2019/4/14,计算机算法设计与分析,57,最接近点对的算法复杂性,修改后的递归程序Cpair2(S) 中的合并函数D(n)的复杂性为O(n)，子问题个数a为2，递减步长b为2。由a = D(b) = b 可知递归程序Cpair2(S)的时间复杂性为O(nlogn)。 主程序中预排序需时为O(nlogn)。 从而整个算法需时为O(nlogn) + O(nlogn)。因而平面最接近点对的算法时间复杂性仍然为O(nlogn)。,2019/4/14,计算机算法设计与分析,58,三维空间最接近点对,求三维空间点集合S中最接近点对的距离。 求解的方法类似求平面问题的算法。,与求平面问题中不同处是：将S分割为S1和S2两个部分的x = m是平面，而非直线。 与求平面问题中一样，分别求出S1、S2和它们之间的最近点对；再取其最小者。,2019/4/14,计算机算法设计与分析,59,三维空间最接近点对,求三维空间点集合S中最接近点对的距离。 求解的方法类似求平面问题的算法。,求S1和S2之间的最近点对时同样只考察md的区间P1和P2。 对P1中的点p，考察P2中pyd或pzd范围内的点。考察范围是立方体d2d2d，其中点数不超过常数。,P1,P2,S2,是多少？请同学们自己去考虑。,请同学们自己去求解此问题，并在明天的实验课上编程实现。,2019/4/14,计算机算法设计与分析,60,三维空间最接近点对,求三维空间点集合S中最接近点对的距离。 可用类似求平面最接近点对的算法求解。 用平面x = m将S分为S1和S2两个部分。,在求S1和S2之间的最接近点对时考虑的是d2d2d的立方体。该立方体内的点的数目不超过一常数(当然不再是6)。,此算法的时间复杂性仍然是O(nlogn)。,2019/4/14,计算机算法设计与分析,61,棋盘覆盖问题,一个2k2k特殊棋盘是其中含有一个特殊方格的棋盘，左下图为k=2的一个特殊棋盘。,现在任给定一个2k2k特殊棋盘，要用右下图所示的L型骨牌来无重叠的覆盖它。,在2k2k的棋盘覆盖中要用到(4k1)/3个L型骨牌。,2019/4/14,计算机算法设计与分析,62,棋盘覆盖问题,让我们先来考虑最简单的情况：,什么是最简单的情况？,最简单情况是k = 0。这时棋盘有2020 = 1个格子，即只有一个特殊格子。 这时棋盘已被完全覆盖，无须再做什么了。 下面我们来考虑复杂情况是怎样由较简单情况构成的。,2019/4/14,计算机算法设计与分析,63,棋盘覆盖问题的分析,当k0时，将2k2k棋盘分割成4个2k12k1的子棋盘，如右下图所示：,特殊方格必定位于4个子棋盘之一中。,而这四个子棋盘却不一致。递归求解是将问题归结到较小规模的同一问题，这就需要将三个正常子棋盘也转化成特殊棋盘。,2019/4/14,计算机算法设计与分析,64,棋盘覆盖问题的分析,当k0时，将2k2k棋盘分割成4个2k12k1的子棋盘，如右下图所示：,特殊方格必定位于4个子棋盘之一中。,为此，可用一个L型骨牌覆盖三个正常子棋盘的会合处，如左图所示。,这次覆盖后四个子棋盘都是特殊棋盘了。,2019/4/14,计算机算法设计与分析,65,棋盘覆盖的算法,棋盘覆盖(参数表) 如果是单个格子，则返回； 将棋盘划分成尺寸为一半的子棋盘； 判断特殊方格在哪个子棋盘中，再用相应L型骨牌覆盖相应结合部，即不含特殊方格的部分在结合部的三个方格；并记下它们的位置，作为各部分的特殊方格； 依次对左上角、右上角、右下角和左下角四个子棋盘进行棋盘覆盖；,2019/4/14,计算机算法设计与分析,66,棋盘覆盖算法中的参数,算法的形参表中需要的参数有： 递归元：棋盘尺寸为2n。每轮递归时将n减 1，则棋盘尺寸减半；当n为0时递归终止。 棋盘位置：棋盘左上角方格的行列号tr和tc。 特殊方格位置：特殊方格的行列号dr和dc。,参数表中应有哪些参数呢？,递归元定义为int n 棋盘位置定义为int tr, tc。 特殊方格位置定义为int dr, dc。,2019/4/14,计算机算法设计与分析,67,棋盘覆盖算法中其它变量,除了形参表中的那些参数外，棋盘覆盖程序中还需要如下的变量： 表示棋盘的变量。 表示L型骨牌覆盖顺序的变量。 棋盘尺寸的变量。 各子棋盘在结合部的方格位置。 各子棋盘的特殊方格的位置。,除形参外，算法中还应 有哪些变量呢？,为什么要设这个变量呢？,2019/4/14,计算机算法设计与分析,68,棋盘覆盖算法中其它变量,棋盘定义为int Board2n2n，初值为全0。 覆盖顺序变量定义为int tile，其初值为0。 棋盘尺寸的变量定义为int s，其初值为2n。,不设此变量也可以。但因s = 2n，则每轮递归中都要做求2n的幂运算。设变量s后，只需初始时计算一次s = 2n，以后只要做s = s/2即可。这样降低了递归中的运算强度。,2019/4/14,计算机算法设计与分析,69,棋盘覆盖算法中其它变量,棋盘定义为int Board2n2n，初值为全0。 覆盖顺序变量定义为int tile，其初值为0。 棋盘尺寸的变量定义为int s，其初值为2n。,四个子棋盘的排序为,结合部的方格位置定义为int jr4, jc4。 各子棋盘的特殊方格的位置定义为int Sr4, Sc4。,2019/4/14,计算机算法设计与分析,70,棋盘覆盖算法中其它变量,棋盘定义为int Board2n2n，初值为全0。 覆盖顺序变量定义为int tile，其初值为0。 棋盘尺寸的变量定义为int s。 结合部的方格位置定义为int jr4, jc4。 各子棋盘的特殊方格的位置定义为int Sr4, Sc4。,将棋盘覆盖程序取名为CoverBoard；,2019/4/14,计算机算法设计与分析,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是减半后的子棋盘尺寸。,在对结合部覆盖之前将覆盖序号tile加一。,2019/4/14,计算机算法设计与分析,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 。,依次对四个子棋盘进行覆盖。,覆盖左上角的子棋盘。,覆盖右上角的子棋盘。,覆盖右下角的子棋盘。,覆盖左下角的子棋盘。,2019/4/14,计算机算法设计与分析,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号子棋盘。,覆盖右下角的2号子棋盘。,覆盖左下角的3号子棋盘。,2019/4/14,计算机算法设计与分析,74,Coverjoin的实现,计算结合部方格位置：,判断特殊方格(dr, dc)落在那个子棋盘：,覆盖结合部并确定各子棋盘特殊方格位置。,2019/4/14,计算机算法设计与分析,75,Coverjoin的实现,计算结合部方格位置：,tr是0区和1区的首行，tc是0区和3区的首列; tr+s是3区和2区的首行; tc+s是1区和2区的首列,tr,tc,2019/4/14,计算机算法设计与分析,76,Coverjoin的实现,计算结合部方格位置：,tr,tc,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+s1,jr1= tr+s1; jc1=tc+s,jr2=tr+s; jc2=tc+s,jr3 =tr+s; jc3=tc+s1,2019/4/14,计算机算法设计与分析,77,Coverjoin的实现,计算结合部方格位置：,判断特殊方格(dr, dc)落在那个子棋盘：,我们可以依据结合部方格的行号和列号来判断特殊方格落在哪个子棋盘中。,tr,tc,jr0=tr+s1; jc0=tc+s1; jr1= tr+s; jc1=tc+s1; jr2=tr+s; jc2=tc+s; jr3 =tr+s1; jc3=tc+s;,2019/4/14,计算机算法设计与分析,78,Coverjoin的实现,计算结合部方格位置：,判断特殊方格(dr, dc)落在那个子棋盘：,覆盖结合部并确定各子棋盘特殊方格位置。,if (dr=jc1) r=1 else if (dr =jr2,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指明了这点。,2019/4/14,计算机算法设计与分析,79,Coverjoin的实现,覆盖结合部并确定各子棋盘特殊方格位置： 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;， 即覆盖相应格子，并将其作为对应子棋盘的特殊方格。下面亦如此。,2019/4/14,计算机算法设计与分析,80,Coverjoin的实现,覆盖结合部并确定各子棋盘特殊方格位置也可以用如下的语句来实现： srr=dr; scr=dc; for (k = 0, kr)Boardjrkjck=tile; srk=jrk; sck= jck;,特殊子棋盘的特殊方格还是原来的。,对每个非特殊子棋盘，则覆盖其结合部的方格并将其作为该子棋盘的特殊方格。,由于这个操作可以用此简单表示，所以才在上一张幻灯片上采用了简记的方式。,2019/4/14,计算机算法设计与分析,81,棋盘覆盖算法的主程序,main(int n, int dr, int dc) int s = 2n int Boardss = 0; int tile = 0; CoverBoard(n, 0, 0, dr, dc); ,请同学们自己编程来具体实现这个程序。,2019/4/14,计算机算法设计与分析,82,棋盘覆盖算法的正确性,要证明一个算法的正确性，需要证明两点： (1)算法的部分正确性； (2)算法的终止性。 下面我们用归纳法证明棋盘覆盖算法的部分正确性：,2019/4/14,计算机算法设计与分析,83,棋盘覆盖算法的部分正确性,归纳基础：k = 0时，特殊棋盘仅含一个特殊方格，显然已经正确覆盖。 假设对2k1的特殊棋盘均可正确覆盖。 对2k的特殊棋盘，算法划分为四个2k1的子棋盘。用一块L型骨牌覆盖三个正常子棋盘的结合处后，恰形成四个2k1的特殊棋盘。由归纳假设，它们均可被正确覆盖。因而也正确覆盖了2k的特殊棋盘。 由归纳法可知，棋盘覆盖算法是部分正确。,2019/4/14,计算机算法设计与分析,84,棋盘覆盖算法的终止性,算法的终止性： 递归终止条件为递归元size为1时递归终止。 递归元size的初值为2k。每次递归时递归元减半，即size=size/2；因此，必然在有穷步内递减为1。 所以此算法必定终止。,由部分正确性和终止性可知，此算法是完全正确的。,2019/4/14,计算机算法设计与分析,85,棋盘覆盖算法的复杂性,设f(k)是棋盘覆盖算法覆盖2k2k的棋盘所需要的时间，则f(k)满足如下递归方程：,其递归元递减方式是减法，故为递推关系。,2019/4/14,计算机算法设计与分析,86,递推递归的时间复杂性,这里k = n / b。,若递归元递减的运算为减法，即n b，则： f(n) = af(n b) + D(n) = a(af(n 2b) + D(n b) + D(n) = ,2019/4/14,计算机算法设计与分析,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)对算法复杂性的影响。,在通常情况下递推递归算法的复杂性视为子任务数a的指数函数。,2019/4/14,计算机算法设计与分析,88,棋盘覆盖算法的复杂性,设f(k)是棋盘覆盖算法覆盖2k2k的棋盘所需要的时间，则T(k)满足如下递归方程：,其递归元递减方式是减法，故为递推关系。 由a = 4可知f(k) = O(4k)。,覆盖2k2k的棋盘要用 (4k1)/3个L型骨牌，故此算法是一个在渐进意义下最优的算法。,2019/4/14,计算机算法设计与分析,89,通信信道上允许传输的单词,已知在通信信道上传输的单词只能由a、b和c三个字母组成并且其中不得有两个字母a连续出现。请编写一个程序生成所有在通信信道上允许传输的长度为n的单词。,将这样的单词称为长度为n的合法单词。,我们该如何来考虑编写这个程序呢？,1、先分析最简单情况的解。 2、再分析复杂情况如何由较简情况组成。,2019/4/14,计算机算法设计与分析,90,通信信道上允许传输的单词,应该是长度n = 1的单词。,此问题中最简单的情况是什么？,长度为1的合法单词只有三个，即a、b和c。,下面我们再考虑长度为n(n 1)的合法单词是如何由长度n 1的合法单词构成的。,2019/4/14,计算机算法设计与分析,91,通信信道上允许传输的单词,把长度为n 合法单词w去掉最前面的一个符号后所剩下的就是长度为n 1的单词w。显然w仍然应该是合法单词。,如何考虑用长度n 1的合法单词来构成长度n的合法单词呢？,于是有：,这里用符号+表示符号串的连接运算。,2019/4/14,计算机算法设计与分析,92,通信信道上允许传输的单词,先考虑w = a + w的情况：,于是有：,因为通信信道上的合法单词中不允许出现连续的a，所以w只能以b或者c开头。 于是w = b + w或者w = c + w。 这里w为任意的长度为n 2的合法单词。,将长度为n的合法单词命名为Legal(n)。,2019/4/14,计算机算法设计与分析,93,通信信道上允许传输的单词,先考虑w = a + w的情况：,于是有：,因为通信信道上的合法单词中不允许出现连续的a，所以w只能以b或者c开头。 于是w = b + w或者w = c + w。 这里w为任意的长度为n 2的合法单词。,2019/4/14,计算机算法设计与分析,94,通信信道上允许传输的单词,再考虑w = b + w和w = c + w的情况：,于是有：,这里的w可以为任意的长度为n 1的合法单词。,2019/4/14,计算机算法设计与分析,95,通信信道上允许传输的单词,综合起来可以得到长度为n的合法单词与长度较短的合法单词之间有如下的关系：,现在发生了一个新的情况！,什么情况？,2019/4/14,计算机算法设计与分析,96,通信信道上允许传输的单词,综合起来可以得到长度为n的合法单词与长度较短的合法单词之间有如下的关系：,这是个两步递归！可是我们只考虑了n = 1这一种最简单情况！,要增加n = 0的情况。,2019/4/14,计算机算法设计与分析,97,通信信道上允许传输的单词,综合起来可以得到长度为n的合法单词与长度较短的合法单词之间有如下的关系：,我们令当n = 0时的合法单词为空串 ，即 Legal(0) = 。,2019/4/14,计算机算法设计与分析,98,通信信道上允许传输的单词,综合n 为 0和1的最简单情况后，有：,2019/4/14,计算机算法设计与分析,99,程序设计的思考,现在就让我们来设计这个程序吧！,这个程序要打印出所有在通信信道上传输的长度为n的合法单词。,2019/