Преобразование числа в римское

Решение

Понимание задачи

Преобразовать целое число (1-3999) в римскую запись. Используется принцип вычитания: V (5) перед X (10) означает 4, а не 15.

Оптимальный алгоритм: Greedy с таблицей значений

def int_to_roman(num):
    """
    Преобразует число в римскую запись.
    """
    # Таблица (значение, символ) отсортирована по убыванию
    values = [
        (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')
    ]
    
    result = ''
    for value, symbol in values:
        count = num // value
        if count:
            result += symbol * count
            num -= value * count
    
    return result

Как это работает

Пример: 1994

Шаг 1: 1994 / 1000 = 1 -> 'M', остаток 994 Шаг 2: 994 / 900 = 1 -> 'CM', остаток 94 Шаг 3: 94 / 90 = 1 -> 'XC', остаток 4 Шаг 4: 4 / 4 = 1 -> 'IV', остаток 0

Результат: 'MCMXCIV'

Сложность

• Временная: O(1) — максимум 13 значений в таблице
• Пространственная: O(1) — результат максимум 4 символа на digit

Расширенная версия с комментариями

def int_to_roman_detailed(num):
    """
    Преобразует число в римскую запись.
    
    Args:
        num: Число от 1 до 3999
    
    Returns:
        Строка с римской записью
    
    Raises:
        ValueError: Если число вне диапазона
    """
    if not isinstance(num, int) or num <= 0 or num >= 4000:
        raise ValueError("Число должно быть от 1 до 3999")
    
    # Таблица с поддержкой субтрактивной нотации
    mapping = [
        (1000, 'M'),  # M = 1000
        (900, 'CM'),  # CM = 900 (1000 - 100)
        (500, 'D'),   # D = 500
        (400, 'CD'),  # CD = 400 (500 - 100)
        (100, 'C'),   # C = 100
        (90, 'XC'),   # XC = 90 (100 - 10)
        (50, 'L'),    # L = 50
        (40, 'XL'),   # XL = 40 (50 - 10)
        (10, 'X'),    # X = 10
        (9, 'IX'),    # IX = 9 (10 - 1)
        (5, 'V'),     # V = 5
        (4, 'IV'),    # IV = 4 (5 - 1)
        (1, 'I')      # I = 1
    ]
    
    roman = ''
    for value, numeral in mapping:
        count = num // value
        roman += numeral * count
        num -= value * count
    
    return roman

Тестирование

# Базовые случаи
assert int_to_roman(1) == 'I'
assert int_to_roman(3) == 'III'
assert int_to_roman(4) == 'IV'
assert int_to_roman(5) == 'V'
assert int_to_roman(9) == 'IX'
assert int_to_roman(27) == 'XXVII'
assert int_to_roman(58) == 'LVIII'
assert int_to_roman(1994) == 'MCMXCIV'
assert int_to_roman(3999) == 'MMMCMXCIX'

# Граничные случаи
assert int_to_roman(1000) == 'M'
assert int_to_roman(400) == 'CD'
assert int_to_roman(40) == 'XL'
assert int_to_roman(4) == 'IV'

Альтернативные подходы

Способ 1: Перевёрнутое преобразование (неоптимально)

def roman_to_int(s):
    roman_values = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
    total = 0
    prev_value = 0
    for char in reversed(s):
        value = roman_values[char]
        if value < prev_value:
            total -= value
        else:
            total += value
        prev_value = value
    return total

• Преобразование из римского в десятичное
• Не решает исходную задачу

Способ 2: С использованием divmod (более elegantly)

def int_to_roman_divmod(num):
    mapping = [(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')]
    
    roman = ''
    for value, numeral in mapping:
        count, num = divmod(num, value)
        roman += numeral * count
    return roman

• Использует divmod вместо целочисленного деления
• Более Pythonic

Граничные случаи и проверка

# Числа с повторениями
assert int_to_roman(3) == 'III'  # Максимум 3 одинаковых
assert int_to_roman(30) == 'XXX'
assert int_to_roman(300) == 'CCC'
assert int_to_roman(3000) == 'MMM'

# Субтрактивная нотация
assert int_to_roman(4) == 'IV'    # Не 'IIII'
assert int_to_roman(9) == 'IX'    # Не 'VIIII'
assert int_to_roman(40) == 'XL'   # Не 'XXXX'
assert int_to_roman(90) == 'XC'   # Не 'LXXXX'
assert int_to_roman(400) == 'CD'  # Не 'CCCC'
assert int_to_roman(900) == 'CM'  # Не 'DCCCC'

# Комплексные числа
assert int_to_roman(2023) == 'MMXXIII'
assert int_to_roman(1949) == 'MCMXLIX'

Выводы

• Greedy алгоритм с таблицей — оптимальное решение
• O(1) время — количество операций ограничено
• Таблица включает субтрактивные пары — 4, 9, 40, 90, 400, 900
• Для QA: проверить граничные числа, повторения, субтрактивную нотацию
• Валидные диапазоны: 1-3999 (древний Рим не имел нуля)