prolog - Prolog-生成斐波那契数列

Question

我想写给定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).

Answer 1

您可以通过使递归谓词尾递归来提高速度:

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)，我们从 reverse/2中删除目标 fib_seq/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不变，并使用其他目标 fib/2来测量 reverse/2(然后 R解决方案中的 fib/2对应于 L解决方案中的 fib_seq/2):

?- 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与发布的解决方案进行比较。