Größter gemeinsamer Teiler (GGT) in C berechnen

Einführung

In diesem Labor lernen Sie, den größten gemeinsamen Teiler (GGT) zweier ganzer Zahlen mithilfe des euklidischen Algorithmus in einem C-Programm zu finden. Sie beginnen damit, zwei ganze Zahlen von der Benutzereingabe zu lesen, wenden dann den euklidischen Algorithmus an, um ihren GGT zu berechnen, und geben schließlich das Ergebnis aus. Dieses Labor behandelt grundlegende Konzepte der Zahlentheorie und diskreten Mathematik und bietet eine praktische Anwendung dieser Prinzipien mithilfe der C-Programmierung.

Zwei ganze Zahlen einlesen

In diesem Schritt lernen Sie, wie Sie zwei ganze Zahlen von der Benutzereingabe in einem C-Programm lesen, um ihren größten gemeinsamen Teiler (GGT) zu finden.

Erstellen Sie zunächst eine neue C-Datei für unser GGT-Programm:

cd ~/project
nano gcd.c

Fügen Sie nun den folgenden Code hinzu, um zwei ganze Zahlen einzulesen:

#include <stdio.h>

int main() {
    int num1, num2;

    printf("Geben Sie die erste ganze Zahl ein: ");
    scanf("%d", &num1);

    printf("Geben Sie die zweite ganze Zahl ein: ");
    scanf("%d", &num2);

    printf("Erste Zahl: %d\n", num1);
    printf("Zweite Zahl: %d\n", num2);

    return 0;
}

Lassen Sie uns den Code aufschlüsseln:

• scanf() wird verwendet, um ganzzahlige Eingaben vom Benutzer zu lesen.
• %d ist der Formatbezeichner für ganze Zahlen.
• &num1 und &num2 übergeben die Speicheradressen der Variablen, um die Eingabe zu speichern.

Kompilieren und führen Sie das Programm aus:

gcc gcd.c -o gcd
./gcd

Beispielausgabe:

Geben Sie die erste ganze Zahl ein: 48
Geben Sie die zweite ganze Zahl ein: 18
Erste Zahl: 48
Zweite Zahl: 18

Euklidischen Algorithmus anwenden

In diesem Schritt implementieren Sie den euklidischen Algorithmus, um den größten gemeinsamen Teiler (GGT) zweier ganzer Zahlen zu finden.

Öffnen Sie die vorherige Datei gcd.c und ändern Sie sie, um die GGT-Berechnung einzuschließen:

cd ~/project
nano gcd.c

Aktualisieren Sie den Code mit der Implementierung des euklidischen Algorithmus:

#include <stdio.h>

// Funktion zur Berechnung des GGT mit dem euklidischen Algorithmus
int calculateGCD(int a, int b) {
    // Sicherstellung positiver Zahlen
    a = (a > 0) ? a : -a;
    b = (b > 0) ? b : -b;

    // Euklidischer Algorithmus
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }

    return a;
}

int main() {
    int num1, num2, gcd;

    printf("Geben Sie die erste ganze Zahl ein: ");
    scanf("%d", &num1);

    printf("Geben Sie die zweite ganze Zahl ein: ");
    scanf("%d", &num2);

    // Berechnung des GGT
    gcd = calculateGCD(num1, num2);

    printf("Erste Zahl: %d\n", num1);
    printf("Zweite Zahl: %d\n", num2);
    printf("Größter gemeinsamer Teiler: %d\n", gcd);

    return 0;
}

Lassen Sie uns die Implementierung des euklidischen Algorithmus aufschlüsseln:

• Der Algorithmus teilt die größere Zahl wiederholt durch die kleinere Zahl.
• Er verwendet den Modulo-Operator %, um den Rest zu erhalten.
• Der Prozess wird fortgesetzt, bis der Rest 0 wird.
• Der letzte nicht-null Rest ist der GGT.

Kompilieren und führen Sie das Programm aus:

gcc gcd.c -o gcd
./gcd

Beispielausgabe:

Geben Sie die erste ganze Zahl ein: 48
Geben Sie die zweite ganze Zahl ein: 18
Erste Zahl: 48
Zweite Zahl: 18
Größter gemeinsamer Teiler: 6

Ausgabe des GGT

In diesem Schritt formatieren und drucken Sie das GGT-Ergebnis mit zusätzlichen Kontextinformationen, um die Ausgabe informativer zu gestalten.

Öffnen Sie die vorherige Datei gcd.c und fügen Sie der Ausgabe einige Formatierungen hinzu:

cd ~/project
nano gcd.c

Aktualisieren Sie den Code, um die GGT-Ausgabe zu verbessern:

#include <stdio.h>

// Funktion zur Berechnung des GGT mit dem euklidischen Algorithmus
int calculateGCD(int a, int b) {
    // Sicherstellung positiver Zahlen
    a = (a > 0) ? a : -a;
    b = (b > 0) ? b : -b;

    // Euklidischer Algorithmus
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }

    return a;
}

int main() {
    int num1, num2, gcd;

    printf("GGT-Rechner (Größter gemeinsamer Teiler)\n");
    printf("----------------------------------------\n");

    printf("Geben Sie die erste ganze Zahl ein: ");
    scanf("%d", &num1);

    printf("Geben Sie die zweite ganze Zahl ein: ");
    scanf("%d", &num2);

    // Berechnung des GGT
    gcd = calculateGCD(num1, num2);

    // Formatierte Ausgabe
    printf("\nErgebnisse:\n");
    printf("Erste Zahl:  %d\n", num1);
    printf("Zweite Zahl: %d\n", num2);
    printf("GGT:           %d\n", gcd);

    // Zusätzliche Erklärung
    printf("\nErklärung:\n");
    printf("Der größte gemeinsame Teiler (GGT) ist die größte positive ganze Zahl,\n");
    printf("die beide Zahlen ohne Rest teilt.\n");

    return 0;
}

Kompilieren und ausführen des Programms:

gcc gcd.c -o gcd
./gcd

Beispielausgabe:

GGT-Rechner (Größter gemeinsamer Teiler)
----------------------------------------
Geben Sie die erste ganze Zahl ein: 48
Geben Sie die zweite ganze Zahl ein: 18

Ergebnisse:
Erste Zahl:  48
Zweite Zahl: 18
GGT:           6

Erklärung:
Der größte gemeinsame Teiler (GGT) ist die größte positive ganze Zahl,
die beide Zahlen ohne Rest teilt.

Wichtige Verbesserungen:

• Hinzufügen eines Titels und Trennlinie
• Formatierte Ausgabe mit ausgerichteten Spalten
• Einschließen einer Erklärung zum GGT-Konzept
• Beibehaltung der Kernlogik der GGT-Berechnung

Zusammenfassung

In diesem Labor haben Sie zunächst gelernt, wie man zwei ganze Zahlen über die Benutzereingabe mit der Funktion scanf() liest. Anschließend haben Sie den euklidischen Algorithmus implementiert, um den größten gemeinsamen Teiler (GGT) der beiden Zahlen zu berechnen. Der euklidische Algorithmus ist eine effiziente Methode zur Bestimmung des GGT, indem die Modulo-Operation wiederholt angewendet wird, bis der Rest Null wird. Zu diesem Zeitpunkt ist der GGT der letzte nicht-null Rest. Schließlich haben Sie den berechneten GGT ausgegeben.