算法分析習題解答(共3頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上2-34、Gray碼是一個長度為2n的序列。序列中無相同元素。每個元素都是長度為n位的串。相鄰元素恰好只有一位不同。用分治策略設計一個算法對任意的n構(gòu)造相應的Gray碼。 答：設序列中元素由0、1組成。 當 n=1 時 Gray碼的序列有2個元素（21=2），分別為：0，| 1 當 n=2 時 Gray碼的序列有4個元素（22=4），分別為：00，10，| 11，01 當 n=3 時 Gray碼的序列有8個元素（23=8），分別為：000，100，110，010，| 011，111，101，001當 n=4 時 Gray碼的序列有16個元素（24=16），分別為：00

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

3、），分別為：011，111，101，001是n=2時Gray碼四個元素反向后加1，n=2時Gray碼四個元素：00，10， 11，01即：011，111，101，001 可以看出，Gray碼可以用分治策略，遞歸實現(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碼的個數(shù)，因為數(shù)組下標從0開始 int i=k; for (int x=k;x>=0;x-) char y=ax; ax=

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

5、1=M-()第二行，row=2，最漂亮的打印字符數(shù)最小空格數(shù)mj1+1j2=M-()那么，m1j2=2M-設：sum=i1+k2+in+n 為文章中字符的總長度，其中i1,i2,in分別為n個單詞的長度，n為單詞之間的空格數(shù)。 M是一行可以輸出的字符數(shù) 該文章可能輸出的行數(shù)約為：sum/M+1 (由于最后一行除外，故可能需處理的行數(shù)為sum/M行。第sum/M行時，row=sum/M最小空格數(shù)m1jx=sum/M*M- (1<=x<=n)1. 當i=j時，Ai:i=Ai，mij=0，表示一個單詞，沒有空格。2. 當i<j時，利用最優(yōu)子結(jié)構(gòu)性質(zhì)計算mij若Ai:j的最優(yōu)解在Ak

6、和Ak+1處斷開，i<=k<j，則mij=minmik+mk+1j，此時，k只有j-i中可能，k是使mij達到最小的那個位置。從而mij可以遞歸地定義為：mij= /上面兩個式子mij給出了最優(yōu)值，即Ai:j的最小空格數(shù)若將對應于mij的斷開位置k記為sij，在計算出最優(yōu)值mij后，可遞歸地由sij構(gòu)造出相應的最優(yōu)解（3） 計算最優(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) break; 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