自动生成格雷码算法
典型的二进制格雷码（Binary Gray Code）简称格雷码，在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码（Gray Code），另外由于最大数与最小数之间也仅一位数不同，即“首尾相连”，因此又称循环码或反射码。
自动生成格雷码的算法主要利用以下规则：
1. 1位格雷码有两个码字。
2. (n+1)位格雷码中的前2n个码字等于n位格雷码的码字，按顺序书写，加前缀0。
3. (n+1)位格雷码中的后2n个码字等于n位格雷码的码字，按逆序书写，加前缀1。
4. (n+1)位格雷码的集合 = n位格雷码集合(顺序)加前缀0 + n位格雷码集合(逆序)加前缀1。
简而言之，就是后面的格雷码等于其相邻的前面的格雷码按顺序书写，加前缀0，再按逆序书写，加前缀1。如下图所示：
按照这个思路很容易的实现代码：
- void generaterGrayCode(int n)
- {
- vector<string> grayCodeVec;
- //当n为1的时候的格雷码
- string aa = "0";
- string bb = "1";
- grayCodeVec.push_back(aa);
- grayCodeVec.push_back(bb);
- //产生大于两位的格雷码，n位格雷码的数量为2^n个
- if (n > 1)
- {
- for (int i = 2; i <= n; i++)
- {
- //设置一个临时存储空间来存储n-1位格雷码
- vector<string> tempGrayCodeVec;
- for (size_t k = 0; k < grayCodeVec.size(); k++)
- {
- tempGrayCodeVec.push_back(grayCodeVec[k]);
- }
- //在前面产生的n-1位格雷码前面添加一位数0产生2^(n-1)个n位格雷码，并替换掉原来的n-1位格雷码
- int tempGrayCodeVecSize = tempGrayCodeVec.size();
- for (int j = 0; j < tempGrayCodeVecSize; j++)
- {
- string tempbitzero = "0";
- tempbitzero += tempGrayCodeVec[j];
- grayCodeVec[j] = tempbitzero;
- }
- //将前面产生的n-1位格雷码的顺序反转
- //在反转后的n-1位格雷码前面添加一位数1产生剩下2^(n-1)个n位格雷码，并存储起来
- for (int jj = tempGrayCodeVecSize-1; jj >= 0; jj--)
- {
- string tempbitone = "1";
- tempbitone += tempGrayCodeVec[jj];
- grayCodeVec.push_back(tempbitone);
- }
- //释放掉临时存储空间
- tempGrayCodeVec.clear();
- }
- }
- //输出n位格雷码
- for (size_t i = 0; i < grayCodeVec.size(); i++)
- {
- cout << grayCodeVec[i] << endl;
- }
- cout << endl;
- }