算法課后作業(yè)參考答案第二章

第二歸與分課后作2-6nm×m個子矩陣，每個子矩陣2k2km乘積第二歸與分課后作2-6nm×m個子矩陣，每個子矩陣2k2km乘積需要計算O(m3次的2k2k的矩陣乘積。而用Strassen矩陣乘法計算2k2k矩陣乘需要時間O(7k，算法計算時間為O(m37k)。此題注意傳統(tǒng)矩陣乘法和Strassen矩陣乘2-7P(xdP(n1P(n2P(nd0，且最高項系數(shù)為因而P(x)(xn1)(xndd2d/2P(x)(xn1)(xnd)[(xn1)(xnd/2)][(xnd/21)(xnd)]dT(d) dT(d)2T(d/2)O(dlogd d解此遞歸式，假設(shè)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碼序列的遞歸關(guān)系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（第三版書）給定數(shù)a[0:n-1]，試設(shè)計一個算法，在情況下用3n22次比較找a[0:n-1]中的最大值和最小值參考解答a[0]~a[n-1]分為2部分，一部分個數(shù)為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可用數(shù)學歸納(n/2)2[2T(n/4)2]2logn1T(2)2logn1...n(n23n2可用數(shù)學歸納法證明當遞歸式含上下取整（如（1）所示T(n3n221）歸納基礎(chǔ)：當n=2時，顯然有T(n)3n222）n：/2)2n有T(n3n223n2n(n/2)T(n/2) 2當n為奇數(shù)時，23n3n3n 3nT(n) –2) –2)2 2n222 23n 3n3數(shù)，n-1和n+1均為偶數(shù)，因此T(n) 22n2222 2 2-27（第三版書）給定n個互不相同的數(shù)組成的集合S，以及個正整k(k≤n)，試設(shè)計一O(n)的時間算法找S中最S的中位數(shù)k個數(shù)參考解答K（1）O(n)的快速選擇算法找到中位數(shù)am（2）STT|aam|ifa（3）O(n)TK（4）SMMa|ifaSand|aam|y2-28（第三版書）設(shè)X[0:n-1]和Y[0:n-1]是兩個長度為n的有（已排好序試設(shè)計一個O(logn)的時間算法X和2n個數(shù)的中位數(shù)參考解答X[0:n-1]Y[0:n-1]O(logn)時間的算法，X和Y2n個數(shù)的中位數(shù)。（已排好序試設(shè)計一個O(logn)的時間算法X和2n個數(shù)的中位數(shù)參考解答X[0:n-1]Y[0:n-1]O(logn)時間的算法，X和Y2n個數(shù)的中位數(shù)。2n2nm個數(shù)（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]:}第二歸與分算法實現(xiàn)題后面的算法實現(xiàn)2-1：（簡的解法第二歸與分算法實現(xiàn)題后面的算法實現(xiàn)2-1：（簡的解法n（的解法（（1n個元素的中位數(shù)及其位置，并且把數(shù)組中與中位數(shù)相同的數(shù)字靠攏，可以統(tǒng)計中；voidr)if(l>=r)return;med=madian(a,l,r);//med為中位//2//spalitllrrspalit(a,med,l,r,ll,medlen=rr-ll+1//medlen為中位數(shù)個//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：在遞歸產(chǎn)生全排列的那段程序開始之前，加一個判斷即可：判斷第ifor{//判斷第i個元素是否在list[k,i－1]中出現(xiàn)過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