3

在尝试学习 Prolog 时，我遇到了一个很好的练习，那就是编写一个显示第 N 个斐波那契数的程序。经过一些工作，我让它工作起来，然后决定看看我是否可以编写一个程序，根据输入显示一系列斐波那契数。

例如输入：

?- fib_sequence(2,5,Output).

给出输出：

?- Output = [1,1,2,3]

然而，我很难找到一个好的起点。这是我到目前为止所拥有的：

fib(0, 0).
fib(1, 1).
fib(N, F) :- X is N - 1, Y is N - 2, fib(X, A), fib(Y, B), F is A + B.

fib_sequence(A,B,R) :- fib(A,Y) , fib(B,Z).

我知道我必须为R分配一个值，但我不确定如何分配多个值。任何帮助是极大的赞赏。

4

3 回答 3

3

Observe that your fib_sequence cannot be done in a single predicate clause: you need at least two to keep things recursive - one to produce an empty list when A is greater than B (i.e. we've exhausted the range from A to B), and another one to prepend X from fib(A,X) to a list that you are building, increment A by 1, and call fib_sequence recursively to produce the rest of the sequence.

The first predicate clause would look like this:

fib_sequence(A,B,[]) :- A > B.

The second predicate clause is a bit harder:

fib_sequence(A,B,[H|T]) :-
    A =< B                   /* Make sure A is less than or equal to B */
,   fib(A, H)                /* Produce the head value from fib(A,...) */
,   AA is A + 1              /* Produce A+1 */
,   fib_sequence(AA, B, T).  /* Produce the rest of the list */
于 2013-10-25T00:37:24.287 回答
1

这是另一种方法。首先，我重新fib做了一点，使它只递归地调用自己一次而不是两次。为此，我创建了一个谓词，它返回前两个斐波那契值而不是最后一个：

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

为了获得序列，我选择了一种内置斐波那契计算的算法，这样它就不需要调用fibO(n^2) 次。但是，它确实需要在完成时反转列表：

fib_sequence(A, B, FS) :-
    fib_seq_(A, B, FSR),
    reverse(FSR, FS).

fib_sequence_(A, B, []) :-
    A > B.
fib_sequence_(A, B, [F]) :-
    A =:= B,
    fib(A, F, _).
fib_sequence_(A, B, [F1,F0]) :-
    1 is B - A,
    fib(B, F1, F0).
fib_sequence_(A, B, [F2,F1,F0|FT] ) :-
    B > A,
    B1 is B - 1,
    fib_sequence_(A, B1, [F1,F0|FT]),
    F2 is F1 + F0.

这是另一种方法，无需反向即可，但上面的反向方法执行起来似乎要快一些。

fib_sequence_dl(A, B, F) :-
    fib_sequence_dl_(A, B, F, [_,_|[]]).

fib_sequence_dl_(A, B, [], _) :-
    A > B, !.
fib_sequence_dl_(A, B, [F], _) :-
    A =:= B,
    fib(A, F, _), !.
fib_sequence_dl_(A, B, [F0,F1|T], [F0,F1|T]) :-
    1 is B - A,
    fib(B, F1, F0), !.
fib_sequence_dl_(A, B, F, [F1,F2|T]) :-
    A < B,
    B1 is B - 1,
    fib_sequence_dl_(A, B1, F, [F0,F1|[F2|T]]),
    F2 is F0 + F1.
于 2013-10-25T14:16:25.887 回答
1

Prolog 内置了一些帮助程序来处理数字序列，然后作为 dasblinkenlight' 答案的替代方法，这是一个惯用的“查询”：

fib_sequence(First, Last, Seq) :-
    findall(F, (between(First,Last,N), fib(N,F)), Seq).

请注意，它不适用于您的 fib/2 开箱即用，因为存在一个错误：我添加了一个条件，以避免您在尝试回溯fib/2 解决方案时遇到的无限循环：

fib(N, F) :- N > 1, % added sanity check
    X is N - 1, Y is N - 2, fib(X, A), fib(Y, B), F is A + B.
于 2013-10-25T09:28:22.203 回答