Prolog，动态编程，斐波那契系列 [英] Prolog, Dynamic Programming, Fibonacci series

问题描述

首先，我要说这是我遇到的家庭作业问题，我不确定在这里是否允许这种事情，但我不知道该怎么办.这是我被问到的问题:

I should preface this by saying this is a homework problem that I am having issues with, and Im not sure if that sort of thing is allowed around here, but I dont know where else to turn to. This is the question I've been asked:

在该问题的示例代码中，您可以看到斐波那契谓词fibSimple/2，该谓词计算X的斐波那契数(自然数).天真的递归解决方案的问题在于，您最终会多次重新计算相同的递归案例.请参阅此处以获取解释.

In the sample code for this question, you can see a Fibonacci predicate fibSimple/2 which calculates the Fibonacci of X, a natural number. The problem with the naive recursive solution, is that you end up recalculating the same recursive case several times. See here for an explanation.

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

For example, working out the fib(5) involves working out the solution for fib(2) three separate times. A Dynamic Programming approach can solve this problem. Essentially, it boils down to starting with fib(2), then calculating fib(3), then fib(4) etc.... until you reach fib(X). You can store these answers in a list, with fib(X) ending up as the first item in the list.

您的基本案例如下:

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

请注意，将fib(1)定义为[1,0]的方式. fib(1)实际上是1，但我们保留了以前的答案列表.

Note the way that fib(1) is defined as [1,0]. fib(1) is really 1 but we are keeping a list of previous answers.

我们为什么要这样做?因为要计算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]等.

Why do we do this? Because to calculate fib(X), we just have to calculate fib(X-1) and add the first two elements together and insert them at the front of the list. For example, from the above, it is easy to calculate fib(2,Ans). fib(2) in this case would be [1,1,0]. Then fib(3) would be [2,1,1,0], fib(4) would be [3,2,1,1,0] etc....

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

Complete the fib/2 predicate as outlined above - the base cases are shown above. You need to figure out the one line that goes after the base cases to handle the recursion.

这是他们提供的示例代码

This is the sample code they provided

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]).

我已经对此进行了几次尝试，虽然我可以肯定我的尝试最终会以绝望的错误失败，但这是我最近尝试过的事情

I've had a few attempts at this, and while I'm fairly certain my attempt will end up being hopelessly wrong, this is what I have most recently tried

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

我这样做的原因是，如果您可以得到最后2个的答案，并将它们加在一起，使它们成为列表的第一个或头"，然后用下划线表示其余部分.

My reasoning to this is that if you can get the answer to the last 2, and add them together making them the first or "head" of the list, and then the underscore representing the rest.

我的2个问题是:

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

1) I don't know/think this underscore will do what I want it to do, and am lost in where to go from here and

2) 我不知道如何运行该程序，因为fib\2谓词需要2个参数.并举例说，我想运行fib\2来找到5的斐波那契，但我不知道要把什么作为第二个参数.

2) I don't know how to even run this program as the fib\2 predicate requires 2 parameters. And lets say for example I wanted to run fib\2 to find the fibonacci of 5, I would not know what to put as the 2nd parameter.

推荐答案

因为这是家庭作业，所以我只会画出解决方案-但它应该回答您提出的问题.

Because this is homework I will only sketch the solution - but it should answer the questions you asked.

谓词与函数的不同之处在于它没有返回值. Prolog只是告诉您它是否可以派生(*).因此，如果您只是问fib(5)是否为真，则可获得的最佳结果是是".但是从1到5的斐波那契数是多少呢?那是第二个参数出现的地方.您已经知道并检查:

A predicate differs from a function in that it has no return value. Prolog just tells you if it can derive it (*). So if you just ask if fib(5) is true the best you can get is "yes". But what are the Fibonacci numbers from 1 to 5 then? That's where the second argument comes in. Either you already know and check:

?- 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会告诉您该变量必须具有哪些值，这样它才能派生您的查询:

Or you leave the second argument as a variable and Prolog will tell you what values that variable must have such that it can derive your query:

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

第二个参数包含您要查找的结果.

So the second argument contains the result you are looking for.

