9

这种逻辑编程真的让我的命令式编程技能跳了起来。这是作业，所以请不要让我回答。这就是我所拥有的：

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 任何输入表示赞赏。

4

5 回答 5

5

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

您列出的斐波那契版本的问题是它效率低下。每次调用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.
于 2010-11-23T20:16:03.257 回答
2

请参阅相关讨论：

用 SICStus Prolog 概括斐波那契数列

并从那里考虑使用有限域约束的非常好的解决方案。

于 2010-11-23T10:19:58.147 回答
1

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

编辑：而不是将 fib(6) 分解为 fib(5)+fib(4) 您可以尝试类似 fib(6) = fib(6,0,0) 第一个参数是步数，当它达到 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

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

于 2010-11-23T17:23:29.760 回答
0

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

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

于 2010-11-23T00:30:29.557 回答
-1

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

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):- ...

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

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

于 2010-11-23T00:49:19.090 回答