## 一.题目描述 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 <iostream> #include <vector> using namespace std; class Solution { public: vector<int> buildGrayCode(int n) { if (n == 0) { vector<int> result; result.push_back(0); return result; } else { vector<int> k = buildGrayCode(n - 1); vector<int> result(k); for (int i = k.size(); i > 0; --i) result.push_back(int(pow(2, n - 1) + k[i - 1])); return result; } } vector<int> Binarycout(int n, const int bit_num) // int to binaries { vector<int> 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<int> k = s.buildGrayCode(n); cout << "The gray code is: " << endl; vector<vector<int> > result; // int to binaries for (vector<vector<int>>::size_type i = 0; i < k.size() ; i++) result.push_back(s.Binarycout(k[i], n)); for (vector<vector<int>>::size_type x = 0; x < result.size(); x++) // vector<vector<int>>::size_type { for (vector<int>::size_type y = 0; y < result[x].size(); y++) // vector<int>::size_type cout << result[x][y] << " "; cout << " : " << k[x] << endl; } } ~~~ 结果：  ## 四.小结 格雷码的实现方法有多种，例如利用一些数学公式，将`0~2^(n-1)` 之间的所有整数转化为格雷码。再有是使用移位计算的技巧进行实现。