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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上2-34、Gray碼是一個(gè)長度為2n的序列。序列中無相同元素。每個(gè)元素都是長度為n位的串。相鄰元素恰好只有一位不同。用分治策略設(shè)計(jì)一個(gè)算法對任意的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），分別為：00

2、00，1000、1100、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

3、），分別為：011，111，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=

4、y+0; ai+1=y+1; 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ù) m1j

5、1=M-()第二行，row=2，最漂亮的打印字符數(shù)最小空格數(shù)mj1+1j2=M-()那么，m1j2=2M-設(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ù)m1jx=sum/M*M- (1<=x<=n)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

6、和Ak+1處斷開，i<=k<j，則mij=minmik+mk+1j，此時(shí)，k只有j-i中可能，k是使mij達(dá)到最小的那個(gè)位置。從而mij可以遞歸地定義為：mij= /上面兩個(gè)式子mij給出了最優(yōu)值，即Ai:j的最小空格數(shù)若將對應(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) 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