描述 Description
The gray code is a binary numeral system where two successive values differ in only one bit.
Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.
For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:
00 - 0
01 - 1
11 - 3
10 - 2
Note:
For a given n, a gray code sequence is not uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.
For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.
分析 Anaysis
格雷码相关知识可参考博客[格雷码Gray Code]。
算法复杂度
方法1和方法都是O(2^n)的。
方法1
二进制码转换成二进制格雷码
二进制码转换成二进制格雷码，其法则是保留二进制码的最高位作为格雷码的最高位，而次高位格雷码为二进制码的高位与次高位相异或，而格雷码其余各位与次高位的求法相类似。
二进制码 ----> 格雷码(编码)：从最右边一位起，依次将每一位与左边一位异或(XOR)，作为对应格雷码该位的值，最左边一位不变(相当于左边是0)。
公式表示：G：格雷码 B：二进制码
整个数的转换G(N) = (B(n) >> 1) XOR B(n)
方法2
镜射排列生成格雷码
生成二进制格雷码方式2：n位元的格雷码可以从n-1位元的格雷码以上下镜射后加上新位元的方式快速的得到，如图所示。
仔细观察格雷码的结构，我们会有以下发现：
1、除了最高位（左边第一位），格雷码的位元完全上下对称（看下面列表）。比如第一个格雷码与最后一个格雷码对称（除了第一位），第二个格雷码与倒数第二个对称，以此类推。
2、最小的重复单元是 0 , 1。
000
001
011
010
110
111
101
100
所以，在实现的时候，我们完全可以利用递归或者非递归也可以，在每一层前面加上0或者1，然后就可以列出所有的格雷码。
比如：
第一步：产生 0, 1 两个字符串。
第二步：在第一步的基础上，正向每一个字符串都分别加上0，然后反向迭代每一个字符串都加上1，但是每次只能加一个，所以得做两次。这样就变成了 00,01,11,10 （注意对称）。
第三步：在第二步的基础上，再给每个字符串都加上0和1，同样，每次只能加一个，这样就变成了 000,001,011,010,110,111,101,100。这样就把3位元格雷码生成好了。
如果要生成4位元格雷码，我们只需要在3位元格雷码上再加一层0,1就可以了： 0000,0001,0011,0010,0110,0111,0101,0100,1100,1101,1110,1010,0111,1001,1000.
也就是说，n位元格雷码是基于n-1位元格雷码产生的。
代码 Code
方法1
进制转换代码
vector<int> gray3(int n) {
/*
* 通过二进制数转换成格雷码二进制数
*/
vector<int> gray_code = vector<int>{};
gray_code.reserve((unsigned long) (1 << n));
int size = 1 << n;
for (int i = 0; i < size; i++)
gray_code.push_back((i >> 1) ^ i);
return gray_code;
}
方法2
镜像排列算法
vector<int> gray2(int n) {
/*
* 格雷码二进制整数的镜射排列实现
*/
vector<int> gray_code = vector<int>{0};
gray_code.reserve((unsigned long) (1 << n));
int high_bit_pos = 1;
vector<int>::reverse_iterator gray_it;
for (int i = 0; i < n; i++) {
//逆序最高位置1
for (gray_it = gray_code.rbegin(); gray_it != gray_code.rend(); gray_it++)
gray_code.push_back(high_bit_pos | *gray_it);
high_bit_pos <<= 1;
}
return gray_code;
}
测试
#include <iostream>
#include <vector>
#include <sstream>
using namespace std;
void test_bray_str(int n, int func = 1) {
vector<string> (*gray)(int) = NULL;
if (func == 0) {
gray = gray0;
cout << "testing gray 0" << endl;
} else if (func == 1) {
gray = gray1;
cout << "testing gray 1" << endl;
}
vector<string> gray_code = gray(n);
vector<string>::iterator gc_it;
for (gc_it = gray_code.begin(); gc_it != gray_code.end(); gc_it++)
cout << *gc_it << endl;
}
void test_bray_int(int n, int func = 3) {
vector<int> (*gray)(int) = NULL;
if (func == 2) {
gray = gray2;
cout << "testing gray 2" << endl;
} else if (func == 3) {
gray = gray3;
cout << "testing gray 3" << endl;
}
vector<int> gray_code = gray(n);
vector<int>::iterator gc_it;
for (gc_it = gray_code.begin(); gc_it != gray_code.end(); gc_it++)
cout << *gc_it << endl;
}
int main() {
istringstream oss("3");
std::cin.rdbuf(oss.rdbuf());
int n;
cin >> n;
test_bray_str(n, 1);
test_bray_int(n, 2);
return 0;
}
测试结果
testing gray 1
000
001
011
010
110
111
101
100
testing gray 2
0
1
3
2
6
7
5
4