前言;尝试使斐波那契更有效？

逻辑编程确实使我的命令式编程技能跳了起来。这是家庭作业，所以请不要给我答案。这就是我所拥有的:

fibo(N,1) :-
   N < 2,
   !.
fibo(N,R) :-
   N1 is N-1,
   N2 is N-2,
   fibo(N1,R1),
   fibo(N2,R2),
   R is R1+R2.

我想做另一个看起来像这样的函数； fib(N,Value,LastValue)。N是第n个数字，value是返回值。我不明白如何使用累积重写此内容。而且由于它是倒数的，所以我看不到它在计算任何内容之前如何“知道”最后一个值。 :s任何输入表示赞赏。

最佳答案

我可以在此处发布解决方案，但是由于这是家庭作业，因此会适得其反。相反，这里有一条线索:

您列出的Fibonacci版本的问题是效率低下。每次对fibo/2的调用都会导致另一个和两个调用，但是其中一些调用会计算相同斐波纳契数的值。例如，用伪代码:

(a) fibo(4) -> fibo(3), fibo(2)
(b) fibo(3) -> fibo(2), fibo(1)
(c) fibo(2) -> fibo(1), fibo(0) % called from (a)
(d) fibo(2) -> fibo(1), fibo(0) % called from (b), redundant

为了克服这一缺陷，要求您重新定义斐波那契，不仅返回最后一个值，而且还要返回最后两个值，以便每次对fib/3的调用仅会导致一次递归调用(因此将以线性时间计算斐波那契数列) 。您需要将基本案例更改为:

fib(1,1,0).
fib(2,1,1).

我将递归的情况留给您。

对于急躁的人

这也是递归的情况:

fib(N, Val, Last) :-
  N > 2,
  N1 is N - 1,
  fib(N1, Last, Last1), % single call with two output arguments,
                        % instead of two calls with one output argument
  Val is Last + Last1.