Алгоритм записи римских цифр

Содержание

1. Правила записи римских цифр
2. Алгоритм преобразования из десятичной записи в римскую
3. Алгоритм преобразования из римской записи в десятичную

Римская система счисления – это система обозначений чисел, которая использовалась в Древнем Риме и до сих пор применяется в некоторых областях, таких как теория чисел, история и геральдика. В этой системе числа записываются с помощью комбинации символов, известных как римские цифры. В этой статье мы рассмотрим алгоритм записи римских цифр и основные правила, которые следует знать при работе с ними.

Правила записи римских цифр

В общей сложности в системе римских цифр используется 7 символов: I, V, X, L, C, D и M. Каждый символ представляет определенное количество единиц, и комбинируя их, можно записывать числа от 1 до 3999.

Вот основные правила алгоритма записи римских цифр:

1. Символы записываются от наибольшего к наименьшему, чтобы указать, что их значения должны быть сложены. Например, число 27 записывается как XXVII, а не VXXII.
2. Когда символ с меньшим значением стоит перед символом с большим значением, это указывает на вычитание. Например, число 4 записывается как IV, а не IIII.
3. Символы I, X и C могут повторяться не более трех раз подряд, чтобы избежать неоднозначности. Например, число 14 записывается как XIV, а не XIIII.
4. Символы V, L и D никогда не повторяются.
5. Символы I, X и C могут использоваться в сочетании с символами, которые имеют более высокое значение, чтобы увеличить значение. Например, число 8 записывается как VIII, а не IIX.
6. Символы, которые имеют более высокое значение, всегда стоят перед символами, которые имеют более низкое значение.
7. Числа, которые больше 3999, не могут быть записаны в системе римских цифр.

Ниже представлена таблица соответствия символов римских системы счисления и привычной нам десятичной:

Обратите внимание, что в римской системе счисления не было отдельной цифры для нуля. Римляне не использовали нуль в своих математических вычислениях, поэтому его не было необходимости включать в систему римских чисел.

Тем не менее в некоторых контекстах, например, при записи дат, вместо нуля могла использоваться латинская буква «N» (от слова «nulla», что означает «ни один»). Однако в настоящее время буква «N» не считается стандартной частью системы римских чисел.

Алгоритм преобразования из десятичной записи в римскую

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

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

Теперь напишем метод toRomanNumeral(), который принимает на вход целое число и возвращает строку с римским числом.

Результат складываем в StringBuilder для оптимизации работы с памятью. Далее в цикле проходимся по всем символам римских цифр из нашего глобального массива, начиная с наибольшего. Для каждого такого символа во вложенном цикле while пытаемся вычитать соответствующее ему десятичное число из исходного числа до тех пор, пока это возможно. И каждый раз добавляем вычтенный символ в результирующую строку.

Алгоритм преобразования из римской записи в десятичную

Теперь решим обратную задачу. Напишем метод fromRomanNumeral(), принимающий на вход строку с римским числом и возвращающий целое число.

Здесь мы используем цикл, который проходит по массиву ROMAN_NUMERALS и проверяет, начинается ли входная строка с данной римской цифры. Если это так, то соответствующее десятичное значение добавляется к результату, а римское число обрезается до тех пор, пока оно не будет полностью обработано.