Có nhiều cách xây dựng Gray code:

• Đệ quy phản chiếu: từ Gray(n-1), thêm tiền tố 0 cho toàn bộ dãy, rồi thêm tiền tố 1 cho dãy còn lại nhưng theo thứ tự ngược.
• Công thức bitwise: với số nhị phân i, mã Gray tương ứng là

G(i)=i⊕(i≫1)

• Cách lật bit theo vị trí thấp nhất của số bước: bắt đầu từ dãy toàn 0, mỗi bước chỉ cần lật 1 bit xác định bởi số thứ tự của bước.

Ví dụ với n = 3, ta thu được dãy:

        000, 001, 011, 010, 110, 111, 101, 100

Thuật toán có ưu điểm là:

• Sinh tuần tự dễ dàng, không cần lưu toàn bộ dãy.
• Mỗi bước chỉ thay đổi 1 bit, nên rất hữu ích trong các ứng dụng cần giảm sai số đo, trong tối ưu tổ hợp, hoặc trong thiết kế mạch số.

#include <bits/stdc++.h>

using namespace std;

vector<string> gray_code(int n) {

    vector<string> res;

    int total = 1 << n; // 2^n

    for (int i = 0; i < total; i++) {

        int g = i ^ (i >> 1); // công thức Gray code

        string s;

        for (int k = n - 1; k >= 0; k--) {

            s.push_back( ( (g >> k) & 1 ) ? '1' : '0' );

        }

        res.push_back(s);

    }

    return res;

}

 

int main() {

    int n;

    cout << "Nhap n: ";

    cin >> n;

    auto gray = gray_code(n);

    cout << "Day Gray code do dai " << n << ":\n";

    for (auto &s : gray) cout << s << "\n";

}