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