Задачка с собеседования: как перевести число в римскую систему счисления и обратно
easy

Задачка с собеседования: как перевести число в римскую систему счисления и обратно

Простая задача с приятным решением

Это одна из простых задач, которые задают на технических интервью в ИТ-компаниях. Решается легко, имеет приятное практическое применение. Изучайте на здоровье 🙂

Немного теории

В качестве подводки к этой статье на прошлой неделе мы выпустили статью про римскую систему счисления. Вот основные правила перевода:

  • В ней вместо цифр используются римские буквы: I — 1, V — 5, X — 10, L — 50, C — 100, D — 500, M — 1000.
  • В античности правила перешли от сложения к вычитанию и появились шесть новых комбинаций: IV = 4, IX = 9, XL = 40, XC = 90, CD = 400, CM = 900.
  • Цифры могут повторяться, но не более трёх одинаковых подряд.
  • Если меньшая цифра стоит справа от такой же или большей, то они складываются друг с другом: VIII → 8.
  • если меньшая цифра стоит слева от большей — вычитаем из большего меньшее: IV → 4.

Перевод из десятичной в римскую

Для перевода в римскую систему счисления сначала сделаем попарный список из десятичных чисел и их аналогов в римской системе:

all_roman = [(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')]

Идея будет в том, чтобы сразу составить список по убыванию — от самого большого числа к самому маленькому. А теперь самое важное: благодаря тому, что мы добавили туда новые комбинации, это даёт нам возможность составлять из них любые числа.

Дело в том, что сейчас в римской системе нельзя использовать больше трёх одинаковых знаков подряд. Число 8 — это VIII, а 9 — это уже не VIIII, а IX. Чтобы нам не проверять каждый раз, что стоит слева, а что справа, мы добавили эти шесть комбинаций. 

Теперь нам осталось сделать простой алгоритм, который будет работать так:

  • Берёт наше число и смотрит, какое максимальное число из нашего списка можно оттуда вычесть.
  • Для этого он проходит список слева направо (поэтому мы сразу отсортировали его по убыванию) и как только находит первое подходящее число — вычитает его из нашего.
  • Сразу после этого он добавляет к результату букву (одну или две), которая соответствовала вычтенному числу.
  • Так раз за разом алгоритм будет уменьшать наше исходное число и добавлять буквы к римскому. 
  • Когда от нашего числа ничего не останется (станет равно нулю), алгоритм остановится, а буквы, которые мы добавляли, и дадут нам римское число.

Запишем это на Python:

# формируем словарь из всех римских чисел и новых комбинаций
all_roman = [(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')]

# функция перевода чисел в римскую систему счисления
def to_roman(num):
    # на старте в римском числе ничего нет
    roman = ''
    # пока наше число больше нуля
    while num > 0:
        # перебираем все пары из словаря
        for i, r in all_roman:
            # пока наше число больше или равно числу из словаря
            while num >= i:
                # добавляем соответствующую букву в римское число
                roman += r
                # вычитаем словарное число из нашего числа
                num -= i
    # как все циклы закончились — возвращаем римское число
    return roman

print("Число 2022 в римской системе = " + to_roman(2022))

Перевод из римской системы в десятичную

Когда мы знаем, как переводить из десятичной системы в римскую, то для обратного перевода надо делать то же самое, только уменьшать уже римское число. Единственная сложность — убрать из начала строки один или два символа, которые есть в нашем словаре (помним, что римское число — это строка из букв). Для этого используем двоеточие: в Python оно делит строку на части. В нашем случае мы делаем так:

  1. Получаем длину строки из словаря — смотрим, в ней один символ или два. Например, в паре (1000, 'M') в строке один символ, а в паре (900, 'CM') — два символа.
  2. Зная это, получим все символы начиная с первого или со второго символа. А так как в Python нумерация строк начинается с нуля, то мы как раз отрежем один или два символа. То, что нам нужно.

Также нам понадобится метод srt.startswith() — он возвращает true, если в начале какой-то строки присутствует искомая строка. У него много интересных параметров (например, можно искать не с начала строки, не до конца строки или даже с конца строки). Но нам сейчас понадобится просто .startswith() — если в начале нашего римского числа будет число из словаря, то это нужное нам число. 

Всё остальное мы делаем точно так же — убираем из римского числа буквы и добавляем их десятичные значения к будущему результату:

# функция перевода римского числа в десятичную систему счисления
def to_dec(rom):
    # на старте десятичное число равно нулю
    dec = 0
    # перебираем все пары из словаря
    for i, r in all_roman:
        # пока римское число начинается буквы из словаря
        while rom.startswith(r):
            # увеличиваем десятичное число на соответствующее значение из словаря
            dec += i
            # убираем найденную букву из римского числа
            rom = rom[len(r):]
    # как все циклы закончились — возвращаем десятичное число
    return dec

print("Число MMXXII в римской системе = " + str(to_dec("MMXXII")))

Что дальше

Впереди у нас много разборов разных задач с собеседований. Они и помогут вам попрактиковаться в коде, и покажут, на что смотрят рекрутеры, и расширят ваш кругозор. 

Текст:

Михаил Полянин

Редактор:

Максим Ильяхов

Художник:

Алексей Сухов

Корректор:

Ирина Михеева

Вёрстка:

Кирилл Климентьев

Соцсети:

Виталий Вебер

Любишь Python? Зарабатывай на нём!
Изучите самый модный язык программирования и станьте крутым бэкенд-разработчиком. Старт — бесплатно.
Попробовать бесплатно
Любишь Python? Зарабатывай на нём! Любишь Python? Зарабатывай на нём! Любишь Python? Зарабатывай на нём! Любишь Python? Зарабатывай на нём!
Получите ИТ-профессию
В «Яндекс Практикуме» можно стать разработчиком, тестировщиком, аналитиком и менеджером цифровых продуктов. Первая часть обучения всегда бесплатная, чтобы попробовать и найти то, что вам по душе. Дальше — программы трудоустройства.
Начать карьеру в ИТ
Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию
easy