prolog中前n个数字的总和

Question

你好任何人都可以帮我计算前n个数字的总和.例如,n = 4 => sum = 10.到目前为止,我已经写了这个

    predicates
  sum(integer,integer)
clauses

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

这个工作但我需要另一个实现.我没有任何想法如何使这种差异化.请帮忙

Answer 1

什么@mbratch说.

你计算的是一个三角形数字.如果你的作业是关于三角形数字而不是学习递归思维,你可以简单地计算它:

triangular_number(N,R) :- R is N * (N+1) / 2 .

如果您更有可能学习递归思想,请尝试以下方法:

 sum(N,R) :-    % to compute the triangular number n,
   sum(N,1,0,R) % - invoke the worker predicate with its counter and accumulator properly seeded
   .

 sum(0,_,R,R).     % when the count gets decremented to zero, we're done. Unify the accumulator with the result.
 sum(C,X,T,R) :-   % otherwise,
   C > 0 ,         % - assuming the count is greater than zero
   T1 is T+X ,     % - increment the accumulator
   X1 is X+1 ,     % - increment the current number
   C1 is C-1 ,     % - decrement the count
   sum(C1,X1,T1,R) % - recurse down
   .               % Easy!

编辑添加:

或者,如果您更喜欢倒计时方法:

 sum(N,R) :- sum(N,0,R).

 sum(0,R,R).       % when the count gets decremented to zero, we're done. Unify the accumulator with the result.
 sum(N,T,R) :-     % otherwise,
   N > 0 ,         % - assuming the count is greater than zero
   T1 is T+N ,     % - increment the accumulator
   N1 is N-1 ,     % - decrement the count
   sum(N1,T1,R)    % - recurse down
   .               % Easy!

这两个都是尾递归的,这意味着prolog编译器可以将它们转换为迭代(google"tail recursion optimization"以获取详细信息).

如果要消除累加器,则需要执行以下操作:

sum(0,0).
sum(N,R) :-
  N > 0 ,
  N1 is N-1 ,
  sum(N1,R1) ,
  R is R1+N
  .

稍微简单一点,但每次递归都会占用另一个堆栈帧:给定N的值足够大,执行将因堆栈溢出而失败.