Chương trình chuyển đổi mã Gray cho số cho trước bằng Python

Cho số n, tìm mã Gray thứ n (giá trị thập phân). Mã Gray: các số nhị phân liên tiếp khác nhau đúng 1 bit.

Ví dụ: n=12 (1100) → mã Gray 1010 → 10.

Giải thuật

• Công thức đệ quy: gray(n) = x + gray(2*x - n - 1), trong đó x là lũy thừa 2 lớn nhất ≤ n.
• Cơ sở: n=0 → 0.
• Tìm x bằng cách nhân đôi cho đến khi 2*x > n.

Ví dụ minh họa

class Solution:
    def solve(self, n):
        if n == 0:
            return 0
        x = 1
        while x * 2 <= n:
            x *= 2
        return x + self.solve(2 * x - n - 1)

ob = Solution()
n = 12
print(ob.solve(n))

Đầu vào

12

Đầu ra

10