您还可以询问其他查询，例如fib(X,Y)我们可以得出哪些数字及其斐波那契式病房?"或fib(X, [3 | _])哪个数字计算斐波那契数3?".在第二种情况下，我们使用下划线表示列表的其余部分无关紧要. (2)

You can also ask the other queries like fib(X,Y) "which numbers and their fibonacci hostories can we derive?" or fib(X, [3 | _]) "which number computes the the fibonacci number 3?". In the second case, we used the underscore to say that the rest of the list does not matter. (2)

那么我们如何使用fib(X,[fib(X-2)+fib(X-1) | _]).?如果我们将其添加到0和1的子句中，则可以查询所有结果:

So what do we do with fib(X,[fib(X-2)+fib(X-1) | _]).? If we add it to the clauses for 0 and 1 you were given we can just query all results:

?- 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) | _])，您将获得类似的结果.

The third solution just says: a list that begins with the term fib(X-2)+fib(X-1) is a valid solution (the _2088 as just a variable that was not named by you). But as mentioned in the beginning, this term is not evaluated. You would get similar results by defining fib(X, [quetzovercaotl(X-1) | _]).

与fibSimple类似，您需要一条规则来告诉Prolog如何从已经知道的事实中得出新事实.我为您重新格式化了fibSimple:

So similar to fibSimple you need a rule that tells Prolog how to derive new facts from facts it already knows. I have reformatted fibSimple for you:

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求值.实际发生的情况是，递归在使用查询fib(3,X)进行调用时会构造术语3-1和(3-1)-1).实际评估发生在算术谓词is和<中.例如，递归谓词在尝试评估(3-1)-1 > 1时停止，因为1>1不是true.但是，我们也不会使用基本情况fibSimple(1, 1)，因为术语(3-1)-1与1是不同的，即使它们的值相同.

This says if N > 1 and we can derive fibSimple(N-1,A) and we can derive fibSimple(N-2,B) and we can set X to the result of A + B, then we derive fibSimple(N, X). The difference to what you wrote is that fibSimple(N-1,A) occurs in the body of the rule. Again the argument N-1 does not get evaluated. What actually happens is that the recursion constructs the terms 3-1 and (3-1)-1) when called with the query fib(3,X). The actual evaluation happens in the arithmetic predicates is and <. For example, the recursive predicate stops when it tries to evaluate (3-1)-1 > 1 because 1>1 is not true. But we also do not hit the base case fibSimple(1, 1) because the term (3-1)-1 is not the same as 1 even though they evaluate to the same number.

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

This is the reason why Prolog does not find the Fibonacci number of 3 in the simple implementation:

?- fibSimple(3, X).
false.

算术运算由is谓词完成:查询X is (3-1) -1完全具有解决方案X = 1. (3)

The arithmetic evaluation is done by the is predicate: the query X is (3-1) -1 has exactly the solution X = 1. (3)

所以fibSimple实际上必须看起来像这样:(4)

So fibSimple must actually look like this: (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]).

For fib you can use this as a template where you only need one recursive call because both A and B are in the history list. Be careful with the head of your clause: if X is the new value it can not also be the new history list. For example, the head could have the form fib(N, [X | Oldhistory]).

祝你功课顺利！

(1)这有点简化-Prolog通常会为您提供答案替换，告诉您查询中的变量具有哪些值.还有一些处理不可导数的有限方法，但是您在这里不需要.

(1) This is a little simplified - Prolog will usually give you an answer substitution that tells you what values the variables in your query have. There are also some limited ways to deal with non-derivability but you don't need that here.

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

(2) If you use the arithmetic predicates is and > these two queries will not work with the straightforward implementation. The more declarative way of dealing with this is arithmetic constraints.

(3)为了使此评估有效，is的右侧可能不包含变量.这是您需要(2)中的算术约束的地方.

(3) For this evaluation to work, the right hand side of is may not contain variables. This is where you would need the arithmetic constraints from (2).

(4)或者，基本案例可以评估向下传递的算术项:

(4) Alternatively, the base cases could evaluate the arithmetic terms that were passed down:

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小得多.

But this is less efficient because a single number takes much less space than the term 100000 - 1 - 1 -1 .... -1.

这篇关于Prolog，动态编程，斐波那契系列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！