Sprache: C#
Berechnet den größten gemeinsamen Teiler zweier Zahlen.
public static int ggT( int n, int m )
{
return n == m ? n : n<m ? ggT( n, m-n ) : ggT( n-m, m );
}public static int ggT( int n, int m )
{
return n == m ? n : n<m ? ggT( n, m-n ) : ggT( n-m, m );
}
Alte URL:
/snippet/groessten-gemeinsamen-teiler-berechnen/192
Sieht wirklich gut aus, aber nicht universell. In einem ungünstigen Fall bekommt man „stack overflow exception“. Beispiel: 10 und 10000000. 😉
Hier wird auf Rekursion zurückgegriffen, was bei großen Zahlen sehr lahmend ist. Mit einer iterativen Methode wie der folgenden erhält man bei deinen Zahlen keinen Overflow, Vladimir:
http://dotnet-snippets.de/dns/groessten-gemeinsamen-teiler-iterativ-ermitteln-SID1361.aspx
ich habe folgenden Code dafür benutzt.
Und damit ich garantiert ein ergebnis bekomme, habe ich dafür gesorg, dass bei einem negativen Zähler in einem Bruch der Zähler in der Funktion einmal mit -1 multipliziert wird.
Sonst hängt er sich auf
[code] public int ggT(int a, int b)
{
int functionReturnValue = 0;
if (a < 0) { a = a * (-1); } while (b > 0)
{
functionReturnValue = a % b;
a = b;
b = functionReturnValue;
}
return a;
}[/code]