算法分析习题解答

2-34、Gray码是一个长度为2n的序列。序列中无相同元素。每个元素都是长度为n位的串。相邻元素恰好只有一位不同。用分治策略设计一个算法对任意的n构造相应的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），分别为：0000，1000、1100、0100，0110，1110，1010，0010，| 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，010 Gray码序列的后4个元素（23=8），分别为：011，111，101，001是n=2时Gray码四个元素反向后加1，n=2时Gray码四个元素：00，10， 11，01即：011，111，101，001 可以看出，Gray码可以用分治策略，递归实现，2n的Gray码可以用2n-1的Gray码构成。 算法描述： void Gray( type a,int n) char a; if (n=1) a0=0;a1=1; if (n1) Gray(a,n-1); int k=2n-1-1; /Gray码的个数，因为数组下标从0开始 int i=k; for (int x=k;x=0;x-) char y=ax; ax=y+0; ai+1=y+1; i+; 3-7 给定由n个英文单词组成的一段文章， 答：设由n 个单词组成的一段文章可以表示为 A1:n，它的“漂亮打印”方案记为B1:n，构成该最优解的最小空格数（最优值）记为m1n（1） 分析最优解的结构：A1:n的最优解B1:n，必然在第k个单词处断开，那么A1:k是“漂亮打印”，并且Ak+1:n也是“漂亮打印”。故m1n最小时有m1n=m1k+mk+1n ，m1k是A1:k的最小值，mk+1n是Ak+1:n的最小值。因此，原问题的最优解包含其子问题的最优解，具有最优子结构性质。（2） 建立递归关系：第一行，row=1，最漂亮的打印字符数 最小空格数 m1j1=M-()第二行，row=2，最漂亮的打印字符数最小空格数mj1+1j2=M-()那么，m1j2=2M-设：sum=i1+k2+in+n 为文章中字符的总长度，其中i1,i2,in分别为n个单词的长度，n为单词之间的空格数。 M是一行可以输出的字符数 该文章可能输出的行数约为：sum/M+1 (由于最后一行除外，故可能需处理的行数为sum/M行。第sum/M行时，row=sum/M最小空格数m1jx=sum/M*M- (1=x=n)1. 当i=j时，Ai:i=Ai，mij=0，表示一个单词，没有空格。2. 当ij时，利用最优子结构性质计算mij若Ai:j的最优解在Ak和Ak+1处断开，i=kj，则mij=minmik+mk+1j，此时，k只有j-i中可能，k是使mij达到最小的那个位置。从而mij可以递归地定义为：mij= /上面两个式子mij给出了最优值，即Ai:j的最小空格数若将对应于mij的断开位置k记为sij，在计算出最优值mij后，可递归地由sij构造出相应的最优解（3） 计算最优值算法： 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 (mij0) break; sij=j; for (int k=i+1;kj);k+) t=mik+mk+1j; if (tmij) mij=t;sij=k; ;x=j-1;（4） 构造最优解算法描述：void