算法分析課后習(xí)題解答

1、2-34、Gray碼是一個(gè)長度為2n的序列。序列中無相同元素。每個(gè)元素都是長度為n位的串。相鄰元素恰好只有一位不同。用分治策略設(shè)計(jì)一個(gè)算法對(duì)任意的n構(gòu)造相應(yīng)的Gray碼。 答：設(shè)序列中元素由0、1組成。 當(dāng) n=1 時(shí) Gray碼的序列有2個(gè)元素（21=2），分別為：0，| 1 當(dāng) n=2 時(shí) Gray碼的序列有4個(gè)元素（22=4），分別為：00，10，| 11，01 當(dāng) n=3 時(shí) Gray碼的序列有8個(gè)元素（23=8），分別為：000，100，110，010，| 011，111，101，001當(dāng) n=4 時(shí) Gray碼的序列有16個(gè)元素（24=16），分別為：0000，1000、1100、

2、0100，0110，1110，1010，0010，| 0011，1011，1111，0111，0101，1101，1001，0001從上面的列舉可得如下規(guī)律：n=k時(shí)，Gray碼的序列有2k個(gè)元素，分別為：n=k-1時(shí)的Gray碼元素正向后加0，得前2k-1個(gè)元素，反向后加1的后2k-1個(gè)元素。如 n=2時(shí) Gray碼序列的4個(gè)元素分別為：00，10， 11，01當(dāng) n=3 時(shí) Gray碼序列的前4個(gè)元素（23=8），分別為：000，100，110，010是n=2時(shí)Gray碼四個(gè)元素正向后加0，即：000，100， 110，010 Gray碼序列的后4個(gè)元素（23=8），分別為：011，111

3、，101，001是n=2時(shí)Gray碼四個(gè)元素反向后加1，n=2時(shí)Gray碼四個(gè)元素：00，10， 11，01即：011，111，101，001 可以看出，Gray碼可以用分治策略，遞歸實(shí)現(xiàn)，2n的Gray碼可以用2n-1的Gray碼構(gòu)成。 算法描述： void Gray( type a,int n) char a; if (n=1) a0=0;a1=1; if (n>1) Gray(a,n-1); int k=2n-1-1; /Gray碼的個(gè)數(shù)，因?yàn)閿?shù)組下標(biāo)從0開始 int i=k; for (int x=k;x>=0;x-) char y=ax; ax=y+0; ai+1=y+1

4、; i+; 3-7 給定由n個(gè)英文單詞組成的一段文章， 答：設(shè)由n 個(gè)單詞組成的一段文章可以表示為 A1:n，它的“漂亮打印”方案記為B1:n，構(gòu)成該最優(yōu)解的最小空格數(shù)（最優(yōu)值）記為m1n（1） 分析最優(yōu)解的結(jié)構(gòu)：A1:n的最優(yōu)解B1:n，必然在第k個(gè)單詞處斷開，那么A1:k是“漂亮打印”，并且Ak+1:n也是“漂亮打印”。故m1n最小時(shí)有m1n=m1k+mk+1n ，m1k是A1:k的最小值，mk+1n是Ak+1:n的最小值。因此，原問題的最優(yōu)解包含其子問題的最優(yōu)解，具有最優(yōu)子結(jié)構(gòu)性質(zhì)。（2） 建立遞歸關(guān)系：第一行，row=1，最漂亮的打印字符數(shù) 最小空格數(shù) 第二行，row=2，最漂亮的打印

