recursion - 如何使用尾递归在 Prolog 中反转整数？

Question

我想在 Prolog 中做一个 predicat reverse(N,Result)。

例如:

反向(12345，结果)。

结果 = 54321。

我必须使用尾递归。我可以使用 *、+、- 和 divmod/4，仅此而已。我不能使用列表。

我可以反转一个小于 100 的数字，但我不知道如何完成我的代码，我无法完成我的代码来正确反转大于 100 的整数。

reverse(N,N):-
    N <10,
    N>0.

reverse(N,Result):-
    N > 9,
    iter(N,0,Result).

iter(N,Ac,Result):-
    N  < 100, !,
    divmod(N,10,Q,R),
    R1 is R*10,
    Result is Q + R1.

我可以帮忙吗？

提前谢谢你。

Answer 1

我建议使用 CLP(FD) ，因为它提供了对整数算术的声明式推理，并且许多 Prolog 系统都提供了它。关于数字反转，我建议您查看条目 A004086 in The On-Line Encyclopedia of Integer Sequences .在标题为 FORMULA 的段落中，您会发现以下公式:

a(n) = d(n,0) with d(n,r) = if n=0 then r else d(floor(n/10),r*10+(n mod 10))

这些可以通过为反向数字添加额外的参数来转换为谓词。首先让我们给它一个漂亮的声明性名称，比如 digits_reversed/2 .那么这个关系可以用 #>/2表示, #=/2 , (/)/2 , +/2 , mod/2和尾递归:

:- use_module(library(clpfd)).

digits_reversed(N,X) :-
   digits_reversed_(N,X,0).

digits_reversed_(0,R,R).
digits_reversed_(N,X,R) :-
   N #> 0,
   N0 #= N/10,
   R1 #= R*10 + (N mod 10),
   digits_reversed_(N0,X,R1).

请注意 digits_reversed/2对应 a(n)和 digits_reversed_/3对应于 d(n,r)在上面的公式中。现在让我们使用您帖子中的示例查询谓词:

?- digits_reversed(12345,R).
R = 54321 ;
false.

谓词也可以用在另一个方向，即问什么数颠倒得到54321？然而，由于省略了数字的前导零，一个反转的数字有无限多个原始数字:

?- digits_reversed(N,54321).
N = 12345 ;
N = 123450 ;
N = 1234500 ;
N = 12345000 ;
N = 123450000 ;
N = 1234500000 ;
N = 12345000000 ;
N = 123450000000 ;
.
.
.

即使是最一般的查询也会产生解决方案，但您会得到剩余目标作为超过一位数的数字的答案:

?- digits_reversed(N,R).
N = R, R = 0 ;              % <- zero
N = R,
R in 1..9 ;                 % <- other one-digit numbers
N in 10..99,                % <- numbers with two digits
N mod 10#=_G3123,
N/10#=_G3135,
_G3123 in 0..9,
_G3123*10#=_G3159,
_G3159 in 0..90,
_G3159+_G3135#=R,
_G3135 in 1..9,
R in 1..99 ;
N in 100..999,              % <- numbers with three digits
N mod 10#=_G4782,
N/10#=_G4794,
_G4782 in 0..9,
_G4782*10#=_G4818,
_G4818 in 0..90,
_G4818+_G4845#=_G4842,
_G4845 in 0..9,
_G4794 mod 10#=_G4845,
_G4794 in 10..99,
_G4794/10#=_G4890,
_G4890 in 1..9,
_G4916+_G4890#=R,
_G4916 in 0..990,
_G4842*10#=_G4916,
_G4842 in 0..99,
R in 1..999 ;
.
.
.

要通过上述查询获得实际数字，您必须限制 N 的范围。并在谓词发布算术约束后标记它:

?- N in 10..20, digits_reversed(N,R), label([N]).
N = 10,
R = 1 ;
N = R, R = 11 ;
N = 12,
R = 21 ;
N = 13,
R = 31 ;
N = 14,
R = 41 ;
N = 15,
R = 51 ;
N = 16,
R = 61 ;
N = 17,
R = 71 ;
N = 18,
R = 81 ;
N = 19,
R = 91 ;
N = 20,
R = 2 ;
false.