## 一.題目描述 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)`?之間的所有整數轉化為格雷碼。再有是使用移位計算的技巧進行實現。