中国环难题和格雷码

最近在翻TAOCP的第四卷第2册。看到格雷码问题的一个产生方式是与一个叫做中国环问题相关（作为中国人，我竟然不知道这个东西）。而这个问题我去年在做ACM题目的时候，刚好也有个类似的题目，关于一个囚犯解脱的问题规则和这个一模一样。当时我仅仅得到结论就是每一个步骤只能做一种动作，因为任何动作都是自反的，就是再做就回到上一步了。那么问题就是如何选择第一步，选完第一步，后面的计算是确定的。我当时的程序列出那些数据，那时候并不太明白格雷码的相关知识，也就作罢了。因为需要一个公式才能做那个题，否则就需要硬迭代，范围太大了。
那个格雷码的公式就是格雷码与他的索引之间的关系。就是TAOCP的g(k)与k的公式，是一个总结的结论然后用数学归纳法证明的。

g(k) = (b[n], b[n - 1], ... b[1])
k = (a[n], a[n - 1], ... a[1])
则对 j <= n 有 b[j] = a[j] XOR a[j + 1] 

这个公式就能解释这个中国环问题为什么是格雷码问题，不过高大爷写的过程的不太直接。其实就是找出k ++的格雷码增加的规律。
当 a[1] = 0的时候， k + 1不产生进位，则g(k)的最后一位取反(1 XOR a[2] =NOT(0 XOR a[2])
当 a[1] = 1的时候， k + 1产生一个传递的进位，另（假设n无范围） a[j + 1] = 0, a[j] = a[j - 1] = ... = a[1] = 1有

 X011...11                    Y10...00
+        1     
----------  k   对应 g(k)   ------------
 X100...00                    Z10...00

可以看出，这个进位使得g(k)的0最右0不变，并且第一个1不变，然后紧接这个1的位取反，Z = 1 XOR X = NOT(0 XOR X) = NOT(Y)
这样两个g(k)的变化规律刚好就是中国环的取环和下环规则:
1 最右一个环可随时取下和放上
2 可以取下或放上一个环，这个环的右边的环是放上的，右边的右边到最右边的环都是取下的。
再回到刚才的情况a[1] = 0 或者1的判断其实就是一个简单奇偶判断。
那么一个k可以求出g(k)，反过来g(k)求k就是 （利用第一个公式联j到n + 1位得到的式子,然后XOR这些式子消去中间的式子,这种推导在书上是不会写的，连一个习题都不算）

 
a[j] = b[j] XOR b[j + 1] ... XOR b[n]

上面这个公式对于编程的时候，是可以简单的动态规划的，就是求得a[j] = b[j] XOR a[j + 1],a[n] = b[n]. 于是当面对一个环的状态时，可以转换到对应的自然数索引k，根据k的奇偶这样就可以确定该如何往下走了。 PS,我看得这个书是双语版的，翻译有一些不妥的地方，坚定了我在豆瓣建了一个翻译勘误小组，因为有些翻译还是很容易误导别人的。还有上面的[]索引有些地方看上去超出了范围，其实本没有范围，对于自然数，超出就是0。