这是从算法的书的任务。

This is task from algorithms book.

的事情是，我完全不知道从何说起！

The thing is that I completely don't know where to start!

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. 

所以我知道格雷code 1位应该是 0 1 2 00 01 11 10 等。

许多问题

1）我知道，当n = 1，我可以用 0 1 ？

1) Do I know that for n = 1 I can start of with 0 1?

2）我应该怎样理解开始全部为0的N位串？

2) How should I understand "start with the n-bit string of all 0's"?

3）previous位串？其中字符串为previous？ previous指从较低的n位？ （例如对于n = 2，previous是从一个n = 1）？

3) "Previous bit string"? Which string is the "previous"? Previous means from lower n-bit? (for instance for n=2, previous is the one from n=1)?

4）如何甚至转换1位串为2位的字符串，如果只有操作有翻转？

4) How do I even convert 1-bit strings to 2-bit strings if the only operation there is to flip?

这混淆了我很多。唯一的人的方法，我至今不解的是：取集从较低n位，复制它们，反转第二盘，加0的每个元素在第1套，加1的做在第二集中的每个元素。完成（例如： 0 1 - > 0 1 | 0 1 - > 0 1 | 1 0 - > 00 01 | 11 10 - > 11 01 11 10 完成。

This confuses me a lot. The only "human" method I understand so far is: take sets from lower n-bit, duplicate them, invert the 2nd set, add 0's to every element in 1st set, add 1's do every elements in 2nd set. Done (example: 0 1 -> 0 1 | 0 1 -> 0 1 | 1 0 -> 00 01 | 11 10 -> 11 01 11 10 done.

感谢您的帮助

推荐答案

回答所有四个你的问题是，这种算法不以的较低n值。所有字符串它生成具有相同的长度，而第i （对于我 = 1，...，从产生2 N -1）字符串（I-1）个之一。

The answer to all four your questions is that this algorithm does not start with lower values of n. All strings it generates have the same length, and the i-th (for i = 1, ..., 2n-1) string is generated from the (i-1)-th one.

下面是对于n = 4的拳头几个步骤：

Here is the fist few steps for n = 4:

开始以G 0 = 0000

要生成摹 1 ，翻转 0个 G中 0 位，如 0 是最低显著 1 中的二进制再presentation位置1 = 0001 B 。摹 1 = 0001 。

To generate G1, flip 0-th bit in G0, as 0 is the position of the least significant 1 in the binary representation of 1 = 0001b. G1 = 0001.

要生成摹 2 ，翻转 1-ST G中 1 ，位为 1 是最低显著 1 中的二进制再presentation位置2 = 0010 B 。摹 2 = 0011 。

To generate G2, flip 1-st bit in G1, as 1 is the position of the least significant 1 in the binary representation of 2 = 0010b. G2 = 0011.

要生成摹 3 ，翻转 0个 G中 2 位，如 0 是最低显著 1 中的二进制再presentation位置3 = 0011 B 。摹 3 = 0010 。

To generate G3, flip 0-th bit in G2, as 0 is the position of the least significant 1 in the binary representation of 3 = 0011b. G3 = 0010.

要生成摹 4 ，翻转 2-ND G中 3 位，如 2 是最低显著 1 中的二进制再presentation位置4 = 0100 B 。摹 4 = 0110 。

To generate G4, flip 2-nd bit in G3, as 2 is the position of the least significant 1 in the binary representation of 4 = 0100b. G4 = 0110.

要生成摹 5 ，翻转 0个 G中 4 位，如 0 是最低显著 1 中的二进制再presentation位置5 = 0101 B 。摹 5 = 0111 。

To generate G5, flip 0-th bit in G4, as 0 is the position of the least significant 1 in the binary representation of 5 = 0101b. G5 = 0111.