Berechnen des Ggt und kgV in C#

In  diesem Post möchte ich zeigen wie der größte gemeinsame Teiler (Ggt) und der kleinste gemeinsame Teiler (kgV) zweier Zahlen berechnet werden kann. Außerdem werde ich zeigen wie man die Berechnung des Ggt und kgV in C# implementiert. Ihr könnt euch das ganze im Video ansehen und dann den Code kopieren oder ihr lest euch zuerst die schriftliche Variante durch. Viel Spaß!

Der Größte gemeinsame Teiler (Ggt) ist schnell erklärt. Nehmen wir zwei zahlen x und y die nicht Teilerfremd sind.

x = 21
y = 14

 

Die Teiler von x sind {1, 3, 7, 21}. Während y die Teilermenge {1, 2, 7, 14} hat. Wie man unschwer erkennen kann ist 7 der größte Teiler den x und y gemein haben.

Benannt nach dem griechischen Mathematiker Euklid lässt sich der Ggt zweier Zahlen mit dem Euklidischen Algorithmus berechnen.

Wir ändern x und y:

x = 30
y = 21
//x mod y
30%21=9
//Das ergebnis r ist nicht 0 also wird weiter gerechnet
x=y //x= 21
y=r //y = 9

//x mod y
21%9=3
//Das ergebnis r ist nicht 0 also wird weiter gerechnet
x=y //x= 9
y=r //y =3

//x mod y
9%3=0
//Die 0 ist das Abbruchkriterium
//für den Algorithmus und der Ggt(30,21)=y=3
Nun implementieren wir eine Methode berechneGgt(). Diese methode bekommt zwei Integer als Parameter, und gibt einen Integer als Rückgabewert, den Ggt.
public int berechneGgt(int _zahl1, int _zahl2)
{
int zahl1 = _zahl1;
int zahl2 = _zahl2;
//Diese Variable wird bei Wertzuweisungen zwischen den Zahlen benutzt
int temp = 0;
//Der Rückgabewert zweier gegebener Zahlen.
int ggt = 0;//Solange der Modulo der zwei zahlen nicht 0 ist,
//werden Zuweisungen entsprechend demEuklidischen Algorithmus ausgeführt.
while (zahl1 % zahl2 != 0)
{
temp = zahl1 % zahl2;
zahl1 = zahl2;
zahl2 = temp;
}

ggt = zahl2;

return ggt;

}

Nun zum kgV, wir nehmen die Zahlen:

x = 4
y = 7

Vielfache der Zahl x wären {4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56…} von y {7, 14, 21, 28, 35, 42, 49, 56, 63 , 70, 77…}. Wie man sieht sind 28 und 56 gemeinsame Vielfache von 4 und 7. Es ist auch ersichtlich, dass 28 das kleinste gemeinsame Vielfache ist. Es gibt mehrere Methoden den kgV zweier Zahlen zu berechnen, z.B. die Primfaktorzerlegung. Das wäre aber viel zu umständlich zu implementieren, also benutzen wir folgenden Satz.

x * y = Ggt(x,y) * kgV(x,y)

Das bedeutet, dass mit dem Ggt(x,y) den wir bereits berechnen können ohne Umstände auch den kgV(x,y) berechnen können. Dazu Teilen wir das Produkt von x und y durch ihren Ggt.

//Die Methode berechneKgV() bedient sich der
//berechneGgt()-Methode.
public int berechneKgV(int zahl1, int zahl2)
        {
            return (zahl1 * zahl2) / berechneGgt(zahl1,zahl2);
        }
That’s it folks!
Advertisements
Kurzmitteilung | Dieser Beitrag wurde unter .NET, Algorithmen, Beispiel, Beispiel, c#, Mathematik, Modulo, Modulo, Programmierung abgelegt und mit , , , , , , , verschlagwortet. Setze ein Lesezeichen auf den Permalink.

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden /  Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden /  Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden /  Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden /  Ändern )

Verbinde mit %s