关联罗马数字和阿拉伯数字

问题描述 投票：0回答：3

如何将899999以内的罗马数字和阿拉伯数字进行纯关联？而这次没有使用算术！因此没有

(is)/2
也没有
clpfd
/
clpz
/
clpq
。由于缺乏与整数相关的任何方式，阿拉伯数字必须表示为字符列表。因此
:- set_prolog_flag(double_quotes, chars).
。用于罗马数字的字符如下。

像往常一样，阿拉伯数字没有前导零，中间也没有空格，罗马数字使用“通用”减法规则。见下文。

到目前为止我尝试过的是使用整数。但是这里应该没有他们。效率不是目标，但终止是。

纯部分包括

dif/2
和
dif_si/2
虽然90个事实也可以表达小数位之间的不平等。

?- arabic_roman(A,R) , false.
   false.  % it terminates, we have only 899999 numbers, very finite
?- arabic_roman("0",R).
   false. % no zero
?- arabic_roman(['0'|_],R).
   false. % and in general no leading zeros
?- R=[_], arabic_roman(A,R).
   R = "I", A = "1"
;  R = "V", A = "5"
;  R = "X", A = "10"
;  R = "L", A = "50"
;  R = "C", A = "100"
;  R = "D", A = "500" % no apostrophus "IↃ"
;  R = "M", A = "1000" % no "CIↃ"
;  R = "ↁ", A = "5000" % idem
;  R = "ↂ", A = "10000"
;  R = "ↇ", A = "50000"
;  R = "ↈ", A = "100000"
;  R = "@", A = "500000" % poor support in Unicode
;  false.
?- arabic_roman("899999",R).
   R = "@ↈↈↈↂↈMↂCMXCIX" % the largest number
;  false.
?- arabic_roman(  ['9',_,_, _,_,_],R).
   false. % no six digit number starting with 9
?- arabic_roman( [_, _,_,_, _,_,_|_],R).
   false. % no seven or more digit numbers
?- setof(R,A^arabic_roman(A,R),Rs),length(Rs,N).
   Rs = ["@","@C","@CC","@CCC"|_], N = 899999.  % terms omitted at _
?- setof(A,R^arabic_roman(A,R),As),length(As,N).
   As = ["1","10","100","1000","10000","100000","100001"|_], N = 899999.
?- setof(A-R,arabic_roman(A,R),ARs),length(ARs,N).
   ARs = ["1"-"I","10"-"X","100"-"C","1000"-"M","10000"-"ↂ"|_], N = 899999.
?- arabic_roman(A,"IL").
   false. % no generalized subtractive rule
?- arabic_roman(A,"IM").
   false. % idem
?- arabic_roman(A,R), phrase((...,[X,X,X,X],...),R).
   false.
prolog roman-numerals
3个回答
2
投票

这是我的解决方案。我更改了一些罗马符号，因为我的设置对 unicode 的支持很差，所以 

P
是 5000，
T
是 10000，
F
是 50000，
Q
是 100000 和 
@
是 500000.

:- set_prolog_flag(double_quotes, chars).

arabic_roman(A, R):- phrase(arabic_roman(A), R).

arabic_roman([A|As])-->
  { dif(A, '0') },
  arabic_roman_skip("Q@!TFMPCDXLIV!!", [A|As]).

arabic_roman_skip([P,_,_,P1,C1|S], As)-->
  arabic_roman_skip([P1,C1,P|S], As).
arabic_roman_skip(S, As)-->
  arabic_roman(S, As).

arabic_roman("!!I", [])-->[].
arabic_roman([P,C,N,P1,C1|S], [A|As])-->
  arabic_digit_roman(A, P,C,N),
  arabic_roman([P1,C1,P|S], As).

arabic_digit_roman('0', _,_,_) --> [].
arabic_digit_roman('1', P,_,_) --> [P].
arabic_digit_roman('2', P,_,_) --> [P,P].
arabic_digit_roman('3', P,_,_) --> [P,P,P].
arabic_digit_roman('4', P,C,_) --> [P,C].
arabic_digit_roman('5', _,C,_) --> [C].
arabic_digit_roman('6', P,C,_) --> [C,P].
arabic_digit_roman('7', P,C,_) --> [C,P,P].
arabic_digit_roman('8', P,C,_) --> [C,P,P,P].
arabic_digit_roman('9', P,_,N) --> [P,N], {dif(N,'!')}.

样品运行：

?- arabic_roman("899999",R).
R = [@, 'Q', 'Q', 'Q', 'T', 'Q', 'M', 'T', 'C', 'M', 'X', 'C', 'I', 'X'].
?- time((setof(A1,R^A^(arabic_roman(A,R), atom_codes(A1,A)),As),length(As,N))).
% 3,118,631 inferences, 1.841 CPU in 1.879 seconds (98% CPU, 1694161 Lips)
As = ['1', '10', '100', '1000', '10000', '100000', '100001', '100002', '100003'|...],
N = 899999.
2
投票