5、字符數(shù)最小空格數(shù)那么，設(shè)：sum=i1+k2+in+n 為文章中字符的總長度，其中i1,i2,in分別為n個(gè)單詞的長度，n為單詞之間的空格數(shù)。 M是一行可以輸出的字符數(shù) 該文章可能輸出的行數(shù)約為：sum/M+1 (由于最后一行除外，故可能需處理的行數(shù)為sum/M行。第sum/M行時(shí)，row=sum/M最小空格數(shù) 1. 當(dāng)i=j時(shí)，Ai:i=Ai，mij=0，表示一個(gè)單詞，沒有空格。2. 當(dāng)i<j時(shí)，利用最優(yōu)子結(jié)構(gòu)性質(zhì)計(jì)算mij若Ai:j的最優(yōu)解在Ak和Ak+1處斷開，i<=k<j，則mij=minmik+mk+1j，此時(shí)，k只有j-i中可能，k是使mij達(dá)到最小的那個(gè)位置。從

6、而mij可以遞歸地定義為：mij= /上面兩個(gè)式子mij給出了最優(yōu)值，即Ai:j的最小空格數(shù)若將對(duì)應(yīng)于mij的斷開位置k記為sij，在計(jì)算出最優(yōu)值mij后，可遞歸地由sij構(gòu)造出相應(yīng)的最優(yōu)解（3） 計(jì)算最優(yōu)值算法： void f(int n, int *m, int *s, int sum, int M) for(int i=1;i<=n;i+) mij=0; for(int row=1;row<=sum/M;row+) i=1; for (int r=2;r<=n;r+) j=i+r-1; mij=row*M-j+row-(i1+i2+ik) if (mij<0) b

7、reak; sij=j; for (int k=i+1;k<j);k+) t=mik+mk+1j; if (t<mij) mij=t;sij=k; ;x=j-1;（4） 構(gòu)造最優(yōu)解算法描述：void T(int *B, int *s, int x) y=1; do by=s1x; x=by;y=y+1; while (x<>1) do printf(“%d,”,by); y-; while (y>0) 4-26 求極差M=max-min解：該問題采用貪心選擇算法解決。算法思想：求max的步驟：（1）對(duì)黑板上的n個(gè)正數(shù)從小到大排序（2）取最小的兩個(gè)數(shù)，進(jìn)行a*b+1

8、運(yùn)算，將結(jié)果插入數(shù)列，再從小到大排序。（3）重復(fù)步驟（2），直到黑板上剩一個(gè)數(shù)為止，該數(shù)為最大值max。求min的步驟：（1）對(duì)黑板上的n個(gè)正數(shù)從大到小排序（2）取最大的兩個(gè)數(shù)，進(jìn)行a*b+1運(yùn)算，將結(jié)果插入數(shù)列，再從大到小排序。（3）重復(fù)步驟（2），直到黑板上剩一個(gè)數(shù)為止，該數(shù)為最大值min。算法描述：Void max-min(int n,int max,int min, type *x,type *y) MinHeap<MinHeapNode<Type>>x(1000); MaxHeap<MaxHeapNode<Type>>y(1000);

9、While (true) MinHeapNode<Type>x; MaxHeapNode<Type>y; a=x.DeleteMin(x); b=x.DeleteMin(x); Max=a*b+1 x.insert(max); c=y.DeleteMin(y); d=y.DeleteMin(y); Min=c*d+1 y.insert(min); catch(outofBounds) break; M=a-c5-10 最小重量機(jī)解：該問題用回溯法求解。1 問題的解空間：部件：n個(gè) 1<=I<=n, 供應(yīng)商：m個(gè) 1<= j<=mwij：是從供應(yīng)商

10、j處構(gòu)得的部件I的重量。Cij：是從供應(yīng)商j處構(gòu)得的部件I的價(jià)格。當(dāng)(C11+C12+Cnm)<C時(shí)，求最小的(W11+W12+Wnm)假設(shè)n=4 m=2 時(shí)，該問題的解空間樹如下：該樹為n層的m叉樹。2 回溯法的基本思想：按深度優(yōu)先的方式搜索整個(gè)解空間樹。3 求約束函數(shù)和限界函數(shù)（1） 約束函數(shù)：若大于總價(jià)格C，則該結(jié)點(diǎn)不可能有解，可剪去以這個(gè)結(jié)點(diǎn)為根的子樹。Constraint(c) ：計(jì)算(C11+C12+Cnm)<C（2） 限界函數(shù)：先找到一個(gè)解，在尋找下一個(gè)解時(shí)，判斷擴(kuò)展結(jié)點(diǎn)處的(W11+W12+Wnm)是否小于前一個(gè)解的(W11+W12+Wnm)，若是，則繼續(xù)擴(kuò)展，否則，則該子樹不能得到最優(yōu)解，剪去以該結(jié)點(diǎn)為根的子樹。Bound(w)：計(jì)算(W11+W12+Wnm)的最小值。4 遞歸回溯算法Void weight-cost(t) if ( I>0 ) if ( cc<bestc) bestc=c; if ( bestc<c ) if ( cw<bestw ) bestw=cw; return; for ( j=1 ; j<=m; j+) if ( cc+cIj<c ) cc+=cIj; weight-cost(I+1); cc- =cIj; int n, /部件數(shù) m, /供應(yīng)商樹type *w, /是從供應(yīng)