C-Programmierung | LCM-Berechnung | Rekursion

Einführung

In diesem Lab schreiben wir ein C-Programm, um das kleinste gemeinsame Vielfache (englisch: LCM - Least Common Multiple) von zwei Zahlen mit Hilfe der Rekursion zu berechnen. Das kleinste gemeinsame Vielfache ist die kleinste positive ganze Zahl, die von beiden Zahlen ohne Rest teilbar ist.

Verstehen Sie das Konzept von LCM

Bevor wir mit der Programmierung beginnen, verstehen wir das Konzept des kleinsten gemeinsamen Vielfachen. Das kleinste gemeinsame Vielfache von zwei ganzen Zahlen ist die kleinste positive ganze Zahl, die ein Vielfaches beider Zahlen ist. Um das kleinste gemeinsame Vielfache von zwei Zahlen zu finden, können wir die folgende Formel verwenden:

KGV = (Zahl1 * Zahl2) / ggT

Wobei Zahl1 und Zahl2 die beiden Zahlen sind, für die wir das kleinste gemeinsame Vielfache finden müssen, und ggT der größte gemeinsame Teiler der beiden Zahlen ist.

Erstellen Sie eine neue C-Datei

Erstellen wir in unserem Projektverzeichnis ~/project/ eine neue C-Datei namens main.c, in der wir unser Programm schreiben werden.

Schreiben Sie den Code

Kopieren Sie den folgenden Code in die Datei main.c.

#include<stdio.h>

int find_lcm(int, int); // Funktionsprototypdeklaration

int main()
{
    int a, b, lcm;
    printf("Geben Sie zwei ganze Zahlen ein, um das kleinste gemeinsame Vielfache zu finden:\n");
    scanf("%d %d", &a, &b);
    lcm = find_lcm(a, b); // Funktionsaufruf
    printf("Das kleinste gemeinsame Vielfache von %d und %d ist %d.\n", a, b, lcm);

    return 0;
}

int find_lcm(int a, int b) // Funktionsdefinition
{
    static int temp = 1;
    if(temp % a == 0 && temp % b == 0)
        return temp;
    else
    {
        temp++;
        find_lcm(a, b);
        return temp;
    }
}

Kompilieren und ausführen des Programms

Speichern Sie die Datei main.c und kompilieren Sie das Programm im Terminal mit dem folgenden Befehl:

gcc main.c -o main

Führen Sie das Programm mit dem folgenden Befehl aus:

./main

Geben Sie bei der Aufforderung zwei ganze Zahlen ein, und das Programm wird das kleinste gemeinsame Vielfache der beiden Zahlen anzeigen.

Verstehen Sie den Code

Lassen Sie uns den Code verstehen, den wir gerade geschrieben haben.

Wir importieren zunächst die Standard-Eingabe-/Ausgabebibliothek in unserem Programm mit #include<stdio.h>.
Wir deklarieren den Funktionsprototyp von find_lcm, den wir später in unserem Programm definieren werden. Dies ist notwendig, da wir die find_lcm-Funktion in unserer Hauptfunktion vor ihrer tatsächlichen Definition aufrufen.
In der Hauptfunktion deklarieren wir drei ganzzahlige Variablen a, b und lcm.
Wir bitten den Benutzer, zwei ganze Zahlen einzugeben, indem wir printf verwenden, und akzeptieren die Eingabe mit scanf.
Anschließend rufen wir die find_lcm-Funktion auf und übergeben a und b als Argumente.
Die find_lcm-Funktion nimmt zwei ganzzahlige Argumente a und b entgegen und gibt das kleinste gemeinsame Vielfache der beiden Zahlen mithilfe von Rekursion zurück.
Wir initialisieren eine statische Variable temp mit 1, die den aktuellen Wert speichern wird, den wir auf ein Vielfaches prüfen.
In jeder Rekursion überprüfen wir, ob temp ein Vielfaches von sowohl a als auch b ist.
Wenn es ein Vielfaches ist, geben wir temp als das kleinste gemeinsame Vielfache zurück.
Wenn es kein Vielfaches ist, erhöhen wir temp und rufen die find_lcm-Funktion rekursiv auf, bis wir das kleinste gemeinsame Vielfache finden.

Testen Sie das Programm

Testen Sie das Programm mit verschiedenen Eingabewerten und vergewissern Sie sich, dass es die korrekte kleinste gemeinsame Vielfache-Ausgabe erzeugt.

Vollständiger Code

Hier ist der vollständige Code für das C-Programm, um das kleinste gemeinsame Vielfache von zwei Zahlen mithilfe von Rekursion zu finden:

#include<stdio.h>

int find_lcm(int, int); // Funktionsprototypdeklaration

int main()
{
    int a, b, lcm;
    printf("Geben Sie zwei ganze Zahlen ein, um das kleinste gemeinsame Vielfache zu finden:\n");
    scanf("%d %d", &a, &b);
    lcm = find_lcm(a, b); // Funktionsaufruf
    printf("Das kleinste gemeinsame Vielfache von %d und %d ist %d.\n", a, b, lcm);

    return 0;
}

int find_lcm(int a, int b) // Funktionsdefinition
{
    static int temp = 1;
    if(temp % a == 0 && temp % b == 0)
        return temp;
    else
    {
        temp++;
        find_lcm(a, b);
        return temp;
    }
}

Zusammenfassung

In diesem Lab haben wir gelernt, wie man ein C-Programm schreibt, um das kleinste gemeinsame Vielfache von zwei Zahlen mithilfe von Rekursion zu finden. Wir haben eine rekursive Funktion verwendet, um das kleinste gemeinsame Vielfache zu finden und jede Schritt des Programms im Detail erklärt. Wir haben auch gelernt, wie man ein C-Programm mit dem Terminal kompiliert und ausführt.

Rekursive LCM-Berechnung in C