格雷码(gray code)

（格雷码，Gray Code）格雷码是对十进制数的一种二进制编码。编码顺序与相应的十进制数的大小不一致。其特点是：对于两个相邻的十进制数，对应的两个格雷码只有一个二进制位不同。另外，最大数与最小数之间也仅有一个二进制位不同，以 4 位二进制数为例，格雷编码如下：

十进制数	格雷码	十进制数	格雷码
0	0000	8	1100
1	0001	9	1101
2	0011	10	1111
3	0010	11	1110
4	0110	12	1010
5	0111	13	1011
6	0101	14	1001
7	0100	15	1000

如果把每个二进制的位看作一个开关，则将一个数变为相邻的另一个数，只须改动一个开关。因此，格雷码广泛用于信号处理、数-模转换等领域。

下在是生成格雷码的方式，n为二进制位数。
当n=1时，格雷码只有{0,1}
当n=2时，格雷码有四个，前二个继承n=1时的两个数，把这两个数逆序做为后两个数，前二数首位加0，后两二数在首位加1。结果为{00, 01, 11, 10}
当n位二进制数时，前一半数，继承n-1时格雷码，前首位加0，后一半数，是n-1时格雷码的逆序，再首位加1。
见图解！

下面程序的任务是：由键盘输入二进制数的位数n(n<16)，再输入一个十进制数 m(0≤m<2n)，然后输出对应于 m 的格雷码（共 n 位，用数组 gr[] 存放）。

为了将程序补充完整，你必须认真分析上表的规律，特别是对格雷码固定的某一位，从哪个十进制数起，由0 变为 1，或由 1 变为 0。

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2025-01-08 21:28:22
 * 最后修改: 2025-01-08 21:34:10
 * 文件描述: 通过递推生成二进制n位格雷码中，十进制m对应的格雷码。也可以打印全部格雷码
****************************************************************/
#include <iostream>
#include <vector>
using namespace std;

void genGrayCode(vector<string> &grayCode,int n) {
    grayCode = {"0", "1"}; // 初始状态：1 位格雷码

    // 逐步扩展到 n 位
    for (int i = 2; i <= n; i++) {
        int size = grayCode.size();

        // 反向遍历，将当前格雷码扩展为 n 位
        for (int j = size - 1; j >= 0; j--) {
            grayCode.push_back("1" + grayCode[j]); // 前面加 '1'
        }

        // 正向遍历，将当前格雷码前面加 '0'
        for (int j = 0; j < size; j++) {
            grayCode[j] = "0" + grayCode[j];
        }
    }

}

int main() {
    int n,m;
    cout << "Enter the number of bits and number m: ";
    cin >> n>>m;
    vector<string> grayCode ;
    genGrayCode(grayCode,n);
    cout<<grayCode[m];
    // for (size_t i = 0; i < grayCode.size(); i++) { //打印所有格雷码
    //     cout << grayCode[i] << endl;
    // }

    return 0;
}

Previous Quiz

Back to Lesson

Next Quiz

计算机基础

格雷码(gray code)