ProLog 程序执行中的斐波那契数列总和

Question

我刚刚开始 ProLog 编程并尝试编写斐波那契数列求和程序。

我对这个给定的代码有一个问题。

任何人都可以告诉我这将如何工作（方法的执行），因为我尝试通过打印 N1、N2 值来弄清楚发生了什么，但仍然无法理解，也无法弄清楚 F1 是如何工作的F2 存储系列的总和。

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

Answer 1

查询 0 和 1 非常简单，因为您已将它们定义为事实。如果您要求第 0 个号码：

   ?- fib(X,0).

Prolog 尝试第一个规则并成功匹配 0 与第二个参数。然后 X 与 0 统一。由于 X 是一个变量，统一简单地包括用 0 替换 X。这产生了第一个解决方案：

   ?- fib(X,0).
X = 0 ?

如果您输入 ; Prolog 搜索进一步的解决方案：

   ?- fib(X,0).
X = 0 ?;

第二条规则不匹配，因为1=0无法统一。所以 Prolog 尝试第三条规则。规则头部的N与0成功统一。但是规则主体中的第一个目标失败了，因为 0>1 不成立。所以第三条规则失败了。没有更多的规则可以尝试，因此 Prolog 得出结论，没有更多的解决方案：

X = 0 ?;
no

对第一个数字的查询几乎相同，唯一的区别是这次围绕第一条规则失败而第二条规则成功。把那个作为一个练习来想一想。现在来看一个更有趣的案例：

   ?- fib(X,2).

Prolog 尝试了前两个规则但失败了，因为 0=2 和 1=2 都不能统一。然后Prolog尝试了第三条规则，成功统一了N=2。自 2>1 以来的第一个进球就成功了。第二个目标评估 N1=1。第三个目标评价N2=0。第四个目标递归调用

fib(F1,1)

这符合 fib/2 的第二条规则（见上文），因此替换 F1=1。从递归 Prolog 返回到第五个目标并递归调用

fib(F2,0)

如上所述，第一个规则成功，因此替换 F2=0。 Prolog 再次从递归返回到最后一个目标并计算 F=1。这会产生查询的第一个解决方案：

   ?- fib(X,2).
X = 1 ?

通过输入 ; 您要求进一步的解决方案：

   ?- fib(X,2).
X = 1 ? ;

所以 Prolog 回溯到第五个目标并试图为它找到进一步的解决方案但失败了（见上文）。然后 Prolog 回溯到第四个目标并试图为它找到进一步的解决方案但失败了。目标三、二和一也是如此。所以 Prolog 告诉你没有进一步的解决方案：

   ?- fib(X,2).
X = 1 ? ;
no

如果您想对此有所了解，请拿一张 sheet 纸并尝试查询 3 和 4。您可以使用 trace 检查您的结果，正如 @lurker 在评论。

Sum of Fibonacci series in ProLog program Execution