2-14格雷码问题

（一）题目

问题描述

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

（二）解答

方法：分治递归

算法思路

运用分治递归求解$n$位的Gray码的思路为：

将求解 $n$位Gray码的问题划分成求解 $n-1$位Gray码的问题，再将求解 $n-1$位Gray码的问题划分成求解 $n-2$位Gray码的问题…直到划分成求解1位Gray码的问题，1位Gray码为0和1，通过1位Gray码构造出2位格雷码，再通过2位Gray码构造出3位Gray码…直到构造出 $n$位Gray码。

参考反射法，从$n-1$位Gray码构造$n$位Gray码的思路为：

（1）把$2^n$个Gray码分成两部分；

（2）把前$2^{n-1}$个Gray码的最高位置0，其余位与$n-1$位Gray码一一对应，无需更改；

（3）把后$2^{n-1}$个Gray码的最高位置1，其余位由$n-1$位Gray码上下翻转而来。

举例

以从1位Gray码开始构造3位Gray码为例：

将构造3位Gray码的问题分治为构造2位Gray码的问题，再将构造2位Gray码的问题分治为构造1位Gray码的问题，1位Gray码为0、1，从1位Gray码构造出2位Gray码，再从2位Gray码构造出3位Gray码即可。

构造流程如下：

源代码

#include<iostream>
#include<cstdio>
#include<cmath>

using namespace std;

int a[10000][10000];

//求num个n位Gray码
void GrayCode(int n, int num);

int main()
{
    int n;
    //输入Gray码位数n
    cin>>n;
    //n位Gray码的个数num
    int num = (int)pow(2.0, n);
    //求num个n位Gray码
    GrayCode(n, num);
    //输出num个n位Gray码
    //为了方便运算，Gray码的矩阵从左上角开始构建，最高位在最右边，输出时每个Gray码从右往左输出
    for (int i = 0; i < num; ++i)
    {
        for (int j = n - 1; j >= 0; --j)
        {
            cout<<a[i][j];
        }
        cout<<endl;
    }
    return 0;
}

void GrayCode(int n, int num)
{
    //分治到只有1位Gray码的情况
    if (n == 1)
    {
        a[0][0] = 0;
        a[1][0] = 1;
        return;
    }
    //将求解n位Gray码的问题划分成求解n-1位Gray码的问题
    GrayCode(n - 1, num / 2);
    //n位Gray码的前半部分最高位置0，其余位不变
    for (int i = 0; i < num / 2; ++i)
    {
        a[i][n-1] = 0;
    }
    //n位Gray码的后半部分最高位置1，其余位由n-1位Gray码翻转而来
    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];
        }
    }
}

结果示例

（三）总结

复杂度分析

递归函数GrayCode()的时间复杂度为：
$$T1(n)=\{\begin{array}{l}\mathrm{O}(1),n=1\\ T1(n-1)+\mathrm{O}(n\cdot 2^n),n>1\end{array}$$
因此，
$$\begin{array}{rl}T1(n)& =T1(n-1)+n\cdot 2^n\mathrm{O}(1)\\ & =\mathrm{O}(1)+2\cdot 2^2\mathrm{O}(1)+...+n\cdot 2^n\mathrm{O}(1)\\ & =\mathrm{O}(1)+(2n-1)2^n\mathrm{O}(1)\\ & =\mathrm{O}(n\cdot 2^n)\end{array}$$
整个算法的时间复杂度为：
$$\begin{array}{rl}T(n)& =\mathrm{O}(n\cdot 2^n)+T1(n)\\ & =\mathrm{O}(n\cdot 2^n)+\mathrm{O}(n\cdot 2^n)\\ & =\mathrm{O}(n\cdot 2^n)\end{array}$$