Prolog - 生成斐波那契数列

Question

Prolog - 生成斐波那契数列

3

我希望编写一个断言，为给定的N生成斐波那契数列。

fibon(6, X) -> X = [0,1,1,2,3,5].

我有一个生成斐波那契数列第N个元素的谓词：

fib(0, 0).
fib(1, 1).
fib(N, F) :-
    N > 1,
    N1 is N - 1,
    N2 is N - 2,
    fib(N1, F1),
    fib(N2, F2),
    F is F1 + F2.

我试图编写fibon/2函数，但它没有起作用：

fibon(N, [H|T]) :-
    fib(N, H),
    N1 is N - 1,
    fibon(N1, T).

我解决它的方法如下：

at_the_end(X, [], [X]).
at_the_end(X, [H|T], [H|T2]) :-
    at_the_end(X, T, T2).

revert([], []).
revert([H|T], Out) :-
    revert(T, Out1),
    at_the_end(H, Out1, Out).

fib(0, 0).
fib(1, 1).
fib(N, F) :-
    N > 1,
    N1 is N - 1,
    N2 is N - 2,
    fib(N1, F1),
    fib(N2, F2),
    F is F1 + F2.

fibon(0, [0]).
fibon(N, [H|T]) :-
    fib(N, H),
    N1 is N - 1,
    fibon(N1, T).

fibonacci(In, Out) :-
    fibon(In, Out1),
    revert(Out1, Out).

- user

fibon/2 的递归基是什么？如果 N = 0 或者 N < 0 会发生什么？ - lurker

事实上，现在它可以工作了。我会更新这个问题。 - user

你的递归子句应该有一个 N > 0 条件，以避免因 N 变成 < 0 而导致非终止问题。此外，你的基本情况可能应该是 fibon(0, [])，因为 0 不是斐波那契数。如果你没有斐波那契数（0），那么你应该有一个空列表，对吗？ - lurker

4个回答

2

如果你愿意颠倒序列结果的顺序，那么这段代码可以工作：

``` fib(0, [0]). fib(1, [1,0]). fib(N, [R,X,Y|Zs]) :- N > 1, N1 is N - 1, fib(N1, [X,Y|Zs]), R is X + Y. ```

然后输入 `?- fib(15,Z).` 可以得到 `[610, 377, 233, 144, 89, 55, 34, 21, 13, 8, 5, 3, 2, 1, 1, 0]`。

很容易加入一个 `reverse/3` 谓词：

``` reverse([],Z,Z). reverse([H|T],Z,A) :- reverse(T,Z,[H|A]). ```

- Enigmativity

1

仅供娱乐使用，使用 scanl 和一些标准的 dcgs。

:-use_module(library(clpfd)).

my_plus(X,Y,Z):-
    Z#>=0,
    Z#=<1000, % Max size optional
    Z#=X+Y.

list([])     --> [].
list([L|Ls]) --> [L], list(Ls).

concatenation([]) --> [].
concatenation([List|Lists]) -->
        list(List),
        concatenation(Lists).

fib(Len,List1):-
    X0=1,
    length(List1,Len),
    length(End,2),
    MiddleLen #= Len - 3,
    length(Middle,MiddleLen),
    phrase(concatenation([[X0],Middle,End]), List1),
    phrase(concatenation([[X0],Middle]), List2),
    phrase(concatenation([Middle,End]), List3),
    scanl(my_plus,List2,X0,List3).

- user27815

0

如果您想收集斐波那契数列的前N个元素列表，可以使用以下规则。只需记得初始化前两个谓词即可。

fib(0, [1]).
fib(1, [1, 1]).

fib(N, L) :-
    N > 1,
    N1 is N - 1,
    N2 is N - 2,
    fib(N1, F1),
    last(F1, L1),
    fib(N2, F2),
    last(F2, L2),
    L_new is L1 + L2,
    append(F1, [L_new], L).

- Parsa

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- tas · Accepted Answer

你可以通过将递归谓词变成尾递归来提高一些速度：

fib_seq(0,[0]).                   % <- base case 1
fib_seq(1,[0,1]).                 % <- base case 2
fib_seq(N,Seq) :-
   N > 1,
   fib_seq_(N,SeqR,1,[1,0]),      % <- actual relation (all other cases)
   reverse(SeqR,Seq).             % <- reverse/2 from library(lists)

fib_seq_(N,Seq,N,Seq).
fib_seq_(N,Seq,N0,[B,A|Fs]) :-
   N > N0,
   N1 is N0+1,
   C is A+B,
   fib_seq_(N,Seq,N1,[C,B,A|Fs]). % <- tail recursion

首先让我们观察你的示例查询是否按预期工作：

?- fib_seq(6,L).
L = [0, 1, 1, 2, 3, 5, 8] ;
false.

请注意，列表中不是像你在帖子开头所示的例子中有六个元素，而是七个。这是因为谓词从零开始计数（顺便说一下，这与您在帖子中添加的谓词 fibonacci/2 的行为相同）。

为了比较（与@Enigmativity的帖子中的 fib / 2 进行比较）的原因，让我们从 fib_seq / 2 中删除目标 reverse / 2 （然后您将以相反的顺序获得除N = 0和N = 1之外的所有解决方案）。

?- time((fib(50000,L),false)).
% 150,001 inferences, 0.396 CPU in 0.396 seconds (100% CPU, 379199 Lips)
false.

?- time((fib_seq(50000,L),false)).
% 150,002 inferences, 0.078 CPU in 0.078 seconds (100% CPU, 1930675 Lips)
false.

或者保持fib_seq/2不变，使用附加目标reverse/2来测量fib/2（然后fib/2解决方案中的R对应于fib_seq/2解决方案中的L）：

?- time((fib(50000,L),reverse(L,R),false)).
% 200,004 inferences, 0.409 CPU in 0.409 seconds (100% CPU, 488961 Lips)
false.

?- time((fib_seq(50000,L),false)).
% 200,005 inferences, 0.088 CPU in 0.088 seconds (100% CPU, 2267872 Lips)
false.

顺便提一下，当你尝试处理更大的列表时，比如 N > 30，我建议你和已发布的解决方案比较一下你的谓词 fibonacci/2。