Chuyển đổi nhị phân sang Gray code bằng đệ quy trong C

Số nhị phân chỉ chứa hai bit 0 và 1. Mã Gray là loại mã nhị phân đặc biệt có tính chất: hai số liên tiếp chỉ khác nhau tối đa 1 bit. Tính chất này làm cho mã Gray hữu ích trong bản đồ Karnaugh, sửa lỗi, truyền thông, v.v.

Do đó, việc chuyển đổi nhị phân sang mã Gray là cần thiết. Dưới đây là thuật toán chuyển đổi nhị phân sang mã Gray bằng đệ quy.

Ví dụ

Input : 1001 Output : 1101

Thuật toán

Bước 1: Với đầu vào n:
    Bước 1.1: Nếu n = 0, gray = 0.
    Bước 1.2: Nếu hai bit cuối trái nhau,
        gray = 1 + 10 * (gọi đệ quy với n/10).
    Bước 1.3: Nếu hai bit cuối giống nhau,
        gray = 10 * (gọi đệ quy với n/10).
Bước 2: In gray.
Bước 3: Kết thúc.

Mã nguồn C++

#include <iostream>
using namespace std;

int binaryGrayConversion(int n) {
    if (!n)
        return 0;
    int a = n % 10;
    int b = (n / 10) % 10;
    if ((a && !b) || (!a && b))
        return (1 + 10 * binaryGrayConversion(n / 10));
    return (10 * binaryGrayConversion(n / 10));
}

int main() {
    int binary_number = 100110001;
    cout << "Số nhị phân là " << binary_number << endl;
    cout << "Mã Gray sau chuyển đổi là " << binaryGrayConversion(binary_number);
    return 0;
}

Kết quả

Số nhị phân là 100110001
Mã Gray sau chuyển đổi là 110101001