4、格雷码
格雷码（Gray code），又称反射二进制码（reflected binary code），是一种二进制编码方式，相邻的两个数在二进制下只有一位不同，常用于数字通信、数字电路等领域。
格雷码具有以下几个特点：
- 相邻两个数在二进制下只有一位不同。
- 第一个数和最后一个数在二进制下有且仅有一位不同。
例如，当n=3时，格雷码序列如下：
| C++ |
|---|
| 000
001
011
010
110
111
101
100
|
可以看到，相邻的两个数在二进制下只有一位不同，第一个数和最后一个数在二进制下有且仅有一位不同，任意两个数在十进制下的差值仅为1。
格雷码的生成方法有多种，其中一种比较简单的方法是利用递归。以n=3为例，生成格雷码的步骤如下：
- 生成n=2的格雷码序列：00,01,11,10。
- 在每个数的左边添加0。
- 将n=2的格雷码序列倒序排列，并在每个数的左边添加1。
将上述步骤得到的结果连接起来即为n=3时的格雷码序列。
以下是使用递归生成n位格雷码序列的C++实现代码：
| C++ |
|---|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 | #include <iostream>
#include <vector>
using namespace std;
// 递归生成n位格雷码序列
vector<string> grayCode(int n) {
if(n == 0) {
return vector<string>{"0"};
}
if(n == 1) {
return vector<string>{"0", "1"};
}
vector<string> prev = grayCode(n-1);
vector<string> result;
for(int i = 0; i < prev.size(); i++) {
result.push_back("0" + prev[i]);
}
for(int i = prev.size()-1; i >= 0; i--) {
result.push_back("1" + prev[i]);
}
return result;
}
int main() {
int n = 3;
vector<string> res = grayCode(n);
for(int i=0;i < res.size(); i++) {
cout << res[i] << endl;
}
return 0;
}
|
输出为：
| C++ |
|---|
| 000
001
011
010
110
111
101
100
|
在上述代码中，grayCode函数用于递归生成n位格雷码序列。当n=0时，返回{"0"}；当n=1时，返回{"0", "1"}。对于n>1的情况，先递归生成n-1位格雷码序列，然后将其左边添加一个0，并倒序排列后，在每个数的左边添加一个1。最终得到n位格雷码序列。
以下是常用格雷码解法的汇总：
1、非递归解法
以下是C++实现的非递归解法的格雷码：
| C++ |
|---|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37 | #include <iostream>
#include <vector>
using namespace std;
vector<int> grayCode(int n) {
vector<int> result(1, 0);
for (int i = 0; i < n; i++) {
int size = result.size();
for (int j = size - 1; j >= 0; j--) {
result.push_back(result[j] | 1 << i);
}
}
return result;
}
// 将十进制数转换为二进制字符串
string toBinaryString(int n, int len) {
string s(len, '0');
for (int i = len - 1; i >= 0 && n > 0; i--) {
if (n % 2 == 1) {
s[i] = '1';
}
n /= 2;
}
return s;
}
int main() {
int n = 3;
vector<int> result = grayCode(n);
for (int i = 0; i < result.size(); i++) {
cout << toBinaryString(result[i], n) << " ";
}
cout << endl;
return 0;
}
|
2、递归解法
递归解法是一种简单易懂、代码量较少的解法。具体实现如下：
| C++ |
|---|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 | #include <iostream>
#include <vector>
using namespace std;
// 将n位格雷码存入result中
void grayCode(int n, vector<int>& result) {
if (n == 0) {
result.push_back(0);
return;
}
grayCode(n - 1, result);
int size = result.size();
for (int i = size - 1; i >= 0; i--) {
result.push_back(result[i] | 1 << (n - 1));
}
}
int main() {
int n = 3;
vector<int> result;
grayCode(n, result);
for (int i = 0; i < result.size(); i++) {
cout << result[i] << " ";
}
cout << endl;
return 0;
}
|
该算法的核心思想是递归计算n−1位格雷码，并在其基础之上将结果镜像翻转并在最高位加上1<<n−1。这样可以保证新生成的n位格雷码也满足相邻两个数字只有一位不同的要求。
3、公式法
公式法是一种快速计算格雷码的方法，在n给定时可以直接计算出第i个格雷码。具体公式如下：
gray(i)=i⊕⌊i/2⌋
其中，⊕表示异或运算。该公式的本质是利用了格雷码的对称性，在二进制数i和⌊i/2⌋之间进行异或运算，可以得到相邻两个格雷码的差值为1。
以下是公式法的代码实现：
| C++ |
|---|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 | include <iostream>
#include <vector>
using namespace std;
// 将十进制数转换为二进制字符串
string toBinaryString(int n, int len) {
string s(len, '0');
for (int i = len - 1; i >= 0 && n > 0; i--) {
if (n % 2 == 1) {
s[i] = '1';
}
n /= 2;
}
return s;
}
// 计算第i个格雷码的值
int grayCode(int i) {
return i ^ (i >> 1);
}
int main() {
int n = 3;
for (int i = 0; i < (1 << n); i++) {
cout << toBinaryString(grayCode(i), n) << " ";
}
cout << endl;
return 0;
}
|
在主函数中，我们使用了一个辅助函数toBinaryString()，将十进制数转化为指定长度的二进制字符串，并在输出结果时使用该函数进行格式化输出。
4、格雷码镜像翻转
格雷码的镜像翻转是指将n位格雷码从左向右翻转后得到的新格雷码。可以发现，将原格雷码和其镜像翻转后的格雷码进行异或运算，可以得到一个全为1的二进制数。具体实现如下：
| C++ |
|---|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41 | #include <iostream>
#include <vector>
using namespace std;
// 将十进制数转换为二进制字符串
string toBinaryString(int n, int len) {
string s(len, '0');
for (int i = len - 1; i >= 0 && n > 0; i--) {
if (n % 2 == 1) {
s[i] = '1';
}
n /= 2;
}
return s;
}
// 计算第i个格雷码的值
int grayCode(int i) {
return i ^ (i >> 1);
}
// 计算格雷码的镜像翻转
int reverseGrayCode(int n, int grayCode) {
int reverseGray = 0;
for (int i = 0; i < n; i++) {
reverseGray |= ((grayCode >> i) & 1) << (n - 1 - i);
}
return reverseGray;
}
int main() {
int n = 3;
for (int i = 0; i < (1 << n); i++) {
int gray = grayCode(i);
int reverseGray = reverseGrayCode(n, gray);
cout << toBinaryString(gray, n) << " ";
cout << toBinaryString(reverseGray, n) << endl;
}
return 0;
}
|
5、格雷码转二进制数
将n位格雷码转化为对应的二进制数，可以使用如下递推公式：
bn=gn⊕bn−1,b0=g0
其中，gn表示n位格雷码的第n位二进制数，bn表示n位格雷码对应的二进制数。具体实现如下：
| C++ |
|---|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42 | #include <iostream>
#include <vector>
using namespace std;
// 将十进制数转换为二进制字符串
string toBinaryString(int n, int len) {
string s(len, '0');
for (int i = len - 1; i >= 0 && n > 0; i--) {
if (n % 2 == 1) {
s[i] = '1';
}
n /= 2;
}
return s;
}
// 计算第i个格雷码的值
int grayCode(int i) {
return i ^ (i >> 1);
}
// 将n位格雷码转换为二进制数
int grayToBinary(int gray) {
int binary = gray & 1;
while ((gray >>= 1) > 0) {
binary ^= gray & 1;
binary <<= 1;
}
return binary;
}
int main() {
int n = 3;
for (int i = 0; i < (1 << n); i++) {
int gray = grayCode(i);
int binary = grayToBinary(gray);
cout << toBinaryString(gray, n) << " ";
cout << toBinaryString(binary, n) << endl;
}
return 0;
}
|
其他进制的格雷码
除了二进制格雷码以外，还可以计算其他进制的格雷码。例如，十进制格雷码的递推公式为：
gn=n⊕⌊n/2⌋
本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用