似乎不太值得使用 DCG：

% Need nan, to fill the last group of [I, V, X]
roman_chars(['I', 'V', 'X', 'L', 'C', 'D', 'M', 'ↁ', 'ↂ', 'ↇ', 'ↈ', '@', nan]).

arabic_digit_roman('0', _I, _V, _X, T, T).
arabic_digit_roman('1', I, _, _, [I|T], T).
arabic_digit_roman('2', I, _, _, [I, I|T], T).
arabic_digit_roman('3', I, _, _, [I, I, I|T], T).
arabic_digit_roman('4', I, V, _, [I, V|T], T).
arabic_digit_roman('5', _, V, _, [V|T], T).
arabic_digit_roman('6', I, V, _, [V, I|T], T).
arabic_digit_roman('7', I, V, _, [V, I, I|T], T).
arabic_digit_roman('8', I, V, _, [V, I, I, I|T], T).
arabic_digit_roman('9', I, _, X, [I, X|T], T) :-
    dif(X, nan).

arabic_roman(A, R) :-
    % No leading zero
    A = [First|_],
    dif(First, '0'),
    roman_chars(RCs),
    arabic_roman_(A, RCs, R).

arabic_roman_([], _, []).
arabic_roman_([AH|AT], RCs, R) :-
    arabic_length(AT, RCs, I, V, X, RCs0),
    arabic_digit_roman(AH, I, V, X, R, T),
    arabic_roman_(AT, RCs0, T).
    
arabic_length([], [I, V, X|_], I, V, X, [I]).
arabic_length([_|T], [II, VV|R], I, V, X, [II, VV|RC]) :-
    arabic_length(T, R, I, V, X, RC).

阿拉伯语列表研磨时没有不需要的选择点，例如：

?- arabic_roman(['1', '2', '3', '4', '5', '6'], R).
R = [ↈ, ↂ, ↂ, 'M', 'M', 'M', 'C', 'D', 'L', 'V', 'I'].

swi-prolog 中的性能：

?- time((setof(A1,R^A^(arabic_roman(A,R), atom_codes(A1,A)),As), length(As,N))).
% 3,212,762 inferences, 0.521 CPU in 0.522 seconds (100% CPU, 6169023 Lips)
As = ['1', '10', '100', '1000', '10000', '100000', '100001', '100002', ...
N = 899999.
1
投票

有 15 个子句（取决于我们如何计算）。它终止了。

:- use_module(library(dcgs)).
:- use_module(library(lists)).
:- use_module(library(dif)).

foldl(G__3, [], S, S) --> [].
foldl(G__3, [E|Es], S0, S) --> call(G__3, E, S0, S1), foldl(G__3, Es, S1, S).

d5u('0', s([R10|Rs],[R5,R1|Ds]), s([R1,R5,R10|Rs],Ds)) --> [].
d5u('1', s(Rs,[R5,R1|Ds]), s([R1,R5|Rs],Ds)) --> [R1].
d5u('2', s(Rs,[R5,R1|Ds]), s([R1,R5|Rs],Ds)) --> [R1,R1].
d5u('3', s(Rs,[R5,R1|Ds]), s([R1,R5|Rs],Ds)) --> [R1,R1,R1].
d5u('4', s(Rs,[R5,R1|Ds]), s([R1,R5|Rs],Ds)) --> [R1,R5].
d5u('5', s(Rs,[R5,R1|Ds]), s([R1,R5|Rs],Ds)) --> [R5].
d5u('6', s(Rs,[R5,R1|Ds]), s([R1,R5|Rs],Ds)) --> [R5,R1].
d5u('7', s(Rs,[R5,R1|Ds]), s([R1,R5|Rs],Ds)) --> [R5,R1,R1].
d5u('8', s(Rs,[R5,R1|Ds]), s([R1,R5|Rs],Ds)) --> [R5,R1,R1,R1].
d5u('9', s([R10|Rs],[R5,R1|Ds]), s([R1,R5,R10|Rs],Ds)) --> [R1,R10].

au5(_, s([R1,R5|Rs0],Rs), s(Rs0,[R5,R1|Rs])).

arabic_roman([C|Cs]) -->
    { foldl(au5, [C|Cs], s("IVXLCDMↁↂↇↈ@",[]), S0) },
    foldl(d5u,[C|Cs], S0, s([_|_],[])),
    { dif(C, '0') }.

arabic_roman(A, R) :-
    phrase(arabic_roman(A), R).
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.