Статьи
Утилиты Telegram YouTube Отзывы

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

17 апреля 2023

Тэги: Java, алгоритмы, головоломки.

Содержание

  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, не могут быть записаны в системе римских цифр.

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

СимволЗначение
I1
V5
X10
L50
C100
D500
M1000

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

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

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

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

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

private final static String[] ROMAN_NUMERALS = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
private final static int[] DECIMAL_VALUES = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};

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

public static String toRomanNumeral(int number) {
    var result = new StringBuilder();
    int remaining = number;
    for (int i = 0; i < ROMAN_NUMERALS.length; i++) {
        int decimalValue = DECIMAL_VALUES[i];
        String romanNumeral = ROMAN_NUMERALS[i];
        while (remaining >= decimalValue) {
            result.append(romanNumeral);
            remaining -= decimalValue;
        }
    }
    return result.toString();
}

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

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

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

public static int fromRomanNumeral(String romanNumeral) {
    int result = 0;
    var input = romanNumeral.toUpperCase();
    for (int i = 0; i < ROMAN_NUMERALS.length; i++) {
        var romanNumeralToCheck = ROMAN_NUMERALS[i];
        int decimalValue = DECIMAL_VALUES[i];
        while (input.startsWith(romanNumeralToCheck)) {
            result += decimalValue;
            input = input.substring(romanNumeralToCheck.length());
        }
    }
    return result;
}

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


Облако тэгов

Kotlin, Java, Spring, Spring Boot, Spring Data, SQL, PostgreSQL, Oracle, Linux, Hibernate, Collections, Stream API, многопоточность, файлы, Nginx, Apache, maven, gradle, JUnit, YouTube, новости, руководство, ООП, алгоритмы, головоломки, rest, GraphQL, Excel, XML, json, yaml.

Последние статьи


Комментарии

Добавить комментарий

×

devmark.ru