Größter gemeinsamer Teiler - funktional

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

Hintergrundwissen

 $Fuer~x,y>0~gilt:$ 
 $ggT(x,y):=x$ 
 $ggT(x,y):=ggT(y,x)$ 
 $ggT(x,y):=ggT(x,y-x)~fuer~x\leq y$

Wir haben folgende funktionale Spezifikationen:

$ggt(x,y):=\left\{{\begin{array}{ll}if(x\leq 0)\lor (y\leq 0)&then~ggT(x,y)~else\\if~x==y&then~x~else\\if~x>y&then~ggT(y,x)~else\\&ggT(x,y-x)\end{array}}\right.$

Auswertung

Eine beispielhafte Auswertung sieht wie folgt aus:

$ggT(39,15)\to ggT(15,39)\to (15,24)$

\to ggT(15,9)~~\to (9,15)

\to ggT(9,6)~~~\to (6,9)

\to ggT(6,3)~~~\to (3,3)

\to 3

Abbruchbedingungen und Rekursion

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:

x\leq 0

y\leq 0

x==y

Im Fall des Abbruchs wird eine Evaluierung oder Ausnahme angegeben.

Bedingungen für rekursive Verwendung der Funktion, "einfachste" Rekursion zuerst

$x,y>0,~x\geq y$
$x,y>0,~y<x$

Im Fall der Rekursion wird eine Evaluierung angegeben.

Programm

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

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.