Chương trình Python chuyển số nguyên thành số La Mã

Chuyển đổi số nguyên dương num thành số La Mã (Roman numeral).

Bảng ký hiệu La Mã

Quy tắc trừ (Subtractive notation)

• IV = 4 (5-1), IX = 9 (10-1)
• XL = 40 (50-10), XC = 90 (100-10)
• CD = 400 (500-100), CM = 900 (1000-100)

Thuật toán (Greedy)

1. Tạo bảng cặp (giá trị, ký hiệu) giảm dần bao gồm cả các trường hợp trừ.
2. Với mỗi cặp: lấy số lần lặp d = num // val, thêm ký hiệu d lần, cập nhật num %= val.

Code Python

def solve(num):
    res = ""
    table = [
        (1000, "M"), (900, "CM"), (500, "D"), (400, "CD"),
        (100, "C"),  (90, "XC"),  (50, "L"),  (40, "XL"),
        (10, "X"),   (9, "IX"),   (5, "V"),   (4, "IV"),
        (1, "I")
    ]
    for val, roman in table:
        d, num = divmod(num, val)
        res += roman * d
    return res

# Test
print(solve(1520))  # MDXX
print(solve(1994))  # MCMXCIV
print(solve(58))    # LVIII

Trace ví dụ 1520

1520 // 1000 = 1 -> "M",   num=520
520  // 900  = 0 -> "",     num=520
520  // 500  = 1 -> "D",    num=20
20   // 100  = 0 -> "",     num=20
20   // 90   = 0 -> "",     num=20
20   // 50   = 0 -> "",     num=20
20   // 40   = 0 -> "",     num=20
20   // 10   = 2 -> "XX",   num=0
-> "MDXX"

Độ phức tạp

• Thời gian: O(1) - bảng cố định 13 cặp, số vòng lặp tối đa ~15 (khi num=3999).
• Không gian: O(1) - kết quả độ dài tối đa ~15 ký tự.

Giới hạn

Số La Mã chuẩn chỉ biểu diễn đến 3999 (MMMCMXCIX). Số lớn hơn cần ký hiệu đặc biệt (vinculum).