prolog - Prolog，动态规划，斐波那契数列

Question

我应该先说这是一个我遇到问题的家庭作业问题，我不确定这里是否允许这种事情，但我不知道还能去哪里。这是我被问到的问题：

在这个问题的示例代码中，您可以看到一个斐波那契谓词fibSimple/2，它计算 X 的斐波那契，一个自然数。朴素递归解决方案的问题在于，您最终会多次重新计算相同的递归情况。请参阅此处以获取解释。

例如，计算 fib(5) 涉及计算 fib(2) 的解三个不同的时间。动态规划方法可以解决这个问题。本质上，它归结为从 fib(2) 开始，然后计算 fib(3)，然后是 fib(4) 等......直到达到 fib(X)。您可以将这些答案存储在一个列表中，并将 fib(X) 作为列表中的第一项。

您的基本案例如下所示：

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

请注意 fib(1) 定义为 [1,0] 的方式。fib(1) 确实是 1，但我们保留了先前答案的列表。

我们为什么要做这个？因为要计算 fib(X)，我们只需要计算 fib(X-1) 并将前两个元素加在一起，然后将它们插入到列表的前面。例如，从上面，很容易计算 fib(2,Ans)。在这种情况下，fib(2) 将是 [1,1,0]。那么 fib(3) 将是 [2,1,1,0]，fib(4) 将是 [3,2,1,1,0] 等等......

完成上述 fib/2 谓词 - 基本情况如上所示。您需要找出在基本案例之后处理递归的一行。

这是他们提供的示例代码

fibSimple(0,0). % fib of 0 is 0
fibSimple(1,1). % fib of 1 is 1
fibSimple(N,X) :- N>1,fibSimple(N-1,A), fibSimple(N-2,B), X is A+B.

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

我对此进行了几次尝试，虽然我相当肯定我的尝试最终会是无可救药的错误，但这是我最近尝试过的

fib(X,[fib(X-2)+fib(X-1) | _]).

我对此的推理是，如果你能得到最后 2 个的答案，并将它们加在一起，使它们成为列表的第一个或“头”，然后下划线代表其余部分。

我的两个问题是：

1）我不知道/认为这个下划线会做我想做的事情，并且迷失了从这里去哪里和

2)我什至不知道如何运行这个程序，因为fib\2谓词需要 2 个参数。例如，我想运行fib\2以找到 5 的斐波那契，我不知道将什么作为第二个参数。

标签： prologlogicfibonacci

Answer 1

因为这是家庭作业，所以我只会勾勒出解决方案——但它应该回答你提出的问题。

谓词与函数的不同之处在于它没有返回值。Prolog 只是告诉你它是否可以派生它 (*)。因此，如果您只是问是否fib(5)是真的，那么您能得到的最好的答案就是“是”。但是从 1 到 5 的斐波那契数是多少呢？这就是第二个参数的用武之地。要么你已经知道并检查：

?- fib(5, [5, 3, 2, 1, 1, 0]).
true ;                   <--- Prolog can derive this fact. With ; I see more solutions.
false                    <--- no, there are no other solutions

或者您将第二个参数保留为变量，Prolog 将告诉您该变量必须具有哪些值才能派生您的查询：

?- fib(5, X).
X = [5, 3, 2, 1, 1, 0] ;
false.

所以第二个参数包含你正在寻找的结果。

您还可以询问其他问题，例如fib(X,Y)“我们可以推导出哪些数字及其斐波那契宿主？” 或fib(X, [3 | _])“哪个数字计算斐波那契数 3？”。在第二种情况下，我们使用下划线表示列表的其余部分无关紧要。(2)

那么我们该怎么做fib(X,[fib(X-2)+fib(X-1) | _]).呢？如果我们将它添加到 0 和 1 的子句中，我们可以查询所有结果：

?- fib(X,Y).
X = 0,
Y = [1] ;    <-- first solution X = 0, Y = [1]
X = 1,
Y = [1, 0] ; <-- second solution X = 1, Y = [1, 0]
Y = [fib(X-2)+fib(X-1)|_2088]. <-- third solution

第三个解决方案只是说：以该术语开头的列表fib(X-2)+fib(X-1)是一个有效的解决方案（_2088只是一个不是您命名的变量）。但正如开头所说，这个词是不被评估的。通过定义 . 你会得到类似的结果fib(X, [quetzovercaotl(X-1) | _])。

与您类似，fibSimple您需要一个规则来告诉 Prolog 如何从它已经知道的事实中推导出新的事实。我已fibSimple为您重新格式化：

fibSimple(N,X) :-
  N>1,
  fibSimple(N-1,A),
  fibSimple(N-2,B),
  X is A+B.

这表示如果N > 1我们可以推导fibSimple(N-1,A)并且我们可以推导fibSimple(N-2,B)并且我们可以将 X 设置为 A + B 的结果，那么我们推导fibSimple(N, X)。与您所写内容的不同fibSimple(N-1,A)之处在于规则正文中。同样，该论点N-1没有得到评估。实际发生的是递归构造了术语3-1，并(3-1)-1)在使用查询调用时fib(3,X)。实际评估发生在算术谓词is和<中。例如，递归谓词在尝试评估时停止，(3-1)-1 > 1因为1>1它不为真。但是我们也没有达到基本情况，因为即使它们评估为相同的数字，fibSimple(1, 1)该术语(3-1)-1也不相同。1

这就是 Prolog 在简单实现中找不到斐波那契数 3 的原因：

?- fibSimple(3, X).
false.

算术评估由is谓词完成：查询X is (3-1) -1正好有解X = 1。(3)

所以fibSimple实际上必须看起来像这样：（4）

fibSimple(0,1).
fibSimple(1,1).
fibSimple(N,X) :-
    N>1,
    M1 is N -1,      % evaluate N - 1
    M2 is N -2,      % evaluate N - 2
    fibSimple(M1,A),
    fibSimple(M2,B),
    X is A+B.

因为fib您可以将其用作模板，您只需要一个递归调用，因为两者A都B在历史列表中。请注意子句的开头：如果X是新值，则它不能也是新的历史列表。例如，头部可以有形式fib(N, [X | Oldhistory])。

祝家庭作业好运！

(1) 这有点简化 - Prolog 通常会给你一个答案替换，告诉你查询中的变量有什么值。还有一些有限的方法可以处理不可推导性，但您在这里不需要。

(2) 如果您使用算术谓词is，>这两个查询将不适用于直接实现。处理这个问题的更具声明性的方式是算术约束。

(3) 为使该评估起作用， 的右侧is可能不包含变量。这是您需要 (2) 中的算术约束的地方。

(4) 或者，基本情况可以评估传递下来的算术项：

fibSimple(X, 0) :-
    0 is X.
fibSimple(X, 1) :-
    1 is X.
fibSimple(N,X) :-
    N>1,
    fibSimple(N-1,A),
    fibSimple(N-2,B),
    X is A+B.

但这效率较低，因为单个数字比术语 占用的空间少得多100000 - 1 - 1 -1 .... -1。