loops - 如何在Prolog中计算数字序列的总和

Question

任务是计算从 0 到 M 的自然数之和。我使用 SWI-Prolog 编写了以下代码：

my_sum(From, To, _) :- From > To, !.
my_sum(From, To, S) :-
  From = 0,
  Next is 1,
  S is 1,
  my_sum(Next, To, S).
my_sum(From, To, S) :-
  From > 0,
  Next is From + 1,
  S is S + Next,
  my_sum(Next, To, S).

但是当我尝试计算时：

my_sum(0,10,S), writeln(S).

我得到了 False 而不是正确的数字。这个例子出了什么问题？

Answer 1

这对于 Next \= 0: 肯定是错误的S is S + Next。另一个更基本的问题是您正在以“相反”的顺序进行计算。也就是说，当From > To程序停止时，您不会“取回”结果。然后你应该添加一个累加器（另一个参数，要传播到所有递归调用）并在最后一步将它与部分总和统一......

无论如何，应该更简单：

my_sum(From, To, S) :-
  From < To,
  Next is From + 1,
  my_sum(Next, To, T),
  S is T + From.
my_sum(N, N, N).

| ?- my_sum(2, 4, N).
N = 9

Answer 2

我会按照这些思路编写谓词，使用带有附加累加器的工作谓词：

sum(X,Y,Z) :-
  integer(X)   ,
  integer(Y)   ,
  sum(X,Y,0,Z)
  .

sum(X,X,T,Z) :- Z is T+X .
sum(X,Y,T,Z) :- X < Y , X1 is X+1 , T1 is T+X , sum(X1,Y,T1,Z) .
sum(X,Y,T,Z) :- X > Y , X1 is X-1 , T1 is T+X , sum(X1,Y,T1,Z) .

这个实现很简单，是双向的，意味着sum(1,3,X)结果sum(3,1,X)是 6 (1+2+3)，尾递归，意味着它应该能够处理任意大小的范围而不会发生堆栈溢出。

Answer 3

碰巧，还有一个纯粹的分析解决方案：

sum(N, Sum) :- Sum is N * (N+1) / 2.

正在使用：

?- sum(100, N).
N = 5050.

您使用了循环标签，因此这可能不是您想要的答案，但如果存在这种解决方案，最好选择这种解决方案。

Answer 4

predicates
 sum(integer,integer)

clauses
 sum(0,0).
 sum(N,R):-
     N1=N-1,
     sum(N1,R1),
     R=R1+N.