ggT mit Prolog

[Kiloui]

Hey,

ich hab hier folgende mögliche Lösung um den ggT mittels Prolog zu bestimmen:

ggt(A, B, C) :-gt(A, B, C), not(larger_gt(A, B, C)).

larger_gt(A, B, C) :-gt(A, B, C1), C1>C.

gt(A, B, C) :-t(A, C), t(B, C).

t( A, C ) : - zwischen(1, C, A), AmodC =:= 0.

zwischen(C, C, O).
zwischen(U, C, O) :-O>U, U1 isU+1, zwischen(U1, C, O).


kann mir jmd die letzten beiden Zeilen erklären !? Was bewirkt "zwischen(C, C, O)."
Und wieso läßt man in der untersten Zeile das U gegen O laufen ?

 

[s4ms3milia]

"zwischen(C, C, O)." ist der rekursive Abschluss.

Quasi das Abbruchkriterium für den rekursiven Aufruf: "zwischen(U1, C, O)".

Den Rest schaue ich mir gleich mal an, Prolog ist etwas lange her

 

[Kiloui]

So weit schonmal danke.

Sowas wie "Abbruchbedingung" habe ich mir bei der vorletzten zeile schon gedacht Prolog is völlig neu für mich....

Hoffe du kriegst die letzte Zeile auch noch hin

 

[s4ms3milia]

Also, es ist im grunde ganz einfach !

Wir schauen nach ob die 2 zwischen der 1 und der 3 liegt!

Das sieht jetzt auf den ersten Blick etwas kompliziert aus, aber da wirst du, wenn du dich mit Prolog beschäftigst nicht drum herum kommen.

Wenn du 'trace.' in die Konsole eingibst, kannst du genau nachvollziehen, was deine Programme bewirken.

Die Idee ist, die Zahl1 solange um 1 zu erhöhen und mit der Testzahl zu vergleichen, bis

a) Die Testzahl gleich der (erhöhten Zahl1 ist) oder
b) Zahl1 > Zahl1 nicht mehr "true" ergibt und das Programm somit mit false abbricht.

zwischen(Testzahl, Testzahl, Zahl2).
zwischen(Zahl1, Testzahl, Zahl2) :-
	Zahl2 > Zahl1, 
	NeueZahl1 is Zahl1 + 1, 
	zwischen(NeueZahl1, Testzahö, Zahl2).

 zwischen(1,[COLOR="Red"]2[/COLOR],3).
   Call: (6) zwischen(1, [COLOR="Red"]2[/COLOR], 3) ? creep
^  Call: (7) 3>1 ? creep
^  Exit: (7) 3>1 ? creep
^  Call: (7) _G434 is 1+1 ? creep
^  Exit: (7) 2 is 1+1 ? creep
   Call: (7) zwischen(2, [COLOR="Red"]2[/COLOR], 3) ? creep [COLOR="Lime"]<-- Abbruchbedingung erreicht![/COLOR]
   Exit: (7) zwischen(2, [COLOR="Red"]2[/COLOR], 3) ? creep
   Exit: (6) zwischen(1, [COLOR="Red"]2[/COLOR], 3) ? creep
true .

Durch die Abbruchbedingung (wenn Zahl1 gleich der Testzahl ist) findet kein rekursiver Aufruf mehr statt, die Rekursion wurde erfolgreich beendet.

Du kannst das Programm auch teilweise unterspezifiziert (mit Variablen im Aufruf) aufrufen:

[trace]  ?- zwischen(1,X,3).
   Call: (6) zwischen(1, _G369, 3) ? creep
   Exit: (6) zwischen(1, 1, 3) ? creep
X = 1 ;
   Redo: (6) zwischen(1, _G369, 3) ? creep
^  Call: (7) 3>1 ? creep
^  Exit: (7) 3>1 ? creep
^  Call: (7) _G446 is 1+1 ? creep
^  Exit: (7) 2 is 1+1 ? creep
   Call: (7) zwischen(2, _G369, 3) ? creep
   Exit: (7) zwischen(2, 2, 3) ? creep
   Exit: (6) zwischen(1, 2, 3) ? creep
X = 2 ;
   Redo: (7) zwischen(2, _G369, 3) ? creep
^  Call: (8) 3>2 ? creep
^  Exit: (8) 3>2 ? creep
^  Call: (8) _G449 is 2+1 ? creep
^  Exit: (8) 3 is 2+1 ? creep
   Call: (8) zwischen(3, _G369, 3) ? creep
   Exit: (8) zwischen(3, 3, 3) ? creep
   Exit: (7) zwischen(2, 3, 3) ? creep
   Exit: (6) zwischen(1, 3, 3) ? creep
X = 3 ;
   Redo: (8) zwischen(3, _G369, 3) ? creep
^  Call: (9) 3>3 ? creep
^  Fail: (9) 3>3 ? creep
   Fail: (8) zwischen(3, _G369, 3) ? creep
   Fail: (7) zwischen(2, _G369, 3) ? creep
   Fail: (6) zwischen(1, _G369, 3) ? creep
false.

X = 1,2,3 liegt also zwischen 1 und 3 .

Also immer schön mit trace schauen, was da eigentlich so passiert .

Viel spaß noch!

Es gibt übrigens 2 Arten von Rekursion in Prolog, es lohnt sich da noch weiter zu recherchieren:
Aufsteigende & Absteigende Rekursion (Endrekursion)

 

[Kiloui]

Ah sehr gut jetzt hab ich es verstanden