出一个题目

[（ヅ）]

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.

[FoxMe]

啥意思？截短不就行了？

[（ヅ）]

啥意思？截短不就行了？

比如n = 7如果你的意思是从n=8(k=3)的格雷码里面选前7个，这7个数字包括了7。

[YWY]

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₀, 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₀ = 0d_k-1...d₀ in binary. Note that the difference between 0d_k-1...d₀ and 1d_k-1...d₀ is precisely one digit. Now, we can connect the two sequences together to get a 低配格雷码 for n.

[（ヅ）]

对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₀, 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₀ = 0d_k-1...d₀ in binary. Note that the difference between 0d_k-1...d₀ and 1d_k-1...d₀ is precisely one digit. Now, we can connect the two sequences together to get a 低配格雷码 for n.

赞, I am convinced!