第三讲分治法3递归与策略

32~3[找出伪币]给你一个装有16个硬币的袋子。16个硬币中有一个是的，并且那个1211111一 分治任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越n1时，不需任何计算。2时，只要作一次比较即可排好序。33次比较即n有时是相当的。k个子问题，1<k≤n，且这些子问题都可解，并可利用这些子（分而治之2、分治法所能解决的问题一般具有以下几个特征简问题的求{{}分解成k个子问题p1,p2 pkDC(pi}kk=2自一种平衡(alancig)子问题的思，它几乎总是问题规模不等的做法要好。二 例棋盘。现在任意给定一个2k×2k的特殊棋盘，要用右下图所示的L型骨牌来无的覆23233221341154455设X和Y都是n位的二进制整数，现在要计算它们的乘积XY。我们可以用小学所学XY的算法，但是这样做计算步骤太多，显得效率较低。见教P25，T(n)=O(n2)。如果将每2个1位数的乘法或加法看作一步运算，那么这种方法要作O(n2)步运算才能求出乘积XY。下面我们用分治法来设计一个更有效的大整数乘积算法。nX和Y2n/2位(为简单起见，假设n2的幂)由此，X=A2n/2+B，Y=C2n/2+D。这样，XY 如果按式(1)计算XY，则须进行4次n/2位整数的乘法(AC，AD，BC和BD)3n位的整数加法(分别对应于式(1)中的加号)2次移位(分别对应于式(1)2n2n/2)。所有这些加法和移位共用O(n)步运算。设T(n)2个n位整数相乘所需的运算总数，则由式(1)，我们有:T(n)=O(n2)。因此，用(1)X和Y的乘积并不比小学生的方法更有XY写成另一种形式:XY=AC2n+[(A-B)(D- 虽然，式(3)看起来比式(1)3n/2位整数的乘法(AC，BD和(A-B)(D-C))，62次移位。由此可得:用解递归方程的套用法马上可得其解为T(n)=O(nlog3)=O(n159)。intMULT(intX，int X和Y22nXY{intS=sign(X)*sign(Y{SXY的符号乘积}Y=abs(Y{XY分别取绝对值}if(n==1)if(X==1)return{

returnA=Xn/2位;B=X的右边n/2位;C=Y的左边n/2位;D=Yn/2位;returnS;}}X=314l,Y=5327XY的计算过程可列表如下，其中带'号的数值是AC，BD，和(A-B)(D-C)之后才填入的。D-C=- A1-D1-C1=-(A1-B1)(D1-C1)=-AC=1500+(15+3-A2-D2-(A2-B2)(D2-|A- A3- 3、StrassenAB2n×n的矩阵，则它们的乘积C=AB同样是一个n×n的矩阵。AB的乘积矩阵CC[i,j]定义为:A和BCCC[i,j]n个n-1Cn20(n3)。60年代末，Strassen2阶矩阵乘积所需的计算时间改进到O(nlog7)=O(n2.18)n2A，BC4个n/2×n/2C=AB重写为:由此可得 n=222阶方阵的乘积可以直接用(2)-(3)8次加法。当子矩阵的阶大于2时，为求2个子矩阵的积，可以继续将子矩阵分块，直到子矩阵的阶降为2。这样，就产生了一个分治降阶的递归算法。依此算法，计算2个n阶方阵的乘积转化为计算8n/2阶方阵的乘积和4n/2阶方阵的加法。2n/2×n/2矩阵的加法显然可以在c*n2/4时间内完成，这里c是一个常数。因此，上述分治法的计算时间T(n)应该满足：T(n3。因此，该方法并不比用原始定义直接计算更有效。究其原因，乃是由于式5并没有减少矩阵的乘法次数。而矩阵乘法耗费的时间要比矩阵加减法耗费的时间多得多。要想改进矩阵乘法的计算时间复杂性，必须减少子矩阵乘法运算的次数。按照上述分治法的思想可以看出，要想减少乘法运算次数，关键在于计228次的乘法运算。Strssn2277次乘法是7次乘法后，再做若干次加、减法就可以得到:=(A11+A22)(B11+B22)+A11(B12-B22)-(A21+A22)B11-(A11--A11B22-A21B11-A22B11-A11B11-由(2)式便知其正确性Strassen7n/218T(n)满足如下的递归方程按照解递归方程的套用法，其解为T(n)=O(nlog7)≈O(n2.81)。由此可见nn-1ijij1≤i≤n，1≤j≤n-1。nn/2

2 8

785 ）图 块分别为选手1至选手4和选手5选手83天的比赛日程。据此，将左上角小块中的角，这样我们就分别安排好了选手1至选手4选手58在后4天的比赛日程。依voidmatchtable(inta[][N],int{intn=1,for(inti=1;i<=k;n*=for(inti=0;i<n;i++)for(ints=0s<k; k{n/=for(intt=0t<n;t每个阶段有t{for(i