ZetZet 17 сен 2023 в 21:31

Римские числа или как не запоминать составные варианты

3 мин

12K

Алгоритмы*Математика*TypeScript*

+15

Комментарии 45

Veratam 17 сен 2023 в 22:24

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

ZetZet 17 сен 2023 в 22:40

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

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

yeswell 18 сен 2023 в 00:30

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

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

ZetZet 18 сен 2023 в 07:23

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

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

yeswell 18 сен 2023 в 18:59

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

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

Radisto 18 сен 2023 в 03:37

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

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

L 50

C 100

D 500

M 1000

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

ZetZet 18 сен 2023 в 07:14

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

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

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

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

kay_kay 18 сен 2023 в 04:03

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

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

ZetZet 18 сен 2023 в 07:16

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

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

Zara6502 18 сен 2023 в 04:49

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

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

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

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

AWRDev 18 сен 2023 в 06:47

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

ZetZet 18 сен 2023 в 07:20

Именно! :)

Zara6502 18 сен 2023 в 08:13

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

ZetZet 18 сен 2023 в 07:19

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

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

Zara6502 18 сен 2023 в 08:14

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

ZetZet 18 сен 2023 в 08:28

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

Zara6502 18 сен 2023 в 11:06

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

Germanjon 18 сен 2023 в 06:58

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

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

ZetZet 18 сен 2023 в 07:12

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

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

Rsa97 18 сен 2023 в 09:36

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

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

ZetZet 18 сен 2023 в 10:29

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

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

Rsa97 18 сен 2023 в 10:55

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

sophist 18 сен 2023 в 12:08

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

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

ibes 18 сен 2023 в 12:12

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

slonopotamus 18 сен 2023 в 21:08

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

Rsa97 18 сен 2023 в 12:36

А здесь, это просто придумать буквы, взять следующие значения (5000, 10000) и все.

А всё уже придумано. На каждые следующие три десятичных разряда просто добавляется одна черта сверху.

— 17504315
Но при этом 1000, 2000 и 3000 обозначаются как M, MM и МММ, а не I̅, I̅I̅ и I̅I̅I̅.

iig 18 сен 2023 в 13:05

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

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

Zenitchik 18 сен 2023 в 13:32

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

iig 18 сен 2023 в 13:41

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

Zenitchik 18 сен 2023 в 13:48

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

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

Rsa97 18 сен 2023 в 13:40

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

iig 18 сен 2023 в 13:50

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

randomsimplenumber 18 сен 2023 в 20:15

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

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

Rsa97 19 сен 2023 в 01:42

Римляне изначально (где-то за 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.

Zenitchik 19 сен 2023 в 02:24

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

Rsa97 19 сен 2023 в 07:34

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

iig 19 сен 2023 в 13:29

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

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

Rsa97 19 сен 2023 в 14:05

А римляне математику не любили, возможно именно из-за такой неудобной записи чисел. Например, знаков операций у них не было, операции просто писались текстом.
Вместо записи 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

Zenitchik 19 сен 2023 в 15:56

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

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

iig 20 сен 2023 в 09:46

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

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

Rsa97 20 сен 2023 в 11:53

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

Абак на десять миллионов

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

drauger 18 сен 2023 в 18:14

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

Rsa97 18 сен 2023 в 18:53

4956 — это I̅V̅CMLVI

ijustwanttobeacool 19 сен 2023 в 20:46

Когда-то давно на 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;
};

fimaszobak 2 окт 2023 в 08:36

Уважаемый автор, к сожалению, название статьи выбрано не вполне корректно.

Речь в статье идёт о согласных, а дифтонги по определению - это "сочетание не разделённых согласными двух гласных звуков в одном слоге."

Примеры можно найти в том же латинском языке, а также в немецком и других.

Зарегистрируйтесь на Хабре, чтобы оставить комментарий

Римские числа или как не запоминать составные варианты

Комментарии 45

Публикации

Истории