Это одна из простых задач, которые задают на технических интервью в ИТ-компаниях. Решается легко, имеет приятное практическое применение. Изучайте на здоровье :-)
Немного теории
В качестве подводки к этой статье на прошлой неделе мы выпустили статью про римскую систему счисления. Вот основные правила перевода:
- В ней вместо цифр используются римские буквы: 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 оно делит строку на части. В нашем случае мы делаем так:
- Получаем длину строки из словаря — смотрим, в ней один символ или два. Например, в паре (1000, 'M') в строке один символ, а в паре (900, 'CM') — два символа.
- Зная это, получим все символы начиная с первого или со второго символа. А так как в 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")))Что дальше
Впереди у нас много разборов разных задач с собеседований. Они и помогут вам попрактиковаться в коде, и покажут, на что смотрят рекрутеры, и расширят ваш кругозор.
