序言；尝试让斐波那契更有效？

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 个数字，value 是返回值。我不明白如何使用累积来重写这个。而且由于它向后计数，我不明白它如何在计算任何内容之前“知道”最后一个值。 :s 任何意见都会受到赞赏。

Answer 1

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

您列出的斐波那契版本的问题在于它效率低下。每次调用 fibo/2 都会引发另外的 two 调用，但其中一些调用会计算相同斐波那契数列的值。例如，在伪代码中：

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

Answer 2

请参阅相关讨论：

用 SICStus Prolog 概括斐波那契序列

并认为其中的非常好使用有限域约束的解决方案。

Answer 3

也许使用尾递归是一个不错的选择

编辑：
您可以尝试类似 fib(6) = fib(6,0,0) 的方法，而不是将 fib(6) 分解为 fib(5)+fib(4)，第一个参数是步数，当它达到 0 时停止，第二个参数是你最后计算的值，第三个参数是要计算的值，它等于当前第二个和第三个参数的总和（第一步除外，其中 0 + 0 将是 1）

所以要计算，您在每次调用时设置第二个参数并在第三个参数中累积，因此 fib(6,0,0) => fib(5,0,1) =>; fib(4,1,1) =>; fib(3,1,2) =>; fib(2,2,3) =>; fib(1,3,5) =>; fib(0,5,8) 然后返回 8

在该方法中，您实际上不必将返回的地址保存在堆栈中，避免堆栈溢出

Answer 4

请记住，还有另一种计算斐波那契数列的方法：从基本情况开始向上移动。

现在，要计算 fib(n)，请添加 fib(n-1) 和 fib(n-2)。相反，将其翻转并根据斐波那契数列的定义计算 fib(0) 和 fib(1)，并以此为基础进行构建。

Answer 5

你几乎已经拥有它了。只需重写：

fibo(N, Value) :-
N1 is N-1, N2 is N-2,
 fibo(N1, LastValue),fibo(N2, SecondToLastValue),
 Value is LastValue + SecondToLastValue.

就

fibo2(N, Value, LastValue):- ...

我不明白如何重写
这使用累积

就不要这样做，这不是必需的（尽管可以这样做）。