騰訊筆試題----格雷碼的實作

遞歸求格雷碼

　　昨天騰訊C++研發的一道筆試題，給定一個N，求這N位的格雷碼，如果不知道格雷碼的請自行問度娘。由于當時答題時間比較緊，是以沒有考慮清楚到底該怎麼做，隻是有一個大體的思路，但是還是沒有寫上去（感覺自己解決問題的能力還是弱啊.....）。

　　題目已經提示，使用遞歸求解，既然是遞歸，我當時想應該利用分治法求解，先設定一位，然後問題的規模就變成N-1，然後再求解，又聯想到劍指offer的第12題（列印1到最大的n位數），是以感覺這種思路應該是可以求解的，但是還有一個問題有待解決--怎麼滿足格雷碼的要求（每次變化1位），這個應該是個大問題，想了一會兒也沒想出來就放棄了....

　　交卷以後仔細考慮了一下，查了百度的資料，綜合成了自己的答案，下面是我的代碼及思路，如果有更好的想法可以留言交流，3Q！

1 #include <iostream>
 2 using namespace std;
 3 void print(int data[],int n){
 4     for(int i=0;i<n;i++)
 5         cout << data[i];
 6     cout << endl;
 7 }
 8 void mygrey(int cur,int data[],int n){
 9     if(cur==0){
10         data[cur]=1-data[cur];   //遞歸終止的條件，cur=0，cur的初始化是n-1，即先設定第0位上的數字
11         print(data,n);
12     }
13     else{
14         mygrey(cur-1,data,n);   //在data[cur]=0的情況下，設定前n-1位
15         data[cur]=1-data[cur];  //修改目前位的值
16         print(data,n);
17         mygrey(cur-1,data,n);   //在data[cur]=1的情況下，設定前n-1位的值
18     }
19 }
20 int main(){
21     const int n=4;
22     int data[n]={0};
23     print(data,n);
24     mygrey(n-1,data,n);
25     return 0;
26 }