一.题目描述
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位二进制数，最后输出结果。
关于格雷码的定义，百度有较为详细的解释，，传送门：?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 。
;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 binariesfor (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_typecout << result[x][y] << ” “;cout << ” : ” << k[x] << endl;}}
结果：
四.小结
格雷码的实现方法有多种，例如利用一些数学公式，将0~2^(n-1) 之间的所有整数转化为格雷码。再有是使用移位计算的技巧进行实现。
自己战胜自己是最可贵的胜利。
