Перевод римских цифр на арабские

Я построил предикат, который преобразует римские цифры в арабские. Единственная проблема в том, что предикат ограничен: если я хочу преобразовать более 3 арабских цифр одновременно, это больше не работает.

Вот как должен работать предикат:

?- convert([v,i,i],Arabic).
Arabic = 7.

Мое решение до сих пор:

tran([],0).
tran(i,1).
tran(v,5).
tran(x,10).

convert([],X) :- X is 0, !.
convert([T],X) :- tran(T,E), X is E,!.
convert([T|Ts],X) :- tran(T,E), tran(Ts,Es), X is E+Es,!.
convert([T,Ts,Tss],X) :- tran(T,E), tran(Ts,Es), tran(Tss,Ess), X is E+Es+Ess.

Я знаю, почему предикат не работает с более чем 3 числительными, и я мог бы также расширить предикат convert, но с тем же шаблоном, как показано выше.

Как сделать предикат convert более «общим» (чтобы он мог работать независимо от количества числительных)? Или у вас есть другие идеи, как написать предикат? Спасибо :)


math integer prolog roman-numerals converter
person jazzsuite    schedule 03.02.2014    source источник
comment
Некоторые комментарии и подсказки. Вы можете упростить convert([],X) :-... до convert([],0). и convert([T],X) :- ... до convert([T],E) :- tran(T,E). Обратите внимание, что правила для римских цифр (см. en.wikipedia.org /wiki/Roman_numerals) зависят от того, следует ли более высокое значение за более низким значением. Таким образом, ваш предикат convert должен будет просмотреть два последовательных значения, чтобы сделать выбор, например, convert([X,Y|T], Value) :- X < Y, % add in Y-X. Я бы также рекомендовал сначала преобразовать список в числа, а затем оперировать, чтобы упростить арифметику и сравнения.   -  person lurker    schedule 04.02.2014

Ответы (3)


arrow_upward
3
arrow_downward

Я не проверял это слишком много, но я пробовал это на нескольких числах, и, похоже, это работает.

Код подчиняется «правилу вычитания пар», описанному, например, в https://projecteuler.net/about=roman_numerals< /а>

В коде используется метод «аккумулятора» для передачи информации о сумме цифр, увиденных ранее. Первоначальный вызов просто устанавливает аккумулятор в 0.

digit(i, 1).
digit(v, 5).
digit(x, 10).
digit(l, 50).
digit(c, 100).
digit(d, 500).
digit(m, 1000).

convert(Roman, Arabic) :-
    convert(Roman, 0, Arabic).

convert([], Acc, Acc).

convert([A], Acc, Arabic) :-
    digit(A, AVal),
    Arabic is Acc + AVal.

convert([A, B | Rest], Acc, Arabic) :-
    digit(A, AVal), digit(B, BVal),
    AVal < BVal,
    NewAcc is Acc + BVal - AVal,
    convert(Rest, NewAcc, Arabic).

convert([A, B | Rest], Acc, Arabic) :-
    digit(A, AVal), digit(B, BVal),
    AVal >= BVal,
    NewAcc is Acc + AVal,
    convert([B | Rest], NewAcc, Arabic).

Некоторые тесты:

convert([v, i, i], Arabic).
Arabic = 7 

?- convert([x, i, x], Arabic).
Arabic = 19 

?- convert([m, d, c, v, i], Arabic).
Arabic = 1606

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

person Sergii Dymchenko    schedule 04.02.2014
comment
Это в основном подход, о котором я думал. Незначительным вариантом может быть вызов maplist(digit, Roman, Numbers) в предикате convert/2, а затем запуск convert/3 в Numbers, исключая отдельные запросы digit/2. - person lurker; 04.02.2014

arrow_upward
3
arrow_downward

Это может помочь, если вы считаете, что количество дискретных «цифр» в римской системе счисления больше, чем просто I, X и V, а именно:

