Zum Inhalt springen

Kurs:Algorithmen und Datenstrukturen/Vorlesung/Größter gemeinsamer Teiler funktional

Aus Wikiversity




Größter gemeinsamer Teiler - funktional

[Bearbeiten]

In folgendem Beispiel werden wir den größten gemeinsamen Teiler mit Hilfe eines funktionalen Algorithmus berechnen.

Hintergrundwissen

[Bearbeiten]




Wir haben folgende funktionale Spezifikationen:

Auswertung

[Bearbeiten]

Eine beispielhafte Auswertung sieht wie folgt aus:

Abbruchbedingungen und Rekursion

[Bearbeiten]

Der 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

[Bearbeiten]
public 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

[Bearbeiten]

Da 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.


R-0 Discussion R-3