歐幾里德遞歸算法

好吧，我知道這確實是一個愚蠢的問題，但我無法得到它。有一個任務，我應該找到一個遞歸算法 Euclid（gcd）。我已經做了一個案例，在這裏：歐幾里德遞歸算法

nondeterm nod (integer,integer,integer) 
CLAUSES 
nod (X,0,X):- !. 
nod (0,X,X):- !. 
nod (X,0,X):-X>0. 
nod (X,Y,G):-Y>0, Z = X mod Y, nod (Y,Z,G).

我需要做的另一種情況下，如果遞歸從х0，beginnig時習則函數計數曦+ 1調用。它應該是這樣的：

PREDICATES 
nondeterm nod (integer,integer,integer) 
nondeterm nod1 (integer,integer,integer,integer,integer)  
CLAUSES 
nod(X,Y,Z):- nod1(X,Y,Z,0,0). 
nod1 (X,Y,Z,X,Y):- Otvet = Z, write("Otvet=", Otvet, "\n"), !. 
nod1 (X,Y,X,Y):- nod1 (X,Y,X,Y). 
nod1 (X,Y,Z,X1,Y1):- 
       X1>Y1, X>0, Y>0, 
       Y2 = X1 mod Y1, 
       X2 = Y1, 
       nod1(X,Y,Z,X2,Y2).

但它不起作用。請幫助我。

來源

2012-04-08 eeeee

爲什麼不和？似乎對我來說是確定性的 – CapelliC 2012-04-08 08:13:45

對不起，我不明白你的問題。 'Xi + 1'在哪裏？在你的第一個代碼框中，'nod（X，0，X）： - ！。'與'nod（X，0，X）衝突： - X> 0。第二個將永遠不會被調用。這個規則是無用的'nod1（X，Y，X，Y）： - nod1（X，Y，X，Y）.'並且如果調用則會循環。 – CapelliC 2012-04-08 08:26:55

好吧......我想因爲我需要找到點頭的結果。我錯了嗎？ – eeeee 2012-04-08 08:44:54

以下代碼適用於我。請注意，使用 REM的，但我猜你也可以使用MOD：

% sys_gcd(+Integer, +Integer, -Integer) 
sys_gcd(X, 0, X) :- !. 
sys_gcd(X, Y, Z) :- 
    H is X rem Y, 
    sys_gcd(Y, H, Z).

這裏有一些例子與SWI-Prolog的運行：

?- sys_gcd(20,30,X). 
X = 10. 
?- sys_gcd(-20,30,X). 
X = 10. 
?- sys_gcd(20,-30,X). 
X = -10. 
?- sys_gcd(-20,-30,X). 
X = -10.

如果你想要的結果的一個特殊標誌，你需要圍繞它的附加代碼。

再見

來源

2015-08-18 09:24:55

歐幾里德遞歸算法

回答

相關問題