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

Größter gemeinsamer Teiler - funktional

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

Hintergrundwissen

$Fuerx,y>0gilt:$
$ggT(x,y):=x$
$ggT(x,y):=ggT(y,x)$
$ggT(x,y):=ggT(x,y-x)fuerx\le y$

Wir haben folgende funktionale Spezifikationen:

$ggt(x,y):=\{\begin{array}{cc}if(x\le 0)\vee (y\le 0)& thenggT(x,y)else\\ ifx==y& thenxelse\\ ifx>y& thenggT(y,x)else\\ & ggT(x,y-x)\end{array}$

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\le 0$

$y\le 0$

$x==y$

Im Fall des Abbruchs wird eine Evaluierung oder Ausnahme angegeben.

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

1. $x,y>0,x\ge y$
2. $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.