Kurs:Algorithmen und Datenstrukturen/Vorlesung/Größter gemeinsamer Teiler funktional
Größter gemeinsamer Teiler - funktional
BearbeitenIn folgendem Beispiel werden wir den größten gemeinsamen Teiler mit Hilfe eines funktionalen Algorithmus berechnen.
Hintergrundwissen
BearbeitenWir haben folgende funktionale Spezifikationen:
Auswertung
BearbeitenEine beispielhafte Auswertung sieht wie folgt aus:
Abbruchbedingungen und Rekursion
BearbeitenDer ggT lässt sich nur korrekt berechnen, wenn positive Eingaben gemacht werden. Bei negativen Eingaben ist der ggT undefiniert und der Algorithmus terminiert nicht.
- Abbruchbedingungen:
Im Fall des Abbruchs wird eine Evaluierung oder Ausnahme angegeben.
- Bedingungen für rekursive Verwendung der Funktion, "einfachste" Rekursion zuerst
Im Fall der Rekursion wird eine Evaluierung angegeben.
Programm
Bearbeitenpublic static int ggT(int x, int y)
{
if ((x <= 0) || (y <= 0))
throw new ArithmeticError(“negative Daten bei ggt“));
else if (x==y) then return x;
else
if x > y then return ggT(y,x);
else return ggT(x,y-x);
}
Literatur
BearbeitenDa die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 3.2.6 zu finden.