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

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

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

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

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

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

  • В ней вместо цифр используются римские буквы: 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")))

Что дальше

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

Код и описание проекта:

LeAnne Chan

Текст:

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

Редактор:

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

Художник:

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

Корректор:

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

Вёрстка:

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

Соцсети:

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

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

Неочевидная ошибка в типах данных Python.

easy
Запускаем нейросеть на домашнем компьютере
Запускаем нейросеть на домашнем компьютере

Пошаговое руководство для начинающих

hard
Создаём статичный сайт на Hugo
Создаём статичный сайт на Hugo

Превращаем простой текст в полноценный сайт.

medium
Как добавить на страницу блок, который можно закрыть (например, баннер)
Как добавить на страницу блок, который можно закрыть (например, баннер)

Рецепт самого бесящего явления в интернете

easy
Улучшаем арканоид
Улучшаем арканоид

Добавляем очки, жизни и нарастание сложности.

medium
Что означает ошибка OverflowError: math range error
Что означает ошибка OverflowError: math range error

Это ошибка переполнения из-за математических операций

easy
Устанавливаем суверенный облачный офис

Пошаговая установка OnlyOffice на ваш собственный или арендованный сервер

hard
Конец ретроградному Меркурию! Пишем собственный гороскоп на Python

Наш гороскоп точен и прост! Сбросим иго астрологов!

medium
Ускоряем работу в Экселе
Ускоряем работу в Экселе

Делаем свой макрос

easy
Делаем эффектную фотогалерею на сайте
Делаем эффектную фотогалерею на сайте

Красивый трёхмерный виджет с несложным кодом

hard
easy