Programm für das Auffinden von Gcd in Prolog

Ich zu schreiben versucht, einen code in Prolog für die Suche nach GCD (ohne modulo)
kann mir jemand sagen, was ist Los mit diesem Programm?

gcd(X,Y,Z):- X>=Y, X1=X-Y, gcd(X1,Y,Z).
gcd(X,Y,Z):- X<Y, X1=Y- X, gcd(X1,X,Z).
gcd(0,X,X):- X>0.

InformationsquelleAutor Ohad | 2014-03-17

  1. 4

    Warum die ursprüngliche Implementierung nicht funktioniert, gibt es zwei Gründe:

    Das Prädikat =/2 ist für die Vereinigung, nicht das arithmetische Zuweisung

    Den Ausdruck X1 = X - Y nicht subtrahieren Y aus X und speichern das Ergebnis in X1. Vielmehr vereint X1 mit dem Begriff -(X,Y). Wenn, zum Beispiel, X=5 und Y=3, dann das Ergebnis wäre, X1=5-3, nicht X1=2. Die Lösung ist die Verwendung is/2 was weist bewertet arithmetische Ausdrücke: X1 is X - Y.

    Andere Prädikate, neben dem base-case-Prädikat, erfolgreich entsprechen die base-case -

    Die Klausel gcd(0,X,X) :- X > 0. ist eine vernünftige Basis, aber es ist nie versucht, da die zweite Klausel (gcd(X,Y,Z):- X<Y,...) immer erfolgreich den gleichen Bedingungen zuerst, was zu einer unendlichen Rekursion und ein stack-überlauf.

    Einen Weg, um dies zu beheben, bewegen Sie den base case auf die erste Klausel, und verwenden Sie einen cut zu vermeiden, backtracking, nachdem es erfolgreich ausgeführt:

    gcd(0, X, X):- X > 0, !.
gcd(X, Y, Z):- X >= Y, X1 is X-Y, gcd(X1,Y,Z).
gcd(X, Y, Z):- X < Y, X1 is Y-X, gcd(X1,X,Z).

    Nun wird es funktionieren:

    | ?- gcd(10,6,X).

X = 2 ? ;

(1 ms) no
| ?- gcd(10,5,X).

X = 5 ? ;

no

    (HINWEIS: die hier "Nein" bedeutet, dass keine weiteren Lösungen gefunden, nach der Suche nach die erste)

    NACHTRAG

    Gibt es noch ein paar verbleibenden "Lücken" in der oben genannten Umsetzung. Einer ist, dass es nicht handhaben gcd(0, 0, R) ordnungsgemäß (es überläuft). Zweitens, es muss nicht mit negativen Werten. Eine mögliche Lösung wäre zu erarbeiten, in diesen Fällen:

    gcd(X, Y, Z) :-
    X < 0, !,
    gcd(-X, Y, Z).
gcd(X, Y, Z) :-
    Y < 0, !,
    gcd(X, -Y, Z).
gcd(X, 0, X) :- X > 0.
gcd(0, Y, Y) :- Y > 0.
gcd(X, Y, Z) :-
    X > Y, Y > 0,
    X1 is X - Y,
    gcd(Y, X1, Z).
gcd(X, Y, Z) :-
    X =< Y, X > 0,
    Y1 is Y - X,
    gcd(X, Y1, Z).
    Hervorragende Erklärung! 🙂

    InformationsquelleAutor lurker

  2. 1

    Versuchen Sie Folgendes statt:

    gcd(X, 0, X):- !.
gcd(0, X, X):- !.
gcd(X, Y, D):- X =< Y, !, Z is Y - X, gcd(X, Z, D).
gcd(X, Y, D):- gcd(Y, X, D).

    Entnommen rosettacode.org auf der GCD in allen Arten von Sprachen.

    Es immer noch nicht produzieren die gcd...
    Irgendwie ist die Ausgabe von gcd(10,5,X) ist falsch.. in Ihrem Programm und in meinem Programm (nach dem hinzufügen des "ist").. keine Ahnung warum ?
    Sorry, siehe meine aktualisierte Antwort. Ich versuchte es auf dieser Seite
    Es ist richtig.. haben Sie eine Idee, warum mein original Programm ist falsch ?( außer der "ist" - Betrieb).

    InformationsquelleAutor helb

  3. 1

    Prolog-code für GCD

    gcd(X,Y,G) :- X=Y, G=X.
gcd(X,Y,G) :- X<Y, Y1 is Y-X, gcd(X,Y1,G).
gcd(X,Y,G) :- X>Y ,gcd(Y,X,G).

?- gcd(24,16,G).
G = 8

    InformationsquelleAutor Dvir Arad

  4. 0
    gcd(A,B,X):- B=0,X=A.

gcd(A,B,X):- A>B, gcd(B, A, X).

gcd(A,B,X) :- A<B, T is B mod A, gcd(A, T, X).
    Bitte, erklären Sie immer den code.

    InformationsquelleAutor rashedcs

  5. 0

    prolog Antwort ist:-

    gcd(X,0,X).
gcd(X,Y,R):-
Y>0,
X1 is X mod Y,
gcd(Y,X1,R).

    InformationsquelleAutor AMIT KUMAR

Schreibe einen Kommentar