โปรแกรม C แปลงเลขฐานสองเป็นรหัส Gray ด้วย Recursion

เลขฐานสอง (Binary) คือตัวเลขที่ประกอบด้วยบิต 0 และ 1 เท่านั้น

รหัส Gray (Gray code) เป็นรหัสฐานสองพิเศษที่มีคุณสมบัติว่า ตัวเลขที่ติดกันจะต่างกันไม่เกิน 1 บิต คุณสมบัตินี้ทำให้รหัส Gray มีประโยชน์ใน K-maps, การแก้ไขข้อผิดพลาด, การสื่อสาร ฯลฯ

ดังนั้นการแปลงจากฐานสองเป็นรหัส Gray จึงจำเป็น มาดูอัลกอริทึมการแปลง binary to gray code แบบเรียกซ้ำ (recursion)

ตัวอย่าง

Input : 1001
Output : 1101

อัลกอริทึม

ขั้นตอน 1: รับค่า n
    ขั้นตอน 1.1: ถ้า n = 0, gray = 0
    ขั้นตอน 1.2: ถ้าบิตสุดท้าย 2 ตัวตรงข้ามกัน (0 และ 1 หรือ 1 และ 0)
        gray = 1 + 10 * (เรียกขั้นตอน 1 ด้วย n/10)
    ขั้นตอน 1.3: ถ้าบิตสุดท้าย 2 ตัวเหมือนกัน
        gray = 10 * (เรียกขั้นตอน 1 ด้วย n/10)
ขั้นตอน 2: แสดงผล gray
ขั้นตอน 3: จบ

โค้ดตัวอย่าง

#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 << "The binary number is " << binary_number << endl;
    cout << "The gray code conversion is " << binaryGrayConversion(binary_number);
    return 0;
}

ผลลัพธ์

The binary number is 100110001
The gray code conversion is 110101001