2

这是算法书中的任务。

问题是我完全不知道从哪里开始！

Trace the following non-recursive algorithm to generate the binary reflexive
Gray code of order 4. Start with the n-bit string of all 0’s. 
For i = 1, 2, ... 2^n-1, generate the i-th bit string by flipping bit b in the 
previous bit string, where b is the position of the least significant 1 in the 
binary representation of i.

所以我知道 1 位的格雷码应该是0 12位00 01 11 10等。

许多问题

1）我知道对于 n = 1 我可以从 开始0 1吗？

2）我应该如何理解“从全0的n位字符串开始”？

3）“前一个位串”？哪个字符串是“前一个”？以前的意思是来自较低的 n 位？（例如对于 n=2，前一个是来自 n=1 的那个）？

4) 如果唯一的操作是翻转，我如何将 1 位字符串转换为 2 位字符串？

这让我很困惑。到目前为止，我理解的唯一“人类”方法是：从较低的 n 位获取集合，复制它们，反转第二个集合，将 0 添加到第一个集合中的每个元素，添加 1 做第二个集合中的每个元素。完成（例如：0 1-> 0 1 | 0 1-> 0 1 | 1 0-> 00 01 | 11 10->11 01 11 10完成。

谢谢你的帮助

4

1 回答 1

4

你所有四个问题的答案是这个算法不是从较低的值开始的n。它生成的所有字符串都具有相同的长度，并且i-th(for i= 1, ..., 2 n -1) 字符串是从该字符串生成的(i-1)-th。

这是 n = 4 的第一步：

从 G 0 =0000

为了生成 G 1，翻转0-thG 0中的位，就像1 = 0001 b0的二进制表示中的最低有效位置一样。G 1 = 。10001

为了生成 G 2，翻转1-stG 1中的位，就像2 = 0010 b的二进制表示中1的最低有效位置一样。G 2 = 。10011

为了生成 G 3，翻转0-thG 2中的位，就像3 = 0011 b0的二进制表示中的最低有效位置一样。G 3 = 。10010

为了生成 G 4，翻转2-ndG 3中的位，就像4 = 0100 b2的二进制表示中的最低有效位置一样。G 4 = 。10110

为了生成 G 5，翻转0-thG 4中的位，就像5 = 0101 b0的二进制表示中的最低有效位置一样。G 5 = 。10111

于 2014-02-26T12:44:42.990 回答