[16テンセントオンラインペン試験問題1]-GrayCode

1組のツリーの符号化において、任意の2つの隣接するコードが1ビットのバイナリしか異なる場合、この符号化をグレイコード(GrayCode)と呼ぶ.
再帰的な方法でNビットのグレイコードを生成し、この関数の頑丈性を保証する関数を作成してください.
問題が始まるのを見て、確かに考えがないので、まずグレイコードの木の構造を描いてみましょう.3ビットグレイコード.
                       
                  0          1
              0    1      1    0
           0  1 1  0  0 1  1  0
この法則は,最高ノード0と1に対応するサブツリーが対称であることを見いだした.
つまり
f(n+1)=‘0’+f(n)(最上位が0のときn番目のグレイコード)
f(n+1)='1'+f'(n)(最高位が1の場合f'(n)はnビット目のグレイ符号の対称解に対応する)
法則は発見されたが,再帰的に解く対称感覚では手がつけにくい.
私たちは再帰を完成しやすい法則を見つけなければならない.
木を観察して、現在の面m個の点1の個数が奇数の時、私達の後の解、私達は左の子の木1、右の子の木0を加えます.偶数の場合は、左サブツリー0、右サブツリー1を加えます.
この法則に従ってコードを書きます.

#include<iostream>
#include <vector>
using namespace std;

void GrayCode(int n,vector<int>temp,vector<vector<int>>&ret,int numof1)
{
    if(n == 0) // 
    {
        ret.push_back(temp);
        return;
    }
    if(numof1%2==0) // 1
    {
        temp.push_back(0);// 0
        GrayCode(n-1,temp,ret,numof1);
        temp.pop_back();// pop 0 
        temp.push_back(1); 
        GrayCode(n-1,temp,ret,numof1+1);//1 1
    }
    else if(numof1%2==1) // 1
    {
        temp.push_back(1);// 1
        GrayCode(n-1,temp,ret,numof1+1);
        temp.pop_back();
        temp.push_back(0);// 0
        GrayCode(n-1,temp,ret,numof1);
    }
    
    
}

テストコード

int main(){
    vector<int> temp;// 
    vector<vector<int> > ret;// 
    int n = 8; //n 
    GrayCode(n,temp,ret,0);
    for(int i=0;i<ret.size();++i)
    {
        cout<<endl;
        for(int j=0;j<ret[0].size();++j)
        {
            cout<<ret[i][j];
        }
    }
}