分治法构建Gray码问题

问题描述

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

编程任务

利用分治策略试设计一个算法对任意的n构造相应的Gray码。

数据输入

输入数据n。

结果输出

程序运行结束时，输出得到的所有编码。

输入示例

3

#include<iostream>
#include <cmath>
using namespace std;
const int N = 1000;
int a[N][N];

void GrayCode(int n, int num) 
{
    if (n == 1) 
    {  
        a[0][0] = 0;
        a[1][0] = 1;
        return;
    }

    GrayCode(n - 1, num / 2);

    //前一半首位为0
    for (int i = 0; i < num / 2; ++i)
    {
        a[i][n - 1] = 0;
    }
        
    //后一半首位为1，且之中元素与前半镜像复制
    for (int i = num / 2; i < num; ++i) 
    {
        a[i][n - 1] = 1;

        for (int j = 0; j < n - 1; ++j)
        {
            a[i][j] = a[num - i - 1][j];
        }
    }
}

int main() 
{
    int n;
    cin >> n;

    //格雷码数目
    int num = (int)pow(2.0, n);

    GrayCode(n, num); 

   //格雷码顺序是从右到左，需要逆序输出
    for (int i = 0; i < num; ++i)
    {
        for (int j = n - 1; j >= 0; j--)
        {
            cout << a[i][j];
        }
        cout << endl;
    }
    return 0;
}