Das Finden des größten gemeinsamen Teilers mit Hilfe der Rekursion

Einführung

In der Mathematik wird der größte gemeinsame Teiler (ggT) zweier Zahlen im Allgemeinen als die größte positive ganze Zahl definiert, die beide Zahlen ohne Rest teilt. In diesem Lab werden wir lernen, ein C-Programm zu schreiben, um den ggT zweier Zahlen mit Hilfe der Rekursion zu finden.

Hinweis: Sie müssen die Datei ~/project/main.c selbst erstellen, um zu üben, wie man Code schreibt und wie man es mit gcc kompiliert und ausführt.

cd ~/project
## main.c erstellen
touch main.c
## main.c kompilieren
gcc main.c -o main
## main ausführen
./main

Eingabe der Zahlen lesen

Zunächst müssen wir zwei ganzzahlige Eingabewerte vom Benutzer entgegennehmen, um ihren ggT zu berechnen. Wir werden die scanf()-Funktion verwenden, um die Eingabe zu lesen.

#include<stdio.h>

int main()
{
    int a, b;
    printf("Geben Sie zwei Zahlen ein, um deren ggT zu berechnen: \n");
    scanf("%d%d", &a, &b);
    // Rest des Codes
    return 0;
}

Definition der rekursiven Funktion zum Finden des ggT

Wir werden eine rekursive Funktion verwenden, um den ggT der zwei eingegebenen Zahlen zu finden. Die rekursive Funktion wird zwei ganzzahlige Parameter haben. Die Funktion wird sich fortlaufend selbst aufrufen, bis die beiden Zahlen den gleichen Wert haben, und gibt diesen Wert als ggT zurück.

int find_gcd(int x, int y)
{
    if(x == y)
        return x;
    if(x > y)
        return find_gcd(x-y, y);
    return find_gcd(x, y-x);
}

Aufrufen der rekursiven Funktion aus der Hauptfunktion

In diesem Schritt wird die rekursive Funktion mit den zwei Eingabewerten (a und b) aufgerufen. Der Rückgabewert der rekursiven Funktion wird in einer ganzzahligen Variable (gcd) gespeichert.

int gcd = find_gcd(a, b);
printf("Der ggT von %d und %d ist: %d\n", a, b, gcd);

Vollständiges Beispielcode

#include <stdio.h>

// Deklarieren der rekursiven Funktion
int find_gcd(int, int);

int main()
{
    int a, b, gcd;
    printf("Geben Sie zwei Zahlen ein, um deren ggT zu berechnen: \n");
    scanf("%d%d", &a, &b);
    gcd = find_gcd(a, b);
    printf("Der ggT von %d und %d ist: %d\n", a, b, gcd);
    return 0;
}

// Definieren der Funktion
int find_gcd(int x, int y)
{
    if(x == y)
        return x;
    if(x > y)
        return find_gcd(x-y, y);
    return find_gcd(x, y-x);
}

Zusammenfassung

In diesem Lab haben wir gelernt, ein C-Programm zu schreiben, um den ggT von zwei Zahlen mit Hilfe der Rekursion zu berechnen. Wir haben eine rekursive Funktion genutzt, um den ggT zu berechnen, indem die Funktion sich selbst mit modifizierten Eingabeparametern aufruft, bis ein Basisfall erreicht ist. Dieses Programm kann zur Lösung von mathematischen Problemen verwendet werden, bei denen der ggT von zwei Zahlen berechnet werden muss.