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




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
  1.  
  2.  

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.