Алгоритмы римских цифр: Реализация на Python, JavaScript и Java

Преобразование между римскими цифрами и целыми числами — это классическая задача программирования, которая встречается на собеседованиях, в спортивном программировании и реальных приложениях. В этом руководстве представлены оптимизированные реализации на Python, JavaScript и Java с объяснением алгоритмов.

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

Нам нужно решить две взаимосвязанные задачи:

1. Целое число в римское: Преобразовать арабское число (например, 1994) в римские цифры (MCMXCIV).
2. Римское в целое число: Преобразовать римские цифры (например, MCMXCIV) в арабское число (1994).

Ограничения

• Диапазон ввода: от 1 до 3999 (стандартный диапазон римских цифр).
• Использование стандартной субтрактивной нотации (IV, IX, XL, XC, CD, CM).
• Обработка всех валидных комбинаций.

Подход жадного алгоритма (Greedy Algorithm)

Оба преобразования используют стратегию жадного алгоритма:

Целое в римское (Жадный подход)

1. Создайте карту соответствия значений и римских символов в порядке убывания.
2. Для каждой пары:
   • Используйте максимально возможное количество этого символа.
   • Вычтите значение из остатка числа.
3. Повторяйте, пока число не станет равным нулю.

Римское в целое (Жадный подход)

1. Сканируйте строку римских цифр слева направо.
2. Для каждого символа:
   • Если он меньше следующего символа, вычтите его значение (субтрактивная нотация).
   • В противном случае прибавьте его.
3. Верните накопленную сумму.

Реализация на Python

Целое в римское

def int_to_roman(num: int) -> str:
    """
    Преобразование целого числа в римские цифры.

    Временная сложность: O(1) - фиксированное число итераций (13)
    Пространственная сложность: O(1)
    """
    # Карта в порядке убывания
    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, numeral in values:
        count = num // value
        if count:
            result.append(numeral * count)
            num -= value * count

    return ''.join(result)

Римское в целое

def roman_to_int(s: str) -> int:
    """
    Преобразование римских цифр в целое число.

    Временная сложность: O(n), где n - длина строки
    Пространственная сложность: O(1)
    """
    roman_map = {
        'I': 1, 'V': 5, 'X': 10, 'L': 50,
        'C': 100, 'D': 500, 'M': 1000
    }

    result = 0
    prev_value = 0

    # Сканирование справа налево
    for char in reversed(s):
        value = roman_map[char]

        if value < prev_value:
            result -= value
        else:
            result += value

        prev_value = value

    return result

Реализация на JavaScript

Целое в римское

function intToRoman(num) {
    const 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']
    ];

    let result = '';

    for (const [value, numeral] of values) {
        while (num >= value) {
            result += numeral;
            num -= value;
        }
    }

    return result;
}

Анализ сложности

Временная сложность

Целое в римское:

• O(1) — Константное время. Алгоритм всегда проходит через 13 пар значений.

Римское в целое:

• O(n) — Линейное время. Каждый символ строки проверяется один раз.

Почему жадный алгоритм работает?

Жадный алгоритм работает для римских цифр, потому что:

1. Оптимальная подструктура: Оптимальное решение содержит оптимальные решения подзадач.
2. Отсутствие перекрывающихся подзадач: Каждое значение используется независимо.
3. Использование максимально возможного значения первым гарантирует кратчайшую запись.

Заключение

Алгоритмы перевода римских цифр демонстрируют мощь жадного подхода. Представленные реализации эффективны, легко читаемы и надежны для стандартного диапазона 1–3999.

Если вам нужен удобный интерфейс без написания кода, попробуйте наш онлайн-конвертер римских цифр с мгновенными результатами.

---

Хотите узнать больше? Изучите наше полное руководство по чтению римских цифр или посмотрите, как использовать римские цифры в Excel.