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

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

2、100, 0110, 1110, 1010, 0010, |001b 101b 1111, 0111, 010b 1101, 1001, 0001從上面的列舉可得如下規(guī)律：n=k時，Gniy碼的序列有2*個元素，分別為：ii=kJ時的 Gray碼元素正向后加0,得前2#】個元素，反向后加1的后2“個元素。如11=2時Giay碼序列的4個元素分別為：00, 10,11, 01當(dāng)n=3時Giay碼序列的前4個元素 是n=2時Gray碼四個元素正向后加0,Gray碼序列的后4個元素 是n=2時Gray碼四個元素反向后加1, n=2時Giay碼四個元素：00, 10,(2M),分別為：000, 100

3、, 110, 010即：000, 100,110, 010(20),分別為:Oil, 111, 101, 001lb 01即：Oil, lib 101, 001 可以看出，Gray碼可以用分治策略，遞歸實現(xiàn)，211的Gray碼可以用的Gray碼構(gòu)成。算法描述：void Giav( type a.iiit n) chai a;if =1) a0=0;al=T;lf(lll) Giay(a,n-1);mt k=2n1-l;/Gray碼的個數(shù)，因為數(shù)組下標(biāo)從0開始mt i=k;for (int x=k;x=0;x-)char y=ax;ax=y+;ai+l=y+T;i+;3- 7給定由n個英文單詞組

4、成的一段文章，答：設(shè)由n個單詞組成的一段文章可以表示為Al:n,它的“漂亮打印”方案記為Bl:n, 構(gòu)成該最優(yōu)解的最小空格數(shù)(最優(yōu)值)記為mln(1) 分析最優(yōu)解的結(jié)構(gòu)：Al:n的最優(yōu)解Bl:n,必然在第k個單詞處斷開，那么Al:k是“漂亮打印”，并且Ak+l:n 也是“漂亮打印”。故 mln最小時有 mln=mlk+mk+ln , mlk是 Al:k的最 小值，mk+ln是Ak+lm的最小值。因此，原問題的最優(yōu)解包含其子問題的最優(yōu)解，具 有最優(yōu)子結(jié)構(gòu)性質(zhì)。(2) 建立遞歸關(guān)系：第一行，I6V=1,最漂亮的打印字符數(shù) ik+ J1-1 Jt=l71最小空格數(shù) mljl=M-( + J1-1)

5、jt=i第二行，】ow=2,最漂亮的打印字符數(shù)ik + j2_jl_l *=ji+i最小空格數(shù)mUl+lj2=M-( ik + j2_jT那么，mlj2=2M-f J2 + 2i=l設(shè)：sum=il+k2+in+n為文章中字符的總長度，其中11)2,m分別為n個單詞的長度，11為單詞之間的空格數(shù)。M是一行可以輸出的字符數(shù)該文章可能輸出的行數(shù)約為：suniM+1 (由于最后一行除外，故可能需處理的行 數(shù)為suni/M行。第 sum/M 行時，rowsunVMjx(l=x=n)最小空格數(shù) m 1 jx=suinM*M-ik 一 jx + sum / Mk=l1-當(dāng)i=j時,Ai:i=Ai, mij

6、=0,表示一個單詞，沒有空格。2. 當(dāng)ij時，利用最優(yōu)子結(jié)構(gòu)性質(zhì)計算若Ai:j的最優(yōu)解在Ak和Az處斷開，i=kj,貝lj mij=minmik+mk4-lj,此時，k 只有 ji 中可能,k 是使 mij達(dá)到 最小的那個位置。從而可以遞歸地定義為：mij=上面兩個式子給出了最優(yōu)值，即Ai:j的最小空格數(shù)若將對應(yīng)于鞏即的斷開位置k記為sij,在計算出最優(yōu)值mi|j后，可遞 歸地由sij構(gòu)造出相應(yīng)的最優(yōu)解(3) 計算最優(yōu)值算法：void f(iiit n, mt *m, nit *s, nit sum, mt M)i=l;i=n;i-H-) mij=0;for(mt 1 ;iow=sum M;l

7、ow-h-)i=l；for (int i=2;r=n;i-H-)j=i+r-l;mi=row*M-j +iow-(il +i2+ik)if (miIj0) break;sijH；for (int k=i+l ;kj);k+)t=mik+mk+lj;if (tmij) mij=t;siIj=k;；x=J-l；(4) 構(gòu)造最優(yōu)解算法描述：void T(iiit *B. int *s, mt x)y=i;doby=slx;x=by;y=y+l;while (xoi)doprintf(t0)4- 26 求極差 M=max-nun 解：該問題采用貪心選擇算法解決。算法思想：求max的步驟：(1) 對黑板

8、上的n個正數(shù)從小到大排序(2) 取最小的兩個數(shù)，進(jìn)行a*b+l運算，將結(jié)果插入數(shù)列，再從小到人排序。(3) 重復(fù)步驟(2),直到黑板上剩一個數(shù)為止，該數(shù)為最人值max。求nun的步驟：(1) 對黑板上的n個正數(shù)從大到小排序(2) 取最人的兩個數(shù)，進(jìn)行a*b+l運算，將結(jié)果插入數(shù)列，再從人到小排序。(3) 重復(fù)步驟(2),直到黑板上剩一個數(shù)為止，該數(shù)為最人值min。 算法描述：Void max-niui(mt n,int niaxjnt nun, type *x.type *v) MiiiHeapMiiiHeapNodeTypex( 1000);MaxHeapMaxHeapNodeTvpey(

9、1000);While (true)MmHeapNodex;MaxHeapNodev;a=x.DeleteMm(x);b=x.DeleteMm(x);Max=a*b+1x. iiisert(niax);c=y.DeleteMm(y);d=y.DeleteMiii(y)；Min=c*d+1y.insert(niiii);catch(outofBounds) break;M=a-c5- 10最小重量機(jī)解：該問題用回溯法求解。1. 問題的解空間：部件：11個 l=I=n,供應(yīng)商：m個 l=j=mwij：是從供應(yīng)商j處構(gòu)得的部件I的重量。Cij：是從供應(yīng)商j處構(gòu)得的部件I的價格。當(dāng)(C11+C12+C

10、mn)C 時，求最小的(W11+W12+Wnm)假設(shè)n=4m=2時，該問題的解空間樹如下：該樹為n層的m叉樹。2. 回溯法的基本思想：按深度優(yōu)先的方式搜索整個解空間樹。3. 求約束函數(shù)和限界函數(shù)(1) 約束函數(shù)：若人于總價格C,則該結(jié)點不可能有解，可剪去以這個結(jié)點為根的子樹。Constraint(c):計算(C11+C124 +Cnm)0)if (ccbestc) bestc=c;if (bestcc ) if ( cwbestw) bestw=cw;leturn;fbr(j=l ; j=m; j+) if (cc+cIjc) cc+=cI|j; weiglit-cost(I+l);cc- =cI|j;mt n,/部件數(shù)m,供應(yīng)商樹type *w, 是從供應(yīng)商j處構(gòu)得