ggT mit Prolog

Kiloui

Hey,

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

Code

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 ?

The User

Code

ggt(A, B, C) :- C is ggt(B, A mod B, C).
ggt(A, 0, C) :- C is A.
ggt(0, 0, C) :- C is 0.

Das sieht für mich wesentlich einfacher und klarer aus...

Kiloui

Zitat von The User
Code
ggt(A, B, C) :- C is ggt(B, A mod B, C).
ggt(A, 0, C) :- C is A.
ggt(0, 0, C) :- C is 0.
Das sieht für mich wesentlich einfacher und klarer aus...

hey danke für deine Antwort
Aber es geht mir wirklich nur speziell um diese mögliche Implementierung und darum die letzten beiden Zeilen zu verstehen.
Deine rekursive Lösung ist an sich besser ich weiß

The User

Es gibt nur rekursive Lösungen in Prolog.
Und auch die obige Lösung ist rekursiv, allerdings scheint er da eben alle Werte auszuprobieren und dann den größten zu nehmen, es ist einfach nur Schrott.

So stimmt es übrigens:

Code

#!/usr/bin/pl -s
ggT(0, 0, 0).
ggT(A, 0, A).
ggT(0, B, B).
ggT(A, B, C) :- ggT(B, AmodB, C).

Unregistriert

Hä?

Eine bessere Lösung bringt mich aber nicht weiter.
Es geht mir wie gesagt darum die letzten beiden Zeilen aus meinem Code zu verstehen und nicht darum den ggT möglichst effizient zu finden.

The User

Hab ich doch angedeutet: Der fängt mit U = 1 an und geht dann von unten nach oben durch und wählt den größten gemeinsamen Teiler... Das zwischen sorgt einfach dafür, dass alle Werte ausprobiert werden...

Tags