Chương trình Python tạo mã Gray bằng đệ quy

Khi cần tạo dãy mã Gray nhị phân bằng đệ quy (hoặc lặp), ta có thể xây dựng danh sách bắt đầu từ ['0', '1'] và mở rộng dần.

Ví dụ

def generate_gray_list(n):
    if n <= 0:
        return
    gray_list = ["0", "1"]
    i = 2
    while i < (1 << n):  # 1 << n tương đương 2^n
        # Sao chép ngược danh sách hiện tại
        for j in range(i - 1, -1, -1):
            gray_list.append(gray_list[j])
        # Thêm tiền tố '0' cho nửa đầu
        for j in range(i):
            gray_list[j] = "0" + gray_list[j]
        # Thêm tiền tố '1' cho nửa sau
        for j in range(i, 2 * i):
            gray_list[j] = "1" + gray_list[j]
        i <<= 1  # Nhân i với 2
    for code in gray_list:
        print(code)

num = 3
print("Số bit:", num)
print("Danh sách mã Gray:")
generate_gray_list(num)

Kết quả

Số bit: 3
Danh sách mã Gray:
000
001
011
010
110
111
101
100

Giải thích

• Khởi tạo danh sách với 2 mã Gray 1 bit: '0', '1'.
• Lặp cho đến khi độ dài mã đạt n bit.
• Mỗi bước: đảo ngược danh sách hiện tại và nối vào cuối (phản xạ).
• Thêm tiền tố '0' cho nửa đầu, '1' cho nửa sau.
• Sử dụng dịch bit trái (<<) để nhân đôi kích thước.