17.09.2023 18:31
ZetZet 44 7200 Источник

Откройте почти любую реализацию перевода чисел из арабской системы в римскую и вы почти со 100% вероятностью увидите там знаменитые дифтонги "CM" (900), "CD" (400) и так далее. И поначалу кажется, что без них не обойтись. Но это не так!

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

Немного правил и объяснений

Если в какой-то момент осознать, что уникальных чисел в римской нумерации всего 3, то все становится немного проще:

  1. "I"

  2. "V"

  3. "X"

Все остальное получается их комбинацией и домножением на 10^n по правилу off by one. Например, "CM" это всего лишь "IX" \cdot 10^2, то есть умножение происходит на ту степень, в какой позиции мы ожидаем это число увидеть в арабской записи. Причем, поскольку запись "IX" равнозначна "10 - 1", то при умножении эти скобки можно раскрыть: "I" \cdot 10^2 = "C", "X" \cdot 10^2 = "M" и составить в той же последовательности.

Это крайне простой трюк, но в этом и сложность – увидеть эту закономерность и понять, как её реализовать.

Взглянем на код

Сначала определим наши константы чисел в обеих нумерациях

const integers = [1000, 500, 100, 50, 10, 5, 1]
const literals = 'mdclxvi'

const arabicToRomanMap = new Map(integers.map((int, index) => [int, literals[index]]))

А затем реализуем конвертер

function toRoman(value: number): string {
	if (!Number.isInteger(value)) throw new Error(`Expected integer, got ${value}`)
	if (value <= 0 || value >= 5000)
		throw new Error(`Expect value between 0 and 5000 exclusive, got ${value}`)

	if (arabicToRomanMap.has(value)) return arabicToRomanMap.get(value)!

	return value
		.toString()
		.split('')
		.map(Number)
		.map(processArabicDigit)
		.map((digit, index, array) => processRomanDigit(digit, array.length - index))
		.join('')
}

Разберемся блочно, что вообще тут происходит.

value
  .toString()
  .split('')
  .map(Number)

Этот код просто превращает число в массив цифр: 4956 становится [4, 9, 5, 6]. А дальше начинается магия:)

Посмотрим на реализацию функции processArabicDigit :

const processArabicDigit = (digit: number) => {
	if (digit === 0) return ''
	if (arabicToRomanMap.has(digit)) return arabicToRomanMap.get(digit)!

	const foundLessByOne = integers.find(integer => integer - digit === 1)
	if (foundLessByOne !== undefined) return `i${arabicToRomanMap.get(foundLessByOne)}`

	return integers.reduce((accumulator, integer) => {
		while (digit >= integer) {
			accumulator += arabicToRomanMap.get(integer)
			digit -= integer
		}

		return accumulator
	}, '')
}

Основная цель этой функции, превратить любую арабскую цифру в последовательность базовых цифр римской нумерации: "I", "V", "X".

  • 0 даст пустую строку

  • 1 и 5 базовые

  • 4 и 9 подчиняются правилу off by one. Они равны в точности "I{цифра + 1}"

  • 2, 3, 6, 7, 8 пройдут по жадному алгоритму и превратятся в "II", "III", "VI", "VII", "VIII" соответственно.

То есть, изначальное число 4956 превратится в ["IV", "IX", "V", "VI"]. Осталось провести операцию потенциирования, которой занимается функция processRomanDigit:

const processRomanDigit = (digit: string, position: number) => {
	if (position === 4) return 'm'.repeat(toArabic(digit))

	return digit
		.split('')
		.map(char => romanToArabicMap.get(char)!)
		.map(digitNumber => arabicToRomanMap.get(digitNumber * 10 ** (position - 1))!)
		.join('')
}

Заметим, что position = 4 является граничным случаем. То есть конструирование количество тысяч выпадает из правила, но это не страшно.

Остальные же числа разбиваются на свои базовые и домножаются на 10 в нужной позиции:

  • "I" с позицией 4 станет "MMMM"

  • "IX" с позицией 2 станет "CM" (рассматривалось в примере объяснений)

  • "V" с позицией 1 станет "L"

  • "VI" с позицией 0 останется неизменным

Последний шаг – собрать все вместе. Итого, 4956 превратится "MMMMCMLVI"

Зачем такой подход вообще нужен?

На то есть несколько причин, и одна из них, это просто весело. Не принимать на веру какие-то правила и докапываться до истины вещей, как можно обобщить правило или его вывести.

Вдобавок, варианты реализаций через запоминание дифтонгов плохо масштабируются, если кому-либо когда-либо захочется расширить домен римских чисел сверх 5000. А здесь, это просто придумать буквы, взять следующие значения (5000, 10000) и все. И так до бесконечности.

