Глава 31. Римская числовая нотация

Идеи реализации
	Глава 31. Римская числовая нотация

Идеи реализации

Перевод в римскую нотацию

Римская нотация использует семь цифр — I, V, X, L, L, D, M. Для представления числа $n$ в римской нотации возьмём количества его единиц $n_{0}$ , десятков $n_{1}$ , сотен $n_{2}$ и тысяч $n_{3}$ . Сначала запишем в римской нотации количество единиц. При $0 ⩽ n_{0} ⩽ 3$ просто запишем подряд цифру I (единица) $n_{0}$ раз. При $4 ⩽ n_{0} ⩽ 8$ запишем цифру V (она обозначает пять), и припишем к ней столько цифр I, на сколько $n_{0}$ больше или меньше пяти, причём если больше, то справа, а если меньше, то слева. Наконец, $n_{0} = 9$ запишем как IX (X обозначает десятку, I слева показывает, что до десятки недостаёт единицы).

Точно так же поступим с количеством десятков $n_{1}$ , только вместо цифр I=1, V=5, C=10 будем использовать X=10, L=50, C=100.

Те же правила применяются к количеству сотен $n_{2}$ , для записи используются цифры C=100, D=500, M=1000.

Для тысяч римских цифр хватит только при $0 ⩽ n_{3} ⩽ 3$ , так что получится либо M, либо MM, либо MMM.

Все перечисленные правила суммированы в таблице 31.1. «Запись десятичных разрядов римскими цифрами».

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

	единицы ( $n_{0}$ )	десятки ( $n_{1}$ )	сотни ( $n_{2}$ )	тысячи ( $n_{3}$ )
$0$
$1$	`I`	`X`	`C`	`M`
$2$	`II`	`XX`	`CC`	`MM`
$3$	`III`	`XXX`	`CCC`	`MMM`
$4$	`IV`	`XL`	`CD`
$5$	`V`	`L`	`D`
$6$	`VI`	`LX`	`DC`
$7$	`VII`	`LXX`	`DCC`
$8$	`VIII`	`LXXX`	`DCCC`
$9$	`IX`	`XC`	`CM`

Теперь составим вместе записи для $n_{3}$ , $n_{2}$ , $n_{1}$ , $n_{0}$ в порядке перечисления. Римская запись числа готова.

Например, число $1987$ записывается как MCMLXXXVII. Здесь $1000 =$ M, $900 =$ CM, $80 =$ LXXX и $7 =$ VII.

Виден недостаток римской нотации: используя шесть цифр, она позволяет представить числа не более $3999$ .

Анализ правил перевода чисел в римскую нотацию показывает, что достаточно записать римскими цифрами каждую из десятичных цифр заданного числа, учитывая номер её разряда, а затем составить вместе полученные записи. Правила записи десятичной цифры с помощью римских цифр примерно одни и те же — меняется в зависимости от разряда только лишь набор римских цифр, используемых для записи. Для единиц это I, V, X, для десятков — X, L, C, для сотен — C, D, M, для тысяч — только M (поскольку цифр для пяти и десяти тысяч не предусмотрено).

С учётом этого обстоятельства было бы разумно реализовать в виде процедуры (назовём её toRomanHelper) преобразование десятичной цифры в римскую нотацию. Процедура будет принимать два параметра — десятичную цифру и номер десятичного разряда. Возвращаемое значение — римская запись десятичной цифры, соответствующая её разряду.

Преобразованием числа в римскую запись будет заниматься процедура toRoman. Она разберёт число по десятичным цифрам. Для каждой десятичной цифры найдёт запись римскими цифрами в соответствии с разрядом, в котором она находится (для этого будет вызвана процедура toRomanHelper). Римские записи для десятичных цифр будут соединены вместе и получившаяся строка будет возвращена из процедуры.

Перевод из римской нотации

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

Задача разделения по разрядам теперь будет сложнее. Дело в том, что не каждая строка, составленная из римских цифр, будет правильной римской записью некоторого числа (в отличие от десятичной записи, в которой правильной будет любая последовательность десятичных цифр).

В соответствии с правилами формирования римской записи чисел правильная запись представляет собой четыре группы римских цифр, составленных вместе. Первая (расположенная слева) — группа, обозначающая тысячи, затем идёт группа сотен, затем десятков, и, наконец, единиц. То, из чего может состоять каждая из этих групп, можно увидеть в соответствующем столбце таблицы 31.1. «Запись десятичных разрядов римскими цифрами».

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

Приступим к созданию шаблона для разряда единиц. Решение, которое первым приходит в голову — перечислить все альтернативы: (|I|II|III|IV|V|VI|VII|VIII|IX). Обратите внимание на пустую альтернативу, с которой начинается перечисление: группа единиц в римской записи может быть и пустой. Это решение можно немного упростить, если использовать квантификаторы. Для цифр от $0$ до $3$ можно написать I{0,3} вместо |I|II|III, для цифр от $5$ до $8$ годится VI{0,3} вместо V|VI|VII|VIII. Таким образом, для разряда единиц получаем шаблон (I{0,3}|IV|VI{0,3}|IX). Его можно дополнительно упростить, объединив первую альтернативу с третьей, а вторую с четвёртой: (V?I{0,3}|I[VX]).

Для десятков и сотен получаются точно такие же шаблоны, только составленные из других римских цифр: (L?X{0,3}|X[LC]) (десятки) и (D?C{0,3}|C[DM]) (сотни). Для разряда тысяч шаблон совсем простой: (M{0,3}).

Итак, для целой римской записи получаем такое регулярное выражение: ^(M{0,3})(D?C{0,3}|C[DM])(L?X{0,3}|X[LC])(V?I{0,3}|I[VX])$.


Глава 31. Римская числовая нотация		Разработка