递归分治法格雷码

一、实验内容

Gray码是一个长度为2^n的序列,序列中无相同元素,每个元素都是长度为n位的(0,1)串,相邻元素恰好只有一位不同。用分治策略设计一个算法对任意的n构造相应的Gray 码。

实验目的：掌握分治法

1. 递归分解问题：将大问题分解为多个小规模的子问题。
2. 处理小问题：对于足够小的子问题，直接解决（称为“基本情形”）。
3. 合并结果：通过合并子问题的解，得到原问题的解。

二、实验原理

基本情形：当 n = 1 时，直接生成格雷码 [0] 和 [1]。

递归分解：如果 n > 1，调用 grayCode(n - 1, a / 2, ans) 递归地生成 n-1 位的格雷码，计算出前半部分的格雷码。通过递归调用生成较小规模的子问题（即 n-1 位的格雷码），这是分治法中的“递归分解问题”部分。

合并结果：递归返回后，利用已经生成的 n-1 位的格雷码来构建 n 位的格雷码。具体来说，前半部分的格雷码保持不变，后半部分的格雷码是前半部分格雷码的逆序，并在最高位设置 1。

 三、调试分析

• 1. a 和 n 的值在这时并不确定，应该在动态分配内存之前根据 n 计算 a = 2^n。将 a 和 n 的初始化放在 main 函数中，并且根据输入的 n 计算 a = 2^n，然后再进行内存分配。
• 2. ans[i + a / 2][j] = ans[a - i - 1][j]; 这样写会导致后半部分的格雷码顺序不正确，从而无法满足格雷码相邻元素只有一位不同的特性。
• 需要修正为 ans[i + a / 2][j] = ans[a / 2 - i - 1][j];，确保后半部分是前半部分的逆序。
• 3. 最高位的设置：前半部分的最高位设置为 0，后半部分的最高位设置为 1。
• 4. 递归终止条件：当 n == 1 时，直接生成 [0, 1] 作为基础格雷码。

#include <stdio.h>
#include <stdlib.h>

int n, a;//n代表位数，a=2^n代表格雷码元素个数

void grayCode(int n, int a, int **ans){
    if(n == 1){
        ans[0][0] = 0;
        ans[1][0] = 1;
        return;
    }

    grayCode(n - 1, a / 2, ans);//递归生成n-1位的格雷码.取倒数第二列，重复，直到n=1
   
    // 复制生成的前半部分到后半部分并设置最后一列
    for (int i = 0; i < a / 2; i++){//i代表第i行
        // 前半部分的最高位设置为0
        ans[i][n - 1] = 0;
        // 后半部分的最高位设置为1
        ans[i + a / 2][n - 1] = 1;
        // 复制前半部分的逆序
        for (int j = 0; j < n - 1; j++) {
            ans[i + a / 2][j] = ans[a / 2 - i - 1][j]; 
        }
    }
}

int main(){
    printf("请输入gray码的位数n:\n");
    scanf("%d", & n);
    a = 1 << n;  // a = 2^n, 将数字 1 左移 n 位，使得 1 变为 2^n
    int **ans = (int **)malloc(a * sizeof(int *));  // 动态分配二维数组
    for (int i = 0; i < a; i++) {
        ans[i] = (int *)malloc(n * sizeof(int));
    }

    grayCode(n, a, ans);

    // 打印格雷码
    printf("生成的Gray码是:\n");
    for (int i = 0; i < a; i++) {
        for (int j = 0; j < n; j++) {
            printf("%d", ans[i][j]);
        }
        printf("\n");
    }

    // 释放内存
    for (int i = 0; i < a; i++) {
        free(ans[i]);
    }
    free(ans);

    return 0;
}