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.