算法分析与设计-格雷码问题（分治递归）（通俗易懂，附源码和图解，含时间复杂度分析）（c++)

2-14格雷码问题（一）题目问题描述Gray码是一个长度为2n2^n2n的序列。序列中无相同元素，每个元素都是长度为 n的(0,1)串，相邻元素只有一位不同。用分治策略设计一个算法对任意的 n构造相应的Gary码。（二）解答方法：分治递归算法思路运用分治递归求解nnn位的Gray码的思路为：将求解 nnn位Gray码的问题划分成求解 n−1n-1n−1位Gray码的问题，再将求解 n−1n-1n−

是奶酥吖_

7385人浏览 · 2022-03-18 23:52:33

是奶酥吖_ · 2022-03-18 23:52:33 发布

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{cases} \Omicron(1),\;\qquad \qquad \qquad \quad \qquad n=1\\ T1(n-1)+\Omicron(n\cdot2^n),\qquad n>1\\ \end{cases}$
因此，
$\begin{aligned}T1(n)&=T1(n-1)+n\cdot2^n\Omicron(1)\\&=\Omicron(1)+2\cdot2^2\Omicron(1)+...+n\cdot2^n\Omicron(1)\\&=\Omicron(1)+(2n-1)2^n\Omicron(1)\\&=\Omicron(n\cdot2^n)\end{aligned}$
整个算法的时间复杂度为：
$\begin{aligned}T(n)&=\Omicron(n\cdot2^n)+T1(n)\\&=\Omicron(n\cdot2^n)+\Omicron(n\cdot2^n)\\&=\Omicron(n\cdot2^n)\end{aligned}$