资源描述：
《算法分析课后习题解答》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、2-34.Gray码是一个长度为2n的序列。序列中无相同元素。每个元素都是长度为n位的串。相邻元素恰好只有一位不同。用分治策略设计一个算法对任意的n构造相应的Gray码。答：设序列中元素由0、1组成。当n=l时Gray码的序列有2个元素(21=2),分别为：0,I12当n=2时Gray码的序列有4个元素(2=4),分别为：00,10,111,013当n=3时Gray码的序列有8个元素(2=8),分别为:000,100,110,010,1011,111,101,001当n=4时Gray码的序列有16个元素(24=16),分别为:0000,10
2、00、1100、0100,0110,1110,1010,0010,10011,1011,1111,0111,0101,1101,1001,0001从上面的列举可f导如下规律:n=k时，Gray码的序列有2k个元索，分别为：n=k-l时的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,艮
3、丄000,100,110,010Gra
4、y码序列的后4个尤素(23=8),分别为：011,111,101,001是n=2时Gray码四个元素反向后加1,n=2时Gray码四个元素：00,10,11,01即：Oil,111,101,001可以看出，Gray码可以用分治策略，递归实现，2n的Gray码可以用2n-l的Gray码构成。算法描述:voidGray(typea[],intn){chara[J;if(n==l){a[0]='0';a[l]=T;}if(n>l){Gray(a[],n-1);intk=2n-l-l;//Gray码的个数，因为数组卜•标从0开始inti=k;
5、for(intx=k;x>=0;x—){chary二a[x];a[x]二y+'O';a[i+l]=y+T;i++;}}}3-7给定由n个英文单词组成的一段文章，……答：设由n个单词组成的一段文章可以表示为A[l:n],“漂亮打卬”它的方案记为B[l:n],构成该最优解的最小空格数(最优值)记为m[l][n](1)分析最优解的结构：A[l:n]的最优解B[l:n],必然在第k个单词处断开，那么A[l:k]是“漂亮打卬”并且A[k+l:n],也是“漂亮打卬”o故m[l][n]最小时有m[l][n]=m[l][k]+m[k+l][n],m[
6、l][k]是A[l:k]的最小值,m[k+l][n]是A[k+l:n]的最小值。因此，原问题的最优解包含其子问题的最优解，具有最优子结构性质。(2)建立递归关系：第一行，row=l,最漂亮的打印字符数》ik+jl?lk=ljl最小空格数m[l][jl]=M-(Xik+jl?1)k=1jl第二行，row=2,最漂亮的打卬字符数k二jl+1j2》ik+j2?jl?1j2最小空格数m[jl+l][j2]=M-(k=jl+lj2工ik+j2?jl?l)那么，m[l][j2]=2M・工ik?j2+2k=1设：sum二订+k2++in+n为文章中字符的
7、总长度，其屮il,i2,……in分别为n个单词的长度，n为单词Z间的空格数。M是一行可以输出的字符数该文章可能输出的行数约为:sum/M+l(由于最后一行除外，故可能需处理的行数为sum/M行。第sum/M行时，row=sum/M最小空格数m[l][jx]二sum/M*M・〈ik?jx+sum/Mk=1jx(l<二x<=n)1.当i=j时,A[i:i]=A[i],m[i][j]=O,表示一个单词,没有空格。2.当i<j时,利用最优子结构性质计算m山[j]若A[i:j啲最优解在Ak和Ak+1处断开，i<=k<j，
8、则m[i][j]=min{m[i][k]+m[k+1][j]},此时,k只有j-i中可能,k是使达到最小的那个位置。从而可以递归地定义为：二〃上而两个式子m[i][j]给岀了最优值，即A[i:j]的最小空格数若将对应于的断开位置k记为s[i][j],在计算出最优值m[i][j]后，可递归地由s[i][j]构造出相应的最优解(3)计算最优值算法：voidf(intn,int**m,int**s,intsum,intM){for(inti=l;i<=n;i++)m[i][j]=0;for(introw=l;row<二sum/M;ro
9、w++){i=l;for(intr=2;r<=n;r+4-){j=i+r-l;m[i]fj]=row*M-j+row-(订+i2+ik)if(m[i][j]<O)br
