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

Question

我想在Prolog中编写一个预测reverse(N,Result)。例如：

• reverse(12345,Result).
• 结果为：Result = 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.

请问我能得到一些帮助吗？

非常感谢您提前的帮助。

- Yazhrod

---

我试图打招呼，但我无法编辑我的帖子。 - Yazhrod

@Yashrod 你尝试过将数字拆分为数字列表，然后将其反转，最后再将数字反转构建吗？ - Anton Danilov

@AntonDanilov 抱歉，我应该说我不能使用列表，我编辑了我的帖子。 - Yazhrod

如果 N >= 0 而不仅仅是 N > 0，为什么 reverse(N, N) 不会成立呢？ - lurker

Answer 1

我建议使用CLP(FD)，因为它提供了整数算术的声明性推理，许多Prolog系统都提供它。关于数字反转，我建议您查看The On-Line Encyclopedia of Integer Sequences中的条目A004086。在标题为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.

- tas

---

谢谢您的时间。这对我很有帮助。 - Yazhrod

Answer 2

如果由于某些原因您不想使用基于约束的解决方案，或者您正在使用不支持约束的Prolog系统，则可选择另一种解决方案：

reverse_digits(N, M) :-
    (   integer(N) ->
        reverse_digits(N, 0, M)
    ;   integer(M),
        reverse_digits(M, 0, N)
    ).

reverse_digits(0, M, M) :- !.
reverse_digits(N, M0, M) :-
    N > 0,
    R is N div 10,
    M1 is M0 * 10 + N mod 10,
    reverse_digits(R, M1, M).

这个解决方案可以用于绑定到整数的任何一个参数，不会留下多余的选择点：

?- reverse_digits(12345, M).
M = 54321.

?- reverse_digits(N, 12345).
N = 54321.

?- reverse_digits(12345, 54321).
true.

但请注意，与基于约束条件的解决方案不同，这种解决方案不能用作满足关系的整数对的生成器。

?- reverse_digits(N, M).
false.

- Paulo Moura

---

谢谢你的帮助。 - Yazhrod

Answer 3

reverseNumber(N,R):-reverse_acc(N,0,R).
reverse_acc(0,Acc,Acc).
reverse_acc(N,Acc,R):- C is N mod 10, N1 is N div 10, 
                                     Acc1 is Acc * 10 + C, 
                                     reverse_acc(N1, Acc1,R).

- Emilian Anton

---

请记住，Stack Overflow 不仅旨在解决当前的问题，还要帮助未来的读者找到类似问题的解决方案，这需要理解底层代码。对于我们社区中的初学者和不熟悉语法的成员来说，这尤其重要。鉴于此，您能否编辑您的答案，包括您正在做什么的解释以及为什么您认为这是最好的方法？ - Jeremy Caney