c语言代码题 减治法生成格雷码 【问题描述】在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码（Gray Code），另外由于最大数与最小数之间也仅一位数不同，即“首尾相连”，因此又称循环码或反射码。对于n=3时，可以得到000，001，011，010，110，111，101，100的格雷码，当n=4的时候可以在3的基础上利用减治法生产格雷码，产生的方法就是，从左到右最高位填0，然后在从右到左最高位填1.image.png 【输入形式】输入一个整数n（0<n<10) 【输出形式】输出n位的格雷码 【样例输入】2 【样例输出】 00 01 11 10

格雷码可以用递归和迭代两种方式生成。这里介绍一下减治法生成格雷码的迭代实现，时间复杂度为 $O(2^n)$。

对于 $n = 1$ 的情况，格雷码为 0 和 1。可以用一个数组保存下来，然后依次输出。

对于 $n > 1$ 的情况，可以先递归地生成 $n-1$ 位的格雷码，然后再在前面加一个 0 和 1。其中，前面加 0 的格雷码不用变，前面加 1 的格雷码需要将 $n-1$ 位的格雷码倒序输出并在前面加上 1。

下面是一个 C 语言的实现：

#include <stdio.h>
#include <math.h>

int main() {
    int n;
    scanf("%d", &n);
    int size = pow(2, n);
    int gray[size];
    gray[0] = 0;
    for (int i = 1; i <= n; i++) {
        int half = pow(2, i-1);
        for (int j = half; j < 2*half; j++) {
            gray[j] = gray[2*half-1-(j-half)] + half;
        }
    }
    for (int i = 0; i < size; i++) {
        for (int j = n-1; j >= 0; j--) {
            printf("%d", (gray[i] >> j) & 1);
        }
        printf("\n");
    }
    return 0;
}

输入样例：

3

输出样例：

000
001
011
010
110
111
101
100