Даже то захардкоженное значение position = 4 можно обобщить. И с обратной конверсией проблем тоже не возникнет, нужно только придумать, как обобщить регулярку проверки валидного римского числа. Но это уже совсем другая история:)

Весь код, включая обратную конверсию, можно найти в репозитории.

Комментарии (44)


  1. Veratam
    17.09.2023 19:24
    #25973730
    +1

    А где же у вас валидация правильности записи числа?


    1. ZetZet Автор
      17.09.2023 19:24
      #25973760

      Если речь про результат работы toRoman, то его можно проверить несколькими способами:

      1. Прогнать через любой другой обратный конвертер (можно даже через тот, что имплементирован в том же репозитории)

      2. Преобразовать число обратно руками, правила не столь сложные

      3. В том же репозитории есть регулярка проверки римского числа на валидность


  1. yeswell
    17.09.2023 19:24
    #25973956

    Не могу не поделиться своей уже достаточно давней реализацией

    Тоже очень хотел сделать простое добавление «новых цифр» и понятную сложность


    1. ZetZet Автор
      17.09.2023 19:24
      #25974274
      +1

      Выглядит неплохо, кста!

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


      1. yeswell
        17.09.2023 19:24
        #25976874

        Вообще вся идея этой реализации — это проход по римским цифрам, а не по десятичному числу. Потому что порядок цифр в римском числе фиксирован (кроме случая с 4 и 9)

        Но удобнее итерироваться не по каждой цифре, а по парам цифр. Отсюда и такой цикл


  1. Radisto
    17.09.2023 19:24
    #25974118
    +7

    Если в какой-то момент осознать, что уникальных чисел в римской нумерации всего 3, то все становится немного проще:

    "I"

    "V"

    "X"

    А если осознать, что их больше

    L 50

    C 100

    D 500

    M 1000

    то все снова станет немного сложнее)))


    1. ZetZet Автор
      17.09.2023 19:24
      #25974250

      Да, тут немного не та формулировка. В моей голове она звучала лучше, теперь я это вижу.

      Более правильно было бы написать:

      Любая арабская цифра представима в виде комбинации следующих римских цифр

      Хотя и эта формулировка не кажется 100% точной


  1. kay_kay
    17.09.2023 19:24
    #25974124
    +3

    Переведите для идиотов фразу "Например, "CM" это всего лишь "IX" \cdot 10^2, то есть умножение происходит на ту степень, в какой позиции мы ожидаем это число увидеть в арабской записи "

    На этой фразе ведь весь смысл статьи держится, не так ли?


    1. ZetZet Автор
      17.09.2023 19:24
      #25974254

      Да, и чуть ниже об этом уже написали.

      “CM” это 900, то есть 9 \cdot 10^2, то есть “IX” \cdot 10^2


  1. Zara6502
    17.09.2023 19:24
    #25974138
    +4

    Например, "CM" это всего лишь "IX" \cdot 10^2, то есть умножение происходит на ту степень, в какой позиции мы ожидаем это число увидеть в арабской записи

    то есть 900 это 9*10^2, это здорово, но мы это знаем, что это даёт в контексте статьи?

    Откройте почти любую реализацию перевода чисел из арабской системы в римскую и вы почти со 100% вероятностью увидите там знаменитые дифтонги "CM" (900), "CD" (400) и так далее. И поначалу кажется, что без них не обойтись. Но это не так!

    и в финале статьи вы пишете "Итого, 4956 превратится "MMMMCMLVI" ", что ставит в тупик, я ожидал какое-то решение где CM и CD не будет.


    1. AWRDev
      17.09.2023 19:24
      #25974216
      +1

      CM и CD если я правильно понимаю нельзя выкинуть просто так, если и можно записать как-то по другому числа, это будет неправильная запись.
      Тут суть я так понимаю в том, что в "стандартном подходе" алгоритм выглядит как-то так:
      Число разбивается по цифрам и в зависимости от разрядности добавляются нужные буквы, а тут процесс "парсинга" по другому идет


      1. ZetZet Автор
        17.09.2023 19:24
        #25974262

        Именно! :)


      1. Zara6502
        17.09.2023 19:24
        #25974542

        почитал подробнее и по факту уже давно нет понятия - неправильная запись, если конечно нет цели записывать что-то строго по классическим правилам, но тогда и XXXX и IIII можно писать. Так что я пока всё равно не понял в чем смысл статьи.


    1. ZetZet Автор
      17.09.2023 19:24
      #25974260

      Мы не захардкодили значение этого “CM”, а нашли его, вывели правило, по которому строятся числа в римской нумерации с этим правилом off by one.

      Римская нумерация работает так, что нужны эти сочетания. Просто они не обязательны в решении


      1. Zara6502
        17.09.2023 19:24
        #25974552

        я читаю правила написания в вики и не понимаю о чем конкретно ваша статья и почему обозначена какая-то проблема? какая кстати?


        1. ZetZet Автор
          17.09.2023 19:24
          #25974596

          Проблема заключается в том, что нельзя просто так полагаться на сочетания букв и использовать не атомарные значения, чем грешат прочие реализации с их “CM” (900), “IV” (4) etc. Зачем они нужные, если они выводятся из базовых значений “C”, “M”, “I”, “V”?


          1. Zara6502
            17.09.2023 19:24
            #25975216
            +5

            ладно, сойдемся на том, что я не понимаю проблематику, а вы не можете объяснить.


  1. Germanjon
    17.09.2023 19:24
    #25974228
    -2

    На Leetcod-e задача "Roman to integer" идёт в первой двадцатке и помечена как лёгкая. На том же Leetcod-е на текущий момент приведено 17.4К вариантов решений на разных языках программирования.

    Вопрос: для чего писать отдельную статью?


    1. ZetZet Автор
      17.09.2023 19:24
      #25974248
      +3

      Начнем с того, что это не Roman to integer, а Integer to roman, а эта проблема на Leetcode имеет уже отметку медиум.

      Вдобавок, в тех решениях все так же присутствуют дифтонги. Прелесть этого решения в том, что тут не надо иметь пары букв, только атомарные значения


      1. Rsa97
        17.09.2023 19:24
        #25974846
        +1

        А недостаток в том, что нужен более сложный алгоритм формирования, а не простейшее взятие значения из массива

        ['', 'I', 'II', 'III', 'IV', 'V', 'VI' ,'VII', 'VIII', 'IX'][digit]
        .


        1. ZetZet Автор
          17.09.2023 19:24
          #25975056
          +1

          Кстати, отличное замечание!

          Но это требует хранить еще и массив всех возможных цифр


          1. Rsa97
            17.09.2023 19:24
            #25975164
            +1

            Да, но тут уже надо смотреть конкретный язык/код. Может оказаться, что массив занимает меньше памяти, чем сложный код. А может и наоборот.


  1. sophist
    17.09.2023 19:24
    #25975442
    +1

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

    Вот тут не понял. Почему они плохо масштабируются, если всё, что для этого надо сделать, – добавить числа из расширения (вместе с новыми дифтонгами) в рабочий массив?


  1. ibes
    17.09.2023 19:24
    #25975452
    +13

    Пожалуйста, не называйте дифтонгами то, что ими не является. Дифтонги - это вообще не про буквы.


    1. slonopotamus
      17.09.2023 19:24
      #25977152
      +1

      Вот я в результате вообще не смог понять что нам пытается сообщить автор, где тут дифтонги, и в каком месте без СМ=900 можно обойтись, если у него же самого СМ=900.


  1. Rsa97
    17.09.2023 19:24
    #25975548
    +1

    А здесь, это просто придумать буквы, взять следующие значения (5000, 10000) и все.
    А всё уже придумано. На каждые следующие три десятичных разряда просто добавляется одна черта сверху.
    image — 17504315
    Но при этом 1000, 2000 и 3000 обозначаются как M, MM и МММ, а не I̅, I̅I̅ и I̅I̅I̅.


    1. iig
      17.09.2023 19:24
      #25975644

      На каждые следующие три десятичных разряда

      В римской системе есть десятичные разряды?


      1. Zenitchik
        17.09.2023 19:24
        #25975730
        +1

        Конечно, есть. Вы же X от I как-то отличаете?


        1. iig
          17.09.2023 19:24
          #25975762

          Римские цифры соответствуют некоторым числам. Эти числа в арабской записи могут занимать некоторое количество десятичных разрядов. А так римская система на степени 10 не сильно завязана.
          </зануда> ;)


          1. Zenitchik
            17.09.2023 19:24
            #25975800

            Вы отчасти правы. Должно было быть написано "десятичный порядок", а не "десятичный разряд".

            Тем не менее римская система на десятичные порядки завязана так же сильно, как и арабская. Но обозначает их не позициями, а уникальными парами цифр.


      1. Rsa97
        17.09.2023 19:24
        #25975758

        Разряды есть, просто нет явного обозначения нуля каким-либо символом.


        1. iig
          17.09.2023 19:24
          #25975804

          Значит это не совсем те разряды ;)
          Хотя да, если кодировать 0 пробелом, а каждую 10-ную цифру — римскими I..IX, а для перехода в следующий 10-ный разряд просто сдвигать римские цифры на 3, то конвертор начинает выглядеть скучно.


    1. randomsimplenumber
      17.09.2023 19:24
      #25977030

      А всё уже придумано

      А это правда нативная римская запись, с черточками? Римлянам действительно не хватало букв? или новодел?


      1. Rsa97
        17.09.2023 19:24
        #25977560

        Римляне изначально (где-то за 700-800 лет до нашей эры) использовали другие символы:
        ↆ — 50, Ↄ — 100, D или IↃ — 500, ↀ или CIↃ — 1000, ↁ или IↃↃ — 5000, ↂ или CCIↃↃ — 10000, ↇ или IↃↃↃ — 50000, ↈ или CCCIↃↃↃ — 100000.
        Вариант с чертой появился примерно в начале нашей эры, но и в XVI веке обе системы ещё использовались одновременно.
        Кроме того, принцип вычитания для 4 и 9 использовался не всегда и встречаются записи вида XLIIII (44). Окончательно он утвердился только в XIX веке.
        85674 — IↃↃↃCCIↃↃCCIↃↃCCIↃↃIↃↃIↃCↆXXIIII или ↇↂↂↂↁDCLXXIIII или L̅X̅X̅X̅V̅DCLXXIV.


        1. Zenitchik
          17.09.2023 19:24
          #25977580

          Вы забыли упомянуть, что у некоторых авторов могли надчёркиваться вообще все числа, и черта там просто выделяла число на фоне текста.


          1. Rsa97
            17.09.2023 19:24
            #25977800

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


            1. iig
              17.09.2023 19:24
              #25979036

              для математических целей

              Кстати, а что с математическими операциями у римлян? Что они с этими числами потом делали? Если бы не IV/IX — сложение выглядело бы достаточно просто: сосчитал символы в слагаемых, выписал рядом. Если одинаковых символов >4 — перенос в следующую группу. А так, сложение-вычитание в столбик достаточно сложное, умножение/деление — почти решение дифуров ;)


              1. Rsa97
                17.09.2023 19:24
                #25979190

                А римляне математику не любили, возможно именно из-за такой неудобной записи чисел. Например, знаков операций у них не было, операции просто писались текстом.
                Вместо записи IV зачастую использовали IIII, вместо IX — VIIII, так что способ с количеством вполне подходит.
                126 * 37 = CXXVI * XXXVII
                Умножаем на каждую цифру:
                CXXVI * X = MCCLX
                CXXVI * X = MCCLX
                CXXVI * X = MCCLX
                CXXVI * V = DLLXXVV = DLLXXX = DCXXX
                CXXVI * I = CXXVI
                CXXVI * I = CXXVI
                Складываем и объединяем:
                MMMDCCCCCCCCCLLLXXXXXXXXXXVVII =(VV => X) MMMDCCCCCCCCCLLLXXXXXXXXXXXII =(XXXXX => L) MMMDCCCCCCCCCLLLLLXII =(LL => C) MMMDCCCCCCCCCCCLXII =(CCCCC => D) MMMDDDCLXII =(DD => M) MMMMDCLXII = 4662


              1. Zenitchik
                17.09.2023 19:24
                #25979552

                Что они с этими числами потом делали?

                Считали на абаке. Запись использовалась только для хранения.


                1. iig
                  17.09.2023 19:24
                  #25981720

                  Считали на абаке.

                  Действительно, для перекладывания шариков из верхней ячейки в нижнюю эта система отлично подходит ;) И шариков нужно меньше чем для десятичных счет.


                  1. Rsa97
                    17.09.2023 19:24
                    #25982198

                    На абаке шарики из ячейки в ячейку не перекладываются, только передвигаются вверх-вниз в пределах ячейки.

                    Абак на десять миллионов
                    image
                    Нижняя часть — единицы разряда, верхняя — пятёрки. Справа разряд для унций (двенадцатых долей, пять камешков снизу вместо четырёх), самая правая колонка: S — 1/24, Ↄ — 1/48 и ƻ — 1/144.


  1. drauger
    17.09.2023 19:24
    #25976748

    А вы уверены, что 4956 - это MMMMCMLVI, а не MMMMLMVI?


    1. Rsa97
      17.09.2023 19:24
      #25976860
      +1

      4956 — это I̅V̅CMLVI


  1. ijustwanttobeacool
    17.09.2023 19:24
    #25980488

    Когда-то давно на codewars такое решение придумал

    Значения захардкожены, конечно, но сам алгоритм простой получается

    function intToRoman(num: number): string {
  const roman = ['I', 'IV', 'V', 'IX', 'X', 'XL', 'L', 'XC', 'C', 'CD', 'D', 'CM', 'M'];
  const numbers = [1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000];
  let result = '';
  let i = numbers.length;
  while(num) {
    if (num >= numbers[i]) {
        result += roman[i];
        num -= numbers[i];
    } else {    
        i--;
    }
  }
  return result;
};