算法课后作业参考答案第二章

第二归与分课后作2-6nm×m个子矩阵，每个子矩阵2k2km乘积第二归与分课后作2-6nm×m个子矩阵，每个子矩阵2k2km乘积需要计算O(m3次的2k2k的矩阵乘积。而用Strassen矩阵乘法计算2k2k矩阵乘需要时间O(7k，算法计算时间为O(m37k)。此题注意传统矩阵乘法和Strassen矩阵乘2-7P(xdP(n1P(n2P(nd0，且最高项系数为因而P(x)(xn1)(xndd2d/2P(x)(xn1)(xnd)[(xn1)(xnd/2)][(xnd/21)(xnd)]dT(d) dT(d)2T(d/2)O(dlogd d解此递归式，假设logdmmOT(d)2T(d/2)O(dlogddd[T(d/22)O( log )]O(dlogd 2mT(1)O(dlogd) )...2mO(d d dO(dlogd)O(dlogd)...O(dlog)O(dlogd(1logdO(dlog2d2-14（在第三版书中是2-参考解答Gray2-14（在第三版书中是2-参考解答Gray码仅仅是要求相邻元素仅有一位不同的码序列。Gray码并不唯一。GrayGray码满足其定义：n=1,2,3,4nGraynGray码序列和n-1Gray码序列的递归关系G(n)0G(n11G1(n1)，这里G(nGray码序列,G1(n1n-1Gray码序列的每个码反序，0G(n1表示n-1码序列的每个码加个前缀0，1G1(n1)表示n-1位Gray码序列的每个码先反序再加个1。递归的边界情况：G(1)={0,1}2-15（第三版书）给定数a[0:n-1]，试设计一个算法，在情况下用3n22次比较找a[0:n-1]中的最大值和最小值参考解答a[0]~a[n-1]分为2部分，一部分个数为n/2，另一部分为n/2，将这两部分分 n(n/2)T(n)n nT(n)2T(n/2) n式（2）(n/2)2[2T(n/4)2]2logn1T(2)2logn1...n(n23n2可用数学归纳(n/2)2[2T(n/4)2]2logn1T(2)2logn1...n(n23n2可用数学归纳法证明当递归式含上下取整（如（1）所示T(n3n221）归纳基础：当n=2时，显然有T(n)3n222）n：/2)2n有T(n3n223n2n(n/2)T(n/2) 2当n为奇数时，23n3n3n 3nT(n) –2) –2)2 2n222 23n 3n3数，n-1和n+1均为偶数，因此T(n) 22n2222 2 2-27（第三版书）给定n个互不相同的数组成的集合S，以及个正整k(k≤n)，试设计一O(n)的时间算法找S中最S的中位数k个数参考解答K（1）O(n)的快速选择算法找到中位数am（2）STT|aam|ifa（3）O(n)TK（4）SMMa|ifaSand|aam|y2-28（第三版书）设X[0:n-1]和Y[0:n-1]是两个长度为n的有（已排好序试设计一个O(logn)的时间算法X和2n个数的中位数参考解答X[0:n-1]Y[0:n-1]O(logn)时间的算法，X和Y2n个数的中位数。（已排好序试设计一个O(logn)的时间算法X和2n个数的中位数参考解答X[0:n-1]Y[0:n-1]O(logn)时间的算法，X和Y2n个数的中位数。2n2nm个数（m=(n-1)/2）？X序YX[m]Y[m]X[m]2nmm1；Y[m]X[m]XY的左半段（m+1）(n-n-0X分Yn为奇时m+1n为偶时m右段：共mXXYY伪代/*LetX[0..n-1]andY[0..n-1]betwoarrays,eachcontainingnnumbersalreadyinsortedorder.GiveanO(logn)-timealgorithmtofindthemedianofall2nelementsinarrayXandY.*/**{returnX[m];returnn==1?Y[m]:returnreturnn==1?X[m]:}第二归与分算法实现题后面的算法实现2-1：（简的解法第二归与分算法实现题后面的算法实现2-1：（简的解法n（的解法（（1n个元素的中位数及其位置，并且把数组中与中位数相同的数字靠拢，可以统计中；voidr)if(l>=r)return;med=madian(a,l,r);//med为中位//2//spalitllrrspalit(a,med,l,r,ll,medlen=rr-ll+1//medlen为中位数个//X//elementnum//Xif(X.num<{X.element=med;X.num=medlen;}if(ll-1>{if(X.num<{X.element=med;X.num=medlen;}mode(a,lll-1递归对左段查找众{if(X.num<{X.element=med;X.num=medlen;}mode(a,lll-1递归对左段查找众}if(r-rr>{if(X.num<{X.element=med;X.num=medlen;}mode(a,rr+1,r);//递归对右段查找众}}//end}//endmode2-5：在递归产生全排列的那段程序开始之前，加一个判断即可：判断第ifor{//判断第i个元素是否在list[k,i－1]中出现过if(Findsame(list,k,i)) Swap(list[k],list[i]);Swap(list[k],list}2-7：2-8题的解法，再做相加。nBellB(n)，则B(n)nB(n)S(n,BellC(n,i)niB(n)C(n1,B(0)2-8：B(n)C(n1,B(0)2-8：nmn个元素中抽掉其中的一个元素, 这m个非空子集合当中，有m种可能。公式表达为：m*S(n-1,m)（２ S(0,0)=1;S(n,0)=0;S(n,n)=1;这 就能写出递归算法{if(n=0&&m==0)return1;if(m==0)return0;if(m>n)return0;if(n==m)return1;returnm*S(n-1,m)+S(n-1,m-}T(n)n1或n(m1)T(n1) 2-9：Hanoi(nAB,C)AnCB（3n时，Hanoi(n,A,B,C)（3Bn异奇偶（异奇偶指不同奇偶性nHanoi(nAB,C)（1）Hanoi(n-1,A,C,move(A,Ha