Gray Code（2016腾讯软件开发笔试题）
最后更新于：2022-04-01 22:55:31
## 一.题目描述
The gray code is a binary numeral system where two successive values differ in only one bit.
Given a non-negative integer n representing the total number of bits in the code, print the sequence of
gray code. A gray code sequence must begin with 0.
For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:
00 - 0
01 - 1
11 - 3
10 - 2
> Note:
> • For a given n, a gray code sequence is not uniquely defined.
> • For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.
> • For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.
## 二.题目分析
昨天腾讯也刚考了这道题，因为不是本人考试，所以不是很记得题目是否有其他限制，这里只是按照腾讯的基本要求：**用递归实现格雷码的生成**，纯属抛砖引玉。
这里，主要函数只是实现了`0~2^(n-1)`的自然数到格雷码排列的映射，还需要一个函数，将`int`型数据转换为`n`位二进制数，最后输出结果。
关于格雷码的定义，百度有较为详细的解释，传送门：[http://baike.baidu.com/link?url=_X6MWv6OPt93bbuMIXnmXIqMKeQgnI2xPa1xkgPlrZR_7uG8xYKec3B67zm8JhqqEdylnUBC7Op8oWp0vQe_bq](http://baike.baidu.com/link?url=_X6MWv6OPt93bbuMIXnmXIqMKeQgnI2xPa1xkgPlrZR_7uG8xYKec3B67zm8JhqqEdylnUBC7Op8oWp0vQe_bq)
以下列出`1`位到`4`位的格雷码，可以从中发现一些规律：
可以发现，一组n位格雷码有 `2^n` 个二进制排列组成，其前 `2^(n-1)` 个数，除去最高位的`0`，剩下的位数与 `n - 1` 位格雷码完全一致；
其次，一组n位格雷码，其后 `2^(n-1)` 个数，除去最高位的`1`，剩下的位数与 `n - 1` 位格雷码的**倒序**完全一致；
基于以上两点性质，我们有理由相信，一组 `n` 位的格雷码，可以递归地从 `n-1` 位的格雷码生成。
## 三.实例代码
其中，主要的函数： `buildGrayCode()`只是实现了`0~2^(n-1)`的自然数到格雷码排列的映射。举个例子，对于`2`位的格雷码，其`int`型数据的排列顺序为：`0 1 3 2`。而函数`Binarycout()` ，将`0 1 3 2` 转换为：`00 01 11 10` 。
~~~
#include
#include
using namespace std;
class Solution
{
public:
vector buildGrayCode(int n)
{
if (n == 0)
{
vector result;
result.push_back(0);
return result;
}
else
{
vector k = buildGrayCode(n - 1);
vector result(k);
for (int i = k.size(); i > 0; --i)
result.push_back(int(pow(2, n - 1) + k[i - 1]));
return result;
}
}
vector Binarycout(int n, const int bit_num) // int to binaries
{
vector result;
for (int i = bit_num - 1; i >= 0; i--)
{
result.push_back((n >> i) & 1);
}
return result;
}
};
~~~
简单的测试代码：
~~~
#include "GrayCode.h"
int main()
{
Solution s;
int n;
cout << "Please input the value of bit: ";
cin >> n;
vector k = s.buildGrayCode(n);
cout << "The gray code is: " << endl;
vector > result; // int to binaries
for (vector>::size_type i = 0; i < k.size() ; i++)
result.push_back(s.Binarycout(k[i], n));
for (vector>::size_type x = 0; x < result.size(); x++) // vector>::size_type
{
for (vector::size_type y = 0; y < result[x].size(); y++) // vector::size_type
cout << result[x][y] << " ";
cout << " : " << k[x] << endl;
}
}
~~~
结果：
## 四.小结
格雷码的实现方法有多种，例如利用一些数学公式，将`0~2^(n-1)` 之间的所有整数转化为格雷码。再有是使用移位计算的技巧进行实现。
';