roman( "M"   , 1000 ) .
roman( "CM"  ,  900 ) .
roman( "D"   ,  500 ) .
roman( "CD"  ,  400 ) .
roman( "C"   ,  100 ) .
roman( "XC"  ,   90 ) .
roman( "L"   ,   50 ) .
roman( "XL"  ,   40 ) .
roman( "X"   ,   10 ) .
roman( "IX"  ,    9 ) .
roman( "V"   ,    5 ) .
roman( "IV"  ,    4 ) .
roman( "I"   ,    1 ) .

Затем вы можете написать что-то вроде

roman_to_decimal( R , D ) :-
  roman_to_decimal( R , 0 , D )
  .

roman_to_decimal( [] , D , D ) :- .
roman_to_decimal( R  , T , D ) :-
  roman(P,V) ,
  append(P,S,R) ,
  ! ,
  T1 is T+V ,
  roman_to_decimal(S,T1,D)
  .

Вызовите его как

roman_to_decimal( "MCM" , D ) .

У этого есть некоторые недостатки, а именно:

  • Синтаксис не применяется: римская система нумерации требовала, чтобы дискретные компоненты располагались слева направо в порядке убывания значения. Это не принимает во внимание.

  • Он не учитывает множество вариаций. Должен ли 999 быть представлен как компактный IM или как более подробный CMXCIX?

person Nicholas Carey    schedule 04.02.2014
comment
Ваша вторая пуля, строго говоря, не является проблемой, поскольку, согласно описанию римских цифр, такая форма, как IM, на самом деле недействительна. Есть только несколько конкретных случаев, вызываемых вычитающей записью римских цифр. - person lurker; 04.02.2014
comment
Фактическое использование римских букв было более гибким, чем позволяет современная конвенция: CCCCC и D были абсолютно правильными способами указать 500. Просто чтобы усложнить ситуацию, использование римских букв в период своего расцвета также включало поддержку больших значений — макрон (горизонтальная черта) над цифрой масштабируется на 1000 (M-с-макроном = 1 000 000, V-с-макроном = 5 000 и т. д.) Регулярность для слабаков! - person Nicholas Carey; 04.02.2014
comment
Круто, я не знал об этом. Мне скорее нравится подход. Пара других комментариев: (1) нужен терминальный случай roman_to_decimal([], D, D)., (2) roman(S,T1,D) должен быть roman_to_decimal(S,T1,D), я полагаю, (3) нужно сократить, или roman_to_decimal("MCM", D") даст 1900 и 2100 в качестве решений. - person lurker; 04.02.2014
comment
Исправлены опечатки. Я помню кое-что из школьных уроков латыни :D - person Nicholas Carey; 04.02.2014

arrow_upward
2
arrow_downward

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

numeral('I', 1).
numeral('V', 5).
numeral('X', 10).
numeral('L', 50).
numeral('C', 100).
numeral('D', 100).
numeral('M', 1000).

r2n(R, N) :-
    char_code(A, R),
    lower_upper(A, C),
    numeral(C, N).

trans(R, N) :-
    maplist(r2n, R, Rn),    % Pre-calculate a numeric list representation
    trans(Rn, 0, N).
trans([X,Y|T], Acc, N) :-
    X >= Y,
    Acc1 is Acc + X,
    trans([Y|T], Acc1, N).
trans([X,Y|T], Acc, N) :-
    X < Y,
    Acc1 is Acc - X,
    trans([Y|T], Acc1, N).
trans([X], Acc, N) :-
    N is Acc + X.
trans([], N, N).   % Optional rule: needed only if you want trans("", 0). to succeed

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

Пример вывода:

| ?- trans("mmxiv", X).

X = 2014 ? ;

no
| ?- trans("CMXCIX", X).

X = 999 ? ;

no
| ?- trans("IM", X).

X = 999 ? ;

no
| ?- trans("IVX", X).   % Not a properly-formed Roman numeral

X = 4 ? ;   % Uh... ok... I guess

no
person lurker    schedule 04.02.2014