[C++] Kleinstes gemeinsames Vielfaches (kgV) und größter gemeinsamer Teiler (ggT)

Wenn man mit C/C++ ein Programm schreiben will (oder muss ;)), das den ggT (größter gemeinsamer Teiler) berechnet, kann man diese Funktion als Vorlange verwenden:

(Algorithmus in C)

int ggT(int zahl1, int zahl2)
{
  if(zahl2 == 0)
  {
   return zahl1;
  }

  return ggT(zahl2, zahl1%zahl2);
}

Der ggT von 18 und 12 ist beispielsweise 6. Denn 18 und 12 sind durch 6 ohne Rest Teilbar.

Wenn man jetzt auch noch das kgV (kleinstes gemeinsames Vielfaches) berechnen will, nimmt man die ggT-Funktion als Grundlage:

(Algorithmus in C)

int kgV(int zahl1, int zahl2)
{
   return (zahl1*zahl2)/ggT(zahl1, zahl2);
}

Das kgV von 18 und 12 ist 36.
Das errechnet sich so:
(zahl1 * zahl2) / ggT(zahl1, zahl2)
(18 * 12) / ggT(18,12)
(216) / 6
= 36

Und zum Abschluss noch ein Programm, das die beiden Werte berechnet:

#include
#include

int ggT(int zahl1, int zahl2)
{
  if(zahl2 == 0)
  {
   return zahl1;
  }

  return ggT(zahl2, zahl1%zahl2);
}

int kgV(int zahl1, int zahl2)
{
   return (zahl1*zahl2)/ggT(zahl1, zahl2);
}

void main(void)
{
   int zahl1, zahl2;
   char nochmal = 'j';
   cout< <"Programm zur Berechnung des ggT und kgVn";
   cout<<"- - - - - - - - - - - - - - - - - - - -  ";
   cout<>zahl1;
    cout< <"nBitte geben sie die zweite Zahl ein: ";
    cin>>zahl2;
    cout< 

Wer sich alles fertig runterladen will:Download von KGVGGT

1 Star2 Stars3 Stars4 Stars5 Stars (3 Stimme, durchschnittlich 5,00 / 5)
Loading...


4 Kommentare zu “[C++] Kleinstes gemeinsames Vielfaches (kgV) und größter gemeinsamer Teiler (ggT)”

  1. […] [C++] Kleinstes gemeinsames Vielfaches (kgV) und größter gemeinsamer Teiler (ggT) (389) […]

  2. Danke!

  3. David Gausmann on Oktober 18th, 2016 at 11:02

    Hallo,

    ich wollte dich nur darauf hinweisen, dass der Code zur Bestimmung des ggT zwar sehr einfach, aber nicht optimal ist.

    Du kannst dir die Rekursion sparen, dadurch läuft der Code dann schneller ab (es ist äußerst unwahrscheinlich, dass der Compiler die Rekursion wegoptimiert):

    int ggT(int zahl1, zahl2)
    {
    for(;;)
    {
    if(!zahl2)
    return zahl1;
    int temp = zahl1;
    zahl1 = zahl2;
    zahl2 = temp % zahl1;
    }
    }

    Aber danke für den Codeschnipsel.

  4. Danke für die Ergänzung

Hinterlasse einen Kommentar!

Time limit is exhausted. Please reload the CAPTCHA.

»Informationen zum Artikel

Autor: Simon
Datum: 24.09.2008
Zeit: 20:54 Uhr
Kategorien: C/C++
Gelesen: 29927x heute: 3x

Kommentare: RSS 2.0.
Diesen Artikel kommentieren oder einen Trackback senden.

»Meta