前言;尝试使斐波那契更有效? [英] Prolog; try to make fibonacci more effective?

问题描述

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

This logic programming is really making a lap dance on my imperative programming skills. This is homework, so please just don't drop me the answer. This is what I have:

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感谢您的任何投入.

I'm suppose to make another function that looks like this; fib(N,Value,LastValue). N is the n'th number, and value is the return value. I don't understand how I can rewrite this using accumulation. And since it counts backwards I don't see how it can "know" a last value before it calculates anything. :s Any input is appreciated.

推荐答案

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

I could post here the solution, but since that this is homework, it would be counter-productive. Instead, here's a lead:

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

The problem with the version of Fibonacci that you listed is that it is inefficient. Each call to fibo/2 causes another two calls, but some of these calls calculate the values of the same Fibonacci numbers. For example, in pseudo-code:

(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 只会导致一个递归调用(因此可以在线性时间内计算斐波那契数列).您需要将基本情况更改为:

To overcome this deficiency, you were asked to rephrase Fibonacci in terms of returning not just the last value, but the last two values, so that each call to fib/3 will cause only a single recursive call (hence calculate the Fibonacci series in linear time). You'll need to change the base cases to:

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.

这篇关于前言;尝试使斐波那契更有效?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！