Prolog中两个整数的递归定义函数（分区函数）

Question

我发誓这不是一个家庭作业问题。几十年来我没有上过课。曾几何时我想出了分区功能，一个可爱的递推公式：

 /0 (k > n) 
f(k, n) { 1 (k = n) 
     \ p(k, n-k)+p(k+1, n) (k < n) 

我想尝试在序言中表示这一点。这是关于据我可以得到：

partition(N, N, 1) :- !. %% http://stackoverflow.com/a/9582409 

partition(K, N, 0) :- K > N. 

partition(K, N, A+B) :- 
X is K+1, 
Y is N-K, 
partition(X, N, A), 
partition(K, Y, B). 

?- partition(1, 10, X).给了我这样的：

X = 1 + 0 + 0 + 0 + 0 + 1 +（1 + 0 + 0）+ （1 + 0 + 0 + 0 +（1 + 0））+（1 + 0 + 0 + 0 + 1 +（1 + 0 + 0）+（1 + 0 + 0 + 1 +（1 + 0 + 1 ）））+（1 + 0 + 0 + 0 + 0 +（1 + 0）+（1 + 0 + 0 + 1）+（1 + 0 + 0 + 0 +（1 + 0）+（1 + 0 +0+（1 + 0）））+（1 + 0 + 0 + 0 + 1 +（1 + 0 + 0）+（1 + 0 + 0 + 1 +（1 + 0 + 1））+（1 + 0 + 0 + 0 +（1 + 0）+（1 + 0 + 0 +（1 + 0））+（1 + 0 + 0 + 1 +（1 + 0 + 1）+（1 + 0 + 0 +（1 + 0）+（1 + 0 + 1 +（1 + 0 +（1 + 1））））））））？

有一件令人欣慰的事情是，在上述表达式（？）中的确有42个。我希望X=42.注意问号。是的，有更多的比赛（显然无限多）。第二个是：

X = 1 + 0 + 0 + 0 + 0 + 1 +（1 + 0 + 0）+（1 + 0 + 0 + 0 +（1 + 0））+ 1 + 0 + 0 + 0 + 1 +（1 + 0 + 0）+（1 + 0 + 0 + 1 +（1 + 0 + 1）））+（1 + 0 + 0 + 0 + 0 +（1 0）+（1 + 0 + 0 + 1）+（1 + 0 + 0 + 0 +（1 + 0）+（1 + 0 + 0 +（1 + 0）））+（1 + 0 + 0 + 0 + 1 +（1 + 0 + 0）+（1 + 0 + 0 + 1 +（1 + 0 + 1））+（1 + 0 + 0 + 0 +（1 + 0）+（1 + 0 +0+（1 + 0））+（1 + 0 + 0 + 1 +（1 + 0 + 1）+（1 + 0 + 0 +（1 + 0）+（1 + 0 + 1 +（1 + （0 + 0）+（1 + 1））））））））？

Answer 1

我发誓这不是一个家庭作业问题。几十年来我没有上过课。

冷静下来，哪怕是家庭作业，也有寻求帮助没有问题给定你做了合理的努力（合理当然是主观的，但我认为这是确定的问题），自己和它更多的是你的实现有一个特定的问题:)。

您的方法存在的问题是，您 - 很多人 - 认为Prolog将语义附加到仿函数。 对于Prolog +不是加号，也不是加在一起的东西,+只是一个符号，它并不估计它。

然而，有一个谓词可以评估表达式树，并使用大多数人认同的“语义”。这是谓词is/2。所以，现在你可以简单地将它修改为：

 
partition(K, N, C) :- 
    X is K+1, 
    Y is N-K, 
    partition(X, N, A), 
    partition(K, Y, B), 
    C is A+B. 

是的，有更多的比赛（显然无限多）。

那是因为你的最后一句话，没有后卫，说K < N，换句话说序言将走回头路且不论如何K和N之间的相互关系，它可以随时拿起最后条款（除K == N因为您放置了剪辑（!））。

您最好使用“后卫”作为您的最后一个句子，否则在回溯时可以调用K < N。因此，完整的代码序列将改为类似：

 
partition(N, N, 1) :- !. %% http://stackoverflow.com/a/9582409 

partition(K, N, 0) :- K > N. 

partition(K, N, C) :- 
    K < N, 
    X is K+1, 
    Y is N-K, 
    partition(X, N, A), 
    partition(K, Y, B), 
    C is A+B. 

注意，没有什么特别有is/2：它只是一个断言：你可以有is(C,A+B)称为它。它只是以这样的方式定义，它也可以用作中缀运算符。

在给定的条款，查询得到：

?- partition(1, 10, X). 
X = 42 ; 
false.