序言; 试着让斐波那契更有效？

Question

这种逻辑编程实际上是在我的命令式编程技巧上跳舞.这是家庭作业,所以请不要给我答案.这就是我所拥有的:

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个数字,值是返回值.我不明白我怎么能用累积重写这个.而且由于它向后计数,我不知道它在计算任何东西之前如何"知道"最后一个值.:s任何输入表示赞赏.

Answer 1

我可以在这里发布解决方案,但既然这是家庭作业,那就会适得其反.相反,这是一个领导:

您列出的Fibonacci版本的问题是它效率低下.每次调用fibo/2都会导致另外两次调用,但其中一些调用会计算相同Fibonacci数的值.例如,在伪代码中:

(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.