一、实验内容
Gray码是一个长度为2^n的序列,序列中无相同元素,每个元素都是长度为n位的(0,1)串,相邻元素恰好只有一位不同。用分治策略设计一个算法对任意的n构造相应的Gray 码。
实验目的：掌握分治法
- 递归分解问题：将大问题分解为多个小规模的子问题。
- 处理小问题：对于足够小的子问题，直接解决（称为“基本情形”）。
- 合并结果：通过合并子问题的解，得到原问题的解。
二、实验原理
基本情形：当 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行// 前半部分的最高位设置为0ans[i][n - 1] = 0;// 后半部分的最高位设置为1ans[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^nint **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;
}
