问题描述
这是从算法的书的任务。
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 -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, ..., 2-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 G, flip 0-th bit in G, as 0 is the position of the least significant 1 in the binary representation of 1 = 0001. G = 0001.
要生成摹，翻转 1-ST G中 1 ，位为 1 是最低显著 1 中的二进制再presentation位置2 = 0010 B 。摹 = 0011 。
To generate G, flip 1-st bit in G, as 1 is the position of the least significant 1 in the binary representation of 2 = 0010. G = 0011.
要生成摹 3 ，翻转 0个 G中位，如 0 是最低显著 1 中的二进制再presentation位置3 = 0011 B 。摹 3 = 0010 。
To generate G, flip 0-th bit in G, as 0 is the position of the least significant 1 in the binary representation of 3 = 0011. G = 0010.
要生成摹 4 ，翻转 2-ND G中 3 位，如 2 是最低显著 1 中的二进制再presentation位置4 = 0100 B 。摹 4 = 0110 。
To generate G, flip 2-nd bit in G, as 2 is the position of the least significant 1 in the binary representation of 4 = 0100. G = 0110.
要生成摹 5 ，翻转 0个 G中 4 位，如 0 是最低显著 1 中的二进制再presentation位置5 = 0101 B 。摹 5 = 0111 。
To generate G, flip 0-th bit in G, as 0 is the position of the least significant 1 in the binary representation of 5 = 0101. G = 0111.
这篇关于非递归灰色code算法的理解的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！