算法分析课后习题解答.doc

《算法分析课后习题解答.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2-34、Gray码是一个长度为2n的序列。序列中无相同元素。每个元素都是长度为n位的串。相邻元素恰好只有一位不同。用分治策略设计一个算法对任意的n构造相应的Gray码。答：设序列中元素由0、1组成。当n=1时Gray码的序列有2个元素（21=2），分别为：0，

2、1当n=2时Gray码的序列有4个元素（22=4），分别为：00，10，

3、11，01当n=3时Gray码的序列有8个元素（23=8），分别为：000，100，110，010，

4、011，111，101，001当n=4时Gray码的序列有16个元素（24=16），分别为：0000，1000、1100、0100，0110，1110

5、，1010，0010，

6、0011，1011，1111，0111，0101，1101，1001，0001从上面的列举可得如下规律：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，010Gray码序列的后4个元素（23=8），分别为：011，111，101，001是n=2时Gray码

7、四个元素反向后加1，n=2时Gray码四个元素：00，10，11，01即：011，111，101，001可以看出，Gray码可以用分治策略，递归实现，2n的Gray码可以用2n-1的Gray码构成。算法描述：voidGray(typea[],intn){chara[];if(n==1){a[0]=’0’;a[1]=’1’;}if(n>1){Gray(a[],n-1);intk=2n-1-1;//Gray码的个数，因为数组下标从0开始inti=k;for(intx=k;x>=0;x--){chary=a[x];a[x]=y+’0’;a[i+1]=y+’1’;i++;}}}3-7给定由n

8、个英文单词组成的一段文章，……答：设由n个单词组成的一段文章可以表示为A[1:n]，它的“漂亮打印”方案记为B[1:n]，构成该最优解的最小空格数（最优值）记为m[1][n]（1）分析最优解的结构：A[1:n]的最优解B[1:n]，必然在第k个单词处断开，那么A[1:k]是“漂亮打印”，并且A[k+1:n]也是“漂亮打印”。故m[1][n]最小时有m[1][n]=m[1][k]+m[k+1][n]，m[1][k]是A[1:k]的最小值，m[k+1][n]是A[k+1:n]的最小值。因此，原问题的最优解包含其子问题的最优解，具有最优子结构性质。（1）建立递归关系：第一行，row=1，最

9、漂亮的打印字符数最小空格数第二行，row=2，最漂亮的打印字符数最小空格数那么，设：sum=i1+k2+……+in+n为文章中字符的总长度，其中i1,i2,……in分别为n个单词的长度，n为单词之间的空格数。M是一行可以输出的字符数该文章可能输出的行数约为：sum/M+1(由于最后一行除外，故可能需处理的行数为sum/M行。第sum/M行时，row=sum/M最小空格数1.当i=j时，A[i:i]=A[i]，m[i][j]=0，表示一个单词，没有空格。2.当i

10、n{m[i][k]+m[k+1][j]}，此时，k只有j-i中可能，k是使m[i][j]达到最小的那个位置。从而m[i][j]可以递归地定义为：m[i][j]=//上面两个式子m[i][j]给出了最优值，即A[i:j]的最小空格数若将对应于m[i][j]的断开位置k记为s[i][j]，在计算出最优值m[i][j]后，可递归地由s[i][j]构造出相应的最优解（2）计算最优值算法：voidf(intn,int**m,int**s,intsum,intM){for(inti=1;i<=n;i++)m[i][j]=0;for(introw=1;row<=sum/M;row++){i=1;f

11、or(intr=2;r<=n;r++){j=i+r-1;m[i][j]=row*M-j+row-(i1+i2+……ik)if(m[i][j]<0)break;s[i][j]=j;for(intk=i+1;k