Euklidischer Algorithmus
Suche nach dem größten gemeinsamen Teiler (GGT)
- Euklid (klassisch)
- Euklid (klassisch-rekursiv)
- Euklid (modern-rekursiv)
Pseudocode
Funktion EuklidKlassisch(a, b)
IF a := 0 THEN
Ergebnis := b
ELSE
WHILE b ungleich 0 DO
IF a > b THEN
a := a - b
ELSE
b := b - a
Ergebnis := a
Pseudocode
Funktion EuklidKlassischRekursiv(a,b)
IF b := 0 THEN
Ergebnis := a
ELSE
IF a := 0 THEN
Ergebnis := b
ELSE
IF a > b THEN
Ergebnis := EuklidKlassischRekursiv(a - b, b)
ELSE
Ergebnis := EuklidKlassischRekursiv(a, b - a)
Pseudocode
Funktion EuklidModern(a,b)
IF b := 0 THEN
Ergebnis := a
ELSE
Ergebnis := EuklidModern(b, a % b)
- Euklid (klassisch)
- Euklid (klassisch-rekursiv)
- Euklid (modern-rekursiv)
C#
static int EuklidKlassisch(int a, int b)
{
if (a == 0)
return b;
else
{
while (b != 0)
{
if (a > b)
a = a - b;
else
b = b - a;
}
}
return a;
}
C#
static int EuklidKlassischRekursiv(int a, int b)
{
if (b == 0)
return a;
else
{
if (a == 0)
return b;
else
{
if (a > b)
return EuklidKlassischRekursiv(a - b, b);
else
return EuklidKlassischRekursiv(a, b - a);
}
}
}
C#
static int EuklidModern(int a, int b)
{
if (b == 0)
{
return a;
}
else return EuklidModern(b, a % b);
}