（ヅ） 写了： 2023年 5月 3日 15:17
k位格雷码的主要特征：
0. n个数字分别是0到n-1
1. 相邻位只相差一位数字
2. 首尾同样只相差一个数字
举例k = 3,n = 2^k = 8的时候
000
001
011
010
110
111
101
100
用归纳法容易证明格雷码能够一定满足这两个特征.但是这里有个限制，n一定是2^k
要求证明:对于任意正整数n，一定可以构造出一个低配格雷码，满足条件0和1.
对n做数学归纳法：When n = 1, the claim is clearly true. Let n > 1 and assume that the claim holds for all positive integers less than n. If n = 2
k, there exists k位格雷码. So it suffices to prove the claim for n such that 2
k < n < 2
k+1. By induction hypothesis, there is a 低配格雷码 for n-2
k, meaning that we can re-arrange the numbers 0, ..., n-2
k-1 such that they 满足条件0和1. Write this 低配格雷码 in k-digit binary, and then add a new digit 1 to the left of each of those k-digit numbers. The result is an arrangement of the numbers 2
k, ..., n-1 such that they 满足条件1. Say the first number of this sequence is 1d
k-1...d
0, in binary. Next, fix a k位格雷码 (for 2
k), which is actually a
circle that satisfies 条件0和1. So we can make it into a sequence whose last number is d
k-1...d
0 = 0d
k-1...d
0 in binary. Note that the difference between 0d
k-1...d
0 and 1d
k-1...d
0 is precisely one digit. Now, we can connect the two sequences together to get a 低配格雷码 for n.