C++ 数学与算法系列之认识格雷码

#include <iostream>
#include <vector>
using namespace std;
/*
*实现格雷编码
*/
vector<string> grayCode(int num) {
    //存储格雷码
 vector<string> vec;
 if(num==1) {
        //出口：1位格雷码是已知的
  vec.push_back("0");
  vec.push_back("1");
  return vec;
 }
    //得到低位格雷码
 vector<string> vec_= grayCode(num-1);
 //对低位格雷码正向遍历，添加前缀 0
 vector<string>::iterator begin=vec_.begin();
 vector<string>::iterator end=vec_.end();
 for(; begin!=end; begin++) {
  vec.push_back("0"+*begin);
 }
 //对低位格雷码反向遍历,添加前缀 1 
 vector<string>::reverse_iterator rbegin=vec_.rbegin();
 vector<string>::reverse_iterator rend=vec_.rend();
 for(; rbegin!=rend; rbegin++) {
  vec.push_back("1"+*rbegin);
 }
 return vec;
}
//测试
int main(int argc, char** argv) {
 vector<string> vec=grayCode(4);
    cout<<"4 位格雷码："<<endl; 
 for(int i=0; i<vec.size(); i++) {
  cout<<vec[i]<<endl;
 }
 return 0;
}

4 位格雷码：
0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000

#include <iostream>
#include <vector>
using namespace std;
/*
*异或转换格雷编码
*/
void  yhGrayCode(int num) {
    //二进制
 vector<int> vec;
    //格雷码
 vector<int>  gc;
 //存储进位值
 int jinWei=0;
    //初始二进制的每一位为 0
 for(int i=0; i<num; i++) {
  vec.push_back(0);
 }
    //循序递增二进制，并且得到对应的格雷码
 while (jinWei!=1) {
  jinWei=0;
  gc.clear();
  //第一位不做异或操作
  gc.push_back(vec[0]);
  //反序遍历,求相邻两个数字的异或结果
  int i=0;
  for(; i<num-1; i++) {
   if(vec[i]==vec[i+1]) {
    gc.push_back(0);
   } else {
    gc.push_back(1);
   }
  }
        //输出格雷码
  for( i=0; i<gc.size(); i++) {
   cout<<gc[i]<<"";
  }
  cout<<endl;
  //更新二进制，递增 1 ，遇到 2 进位
  jinWei= (vec[num-1]+1) /  2;
  vec[num-1]=(vec[num-1]+1) % 2;
  for( i=num-2; i>=0; i--) {
   vec[i] = vec[i]+jinWei;
   jinWei= vec[i] / 2;
   vec[i]=vec[i] % 2;
  }
 }
}
//仅测试 4 位格雷码
int main(int argc, char** argv) {
 cout<<"\ 4 位格雷码："<<endl;
 yhGrayCode(4);
 return 0;
}

#include <iostream>
#include <stack>
using namespace std;
/*
* 4 位格雷码转二进制
*/
int main(int argc, char** argv) {
 //格雷码
 int grayCode[4]= {0,1,1,1};
 //二进制
 int binary[4]= {0};
 //格雷码最左一位自动解码
 binary[0]=grayCode[0];
 //格雷码从左边第二位开始解码
 for(int i=1; i<4; i++) {
  if( grayCode[i]==binary[i-1] ) {
   binary[i]=0;
  } else {
   binary[i]=1;
  }
 }
 //输出二进制
 for(int i=0; i<4; i++) {
  cout<<binary[i];
 }
 return 0;
}

#include <iostream>
#include <cmath>
using namespace std;
/*
* 卡诺图编码 
* num 表示二进制位数
*/ 
string* krtGrayCode(int num) {
 string* gc;
 //一阶格雷码
 if(num==1) {
  gc=new string[2] {"0","1"};
  return gc;
 }
 //格雷码个数与二进制位数关系
 int res=pow(2,num);
 //存储格雷码的数组
 gc=new string[res];
 //得到低阶格雷码
 string* dgc= krtGrayCode(num-1);
 //一阶格雷码
 string* oneGc=krtGrayCode(1);
 //奇偶标志
 int idx=1;
 //低阶格雷码的个数
 int count=pow(2,num-1);
 int gjIdx=0;
 //以行优先扫描低阶格雷码
 for(int i=0; i<count; i++) {
  if(idx % 2==1) {
   //奇数行，从左向右和 1 阶格雷码合并
   for(int j=0; j<=1; j++) {
    gc[gjIdx++]=dgc[i]+oneGc[j];
   }
  } else {
   //偶数行，从右向左和 1 阶格雷码合并合并
   for(int j=1; j>=0; j--) {
    gc[gjIdx++]=dgc[i]+oneGc[j];
   }
  }
  idx++;
 }
 return gc;
}
//测试
int main(int argc, char** argv) {
 int num=4;
 int count=pow(2,num);
 string* gc= krtGrayCode(num);
 for(int i=0; i<count ; i++) {
  cout<<gc[i]<<endl;
 }
 return 0;
}

0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000