算法分析习题解答1[1].doc

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) { a[0]=’0’;a[1]=’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=a[x]; a[x]=y+’0’; a[i+1]=y+’1’; i++; } } } 3-7 给定由n个英文单词组成的一段文章，…… 答：设由n 个单词组成的一段文章可以表示为 A[1:n]，它的“漂亮打印”方案记为B[1:n]，构成该最优解的最小空格数（最优值）记为m[1][n] 分析最优解的结构： 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]的最小值。因此，原问题的最优解包含其子问题的最优解，具有最优子结构性质。 建立递归关系： 第一行，row=1，最漂亮的打印字符数 最小空格数 m[1][j1]=M-() 第二行，row=2，最漂亮的打印字符数 最小空格数m[j1+1][j2]=M-() 那么，m[1][j2]=2M- 设：sum=i1+k2+……+in+n 为文章中字符的总长度，其中i1,i2,……in分别为n个单词的长度，n为单词之间的空格数。 M是一行可以输出的字符数 该文章可能输出的行数约为：sum/M+1 (由于最后一行除外，故可能需处理的行数为sum/M行。 第sum/M行时，row=sum/M 最小空格数m[1][jx]=sum/M*M- (1=x=n) 当i=j时，A[i:i]=A[i]，m[i][j]=0，表示一个单词，没有空格。 当ij时，利用最优子结构性质计算m[i][j] 若A[i:j]的最优解在Ak和Ak+1处断开，i=kj，则 m[i][j]=min{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]构造出相应的最优解 计算最优值 算法： void f(int n,