Prolog 中的斐波那契数列 - 如果为假则中断

Question

我有一个程序 fib(X,Y)。如果 Y 是第 X 个斐波那契数，它 returns True 否则它应该 return False。每当我输入错误的语句时，我的程序就会中断。

fib(R,V) :- fib(0,1,R,V).
fib(X, Y, 0, V) :- Y == V.
fib(X, Y, R, V) :- Z is X + Y, C is R - 1, fib(Y, Z, C, V).

fib(0,1) -> True
fib(1,1) -> True
fib(2,2) -> True
fib(3,3) -> True
fib(4,5) -> True

fib(3,5) -> Won't finish.

我做错了什么？我正在使用 https://swish.swi-prolog.org/ 到运行我的程序查询。

Answer 1

这里的问题是你写了两个子句fib(X, Y, 0, V) :-和fib(X, Y, R, V) :-。 Prolog 使用回溯：如果已经尝试了一个子句，无论成功还是失败，它都会稍后重试下一个子句（有一些元谓词，如 once/1可以改变这个）。

所以即使 R 是 0 或更低，Prolog 也会尝试第二个子句。

解决这个问题的一种快速方法是对第二个子句使用守卫：

fib(<b>_</b>, Y, 0, V) :-
    Y == V.
fib(X, Y, R, V) :-
    <b>R > 0,</b>
    Z is X + Y,
    C is R - 1,
    fib(Y, Z, C, V).

此外，您的代码不是很优雅，因为您不能以相反的方式使用关系，我们也不能查询第 X 个元素。

例如您使用 Y == V，但这会阻止统一：如果我们想知道第 X 个斐波那契数，我们需要一种传播结果的方法背部。所以我们可以使用统一代替：

fib(_, <B>V</b>, 0, V).
fib(X, Y, R, V) :-
    R > 0,
    Z is X + Y,
    C is R - 1,
    fib(Y, Z, C, V).

但现在我们仍然没有双向关系：我们无法获得给定值 V 的 X。这更复杂。最简单的方法可能是为此使用 clpfd：

<b>:- use_module(library(clpfd)).</b>

fib(_, V, 0, V).
fib(X, Y, R, V) :-
    <b>R #> 0,</b>
    <b>V #>= Y,</b>
    Z is X + Y,
    <b>C #= R - 1,</b>
    fib(Y, Z, C, V).

现在我们可以：

枚举所有指数和对应的斐波那契数列：

?- fib(A,B).
A = 0,
B = 1 ;
A = B, B = 2 ;
A = B, B = 3 ;
A = 4,
B = 5 ;
A = 5,
B = 8 ;
A = 6,
B = 13 ;
A = 7,
B = 21
...

获得第i个斐波那契数：

?- fib(2,B).
B = 2 ;
false.

?- fib(10,B).
B = 89 ;
false.

得到i对应的斐波那契数为某个值：

?- fib(A,1).
A = 0 ;
A = 1 ;
false.

?- fib(A,2).
A = 2 ;
false.

?- fib(A,3).
A = 3 ;
false.

?- fib(A,4).
false.

?- fib(A,5).
A = 4 ;
false.

检查第i个斐波那契数是否为给定值：

?- fib(4,5).
true ;
false.

?- fib(4,6).
false.

?- fib(4,10).
false.

?- fib(5,8).
true ;
false.

Prolog 中的斐波那契数列 - 如果为假则中断

Fibonacci in Prolog - Breaks if False

prolog

fibonacci