gray码

created by Dejavu
[完结]

• 介绍
  Gray码是一种数字编码方式，可以使相邻的两个数之间只有一位的差别。
  gray码生成的原理是利用镜像的方式，复制低位的gary码来合成高位的gray码，想要得到二进制的3位全排列只需生成1位的全排列然后做镜像在镜像上方高位添0下方低位添1，即可得到2位的全排列，然后重复上述步骤来得到3位全排列，如下图所示

  
  gray码生成过程

• 实现
  这里的 n代表的是二进制位数

  #include <iostream>
  #include <math.h>
  using namespace std;
  #define MAXN 100
  
  void gray(int n,int *code) {
    int t(0);
    for(int i=0;i<n;t+=code[i++]);
    if(t&1) for(n--;!code[n];n--);
    code[n-1] = 1-code[n-1];
  }
  
  int main() {
    int code[MAXN] = {0};
    int n = 4;
    for(int i=0;i<pow(2,n);i++) {
        for(int j=0;j<n;j++) cout << code[j] << ' ';
        cout << endl;
        gray(n,code);
    }
  }