Gray Code

在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码（Gray Code）。请编写一个函数，使用递归方法生成N位的格雷码，并且保证这个函数的健壮性。

递归生成码表

这种方法基于格雷码是反射码的事实，利用递归的如下规则来构造：

1位格雷码有两个码字
(n+1)位格雷码中的前2n个码字等于n位格雷码的码字，按顺序书写，加前缀0
(n+1)位格雷码中的后2n个码字等于n位格雷码的码字，按逆序书写（将前一个结果反转一下），加前缀1

代码如下：

 C++ Code 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

#include <iostream>
#include <cstring>

using namespace std;

/** @brief
* 将10进制的dec转换为len位的二进制，保存到pBinary中
*
* @param dec int
* @param pBinary int*
* @param len int
* @return bool
*
*/
bool DecimalToBinary(int dec, int *pBinary, int len)
{
    if(NULL == pBinary) return false;
    if(len < 0) return false;

    while(dec != 0 && len > 0)
    {
        pBinary[--len] = dec % 2;
        dec /= 2;
    }

    if(dec != 0) return false; // len长度容纳不下转换后的二进制位

    while(len > 0)
    {
        pBinary[--len] = 0;
    }

    return true；
}

/** @brief
* 采用递归求的n位的格雷码
*
* @param n int - n位格雷码
* @param pCode int* 存储所求得的十进制格雷码
* @param index int& 记录pCode有效下标的后一位
* @return void
*
*/
void GrayCode(int n, int *pCode, int &index)
{
    if(NULL == pCode) return;

    if(0 == n)
    {
        pCode[index++] = 0;
        return;
    }

    if(1 == n)
    {
        pCode[index++] = 0;
        pCode[index++] = 1;
        return;
    }

    GrayCode(n - 1, pCode, index);

    int *pTemp = new int[index];
    for(int i = 0; i < index; ++i)
    {
        pTemp[i] = pCode[index - i - 1];
    }

    unsigned int highest = 1 << n - 1;
    int len = index;
    for(int i = 0; i < len; ++i)
    {
        pCode[index++] = pTemp[i] | highest;
    }

    delete[] pTemp;

}

int main()
{
    int codes[1000];
    int binary[1000];
    memset(codes, -1, sizeof(int) * 1000);

    int index = 0;
    int len = 3; // 格雷码长度
    GrayCode(len, codes, index);

    for(int i = 0; i < index; ++i)
    {
        DecimalToBinary(codes[i], binary, len);
        for(int j = 0; j < len; ++j)
        {
            cout << binary[j];
        }
        cout << endl;
    }
    cout << endl;

    return 0;
}