算法分析習(xí)題解答1

1、234、Gray碼是一個長度為2n的序列。序列中無相同元素。每個元素都是長度為n位的串。相鄰元素恰好只有一位不同。用分治策略設(shè)計一個算法對任意的n構(gòu)造相應(yīng)的Gray碼。答：設(shè)序列中元素由0、1組成。當(dāng)n=1時Gray碼的序列有2個元素（21=2），分別為：0，|1當(dāng)n=2時Gray碼的序列有4個元素（22=4），分別為：00，10，|11，01當(dāng)n=3時Gray碼的序列有8個元素（23=8），分別為：000，100，110，010，|0

2、11，111，101，001當(dāng)n=4時Gray碼的序列有16個元素（24=16），分別為：0000，1000、1100、0100，0110，1110，1010，0010，|0011，1011，1111，0111，0101，1101，1001，0001從上面的列舉可得如下規(guī)律：n=k時，Gray碼的序列有2k個元素，分別為：n=k1時的Gray碼元素正向后加0，得前2k1個元素，反向后加1的后2k1個元素。如n=2時Gray碼序列的4個元

3、素分別為：00，10，11，01當(dāng)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碼四個元素反向后加1，n=2時Gray碼四個元素：00，10，11，01即：011，111，101，001可以看出，Gray碼可以用分治策略，遞歸實現(xiàn)

4、，2n的Gray碼可以用2n1的Gray碼構(gòu)成。算法描述：voidGray(typea[]intn)a[]if(n==1)a[0]=’0’a[1]=’1’if(n1)Gray(a[]n1)intk=2n11Gray碼的個數(shù)，因為數(shù)組下標從0開始inti=kf(intx=kx=0x)y=a[x]a[x]=y’0’a[i1]=y’1’i37給定由n個英文單詞組成的一段文章，……答：設(shè)由n個單詞組成的一段文章可以表示為A[1:n]，它的“漂亮