GGT in der C-Programmierung finden

Einführung

In der C-Programmierung wird häufig der ggT (Größter gemeinsamer Teiler) berechnet. Zwei verschiedene Methoden werden üblicherweise verwendet, um den ggT zu finden. Wir können den euklidischen Algorithmus verwenden und den ggT durch wiederholtes Subtrahieren berechnen. In diesem schrittweisen Lab werden wir beide Methoden demonstrieren.

Verwendung des euklidischen Algorithmus

Der euklidische Algorithmus, bei dem der Zähler durch den Rest der Divisionsoperation ersetzt wird, wird verwendet, um den ggT zu berechnen. Wenn der Rest null wird, ist der ggT der Zähler.

1.1 Beginne die Lösung, indem du eine ganzzahlige Variable namens a und b deklarierst.

    int a, b;

1.2 Danach frage den Benutzer, die Werte von a und b einzugeben.

    printf("Enter two numbers: \n");
    scanf("%d %d", &a, &b);

1.3 Erstelle dann eine while-Schleife, die solange läuft, bis der Rest der Division von a durch b null ist.

    while(a!=b)
    {
        if(a>b)
            a=a-b;
        else
            b=b-a;
    }

1.4 Zeige schließlich den ggT der beiden Zahlen an.

    printf("The GCD of two numbers is %d", a);

Verwendung der Methode mit wiederholtem Subtrahieren

In dieser Methode wird der ggT berechnet, indem der kleinere Wert wiederholt von dem größeren Wert subtrahiert wird, bis beide gleich werden. Wenn beide gleich werden, ist die Zahl der ggT.

2.1 Beginne mit einer ganzzahligen Variable namens num, die mit 0 initialisiert wird.

    int num = 0;

2.2 Deklariere eine ganzzahlige Variable namens x und initialisiere sie mit 2.

    int x = 2;

2.3 Frage den Benutzer, die Anzahl der ganzen Zahlen ein, für die der ggT berechnet werden soll.

    printf("Enter the number of integers you want to find the GCD of: ");
    scanf("%d", &num);

2.4 Danach frage den Benutzer die Zahlen ein.

    printf("Enter %d numbers:\n", num);
    int arr[num];
    for(int i = 0; i < num; i++)
    {
        scanf("%d", &arr[i]);
    }

2.5 Jetzt können wir den ggT berechnen, indem wir die eingegebenen Werte verwenden und die Methode mit wiederholtem Subtrahieren anwenden. Wir werden die Funktion gcd() aufrufen, um den ggT der eingegebenen Werte zu berechnen.

    int result = arr[0];
    for(int i = 1; i < num; i++)
    {
        result = gcd(result, arr[i]);
    }

Kombinieren der Methoden

In diesem Schritt werden wir die Methoden kombinieren, um die Implementierung abzuschließen.

3.1 Deklariere eine Funktion gcd(), die bei der Berechnung des ggT mit der Methode des wiederholten Subtrahierens verwendet wird.

    int gcd(int a, int b)
    {
        if(b==0)
            return a;
        else if(a >= b && b > 0)
            return gcd(b,a%b);
        else
            return gcd(b,a);
    }

3.2 Deklariere eine neue Variable namens gcd_result und initialisiere sie mit Null.

    int gcd_result = 0;

3.3 Wir werden eine neue Schleife erstellen, die den Benutzer auffordert, Zahlen einzugeben, bis ein Eingabewert von 0 erkannt wird.

    printf("Enter numbers. To exit enter 0\n");
    while(1)    // unendliche Schleife, um Eingaben zu erhalten
    {
        int num;
        scanf("%d", &num);
        if(num < 1)
            break;
        else if(gcd_result == 0)
            gcd_result = num;
        else if(num < gcd_result)
            gcd_result = gcd(num, gcd_result);
        else
            gcd_result = gcd(gcd_result, num);
    }

3.4 Am Ende wird das Endresultat mit der printf-Funktion angezeigt.

    printf("The GCD of all the entered numbers is: %d\n", gcd_result);

Zusammenfassung

In diesem Lab haben wir zwei Methoden gelernt, um den ggT (Größten gemeinsamen Teiler) einer Gruppe ganzer Zahlen in der C-Programmierung zu berechnen: den euklidischen Algorithmus und die Methode des wiederholten Subtrahierens. Wir haben gezeigt, wie diese Methoden verwendet werden, mit einer detaillierten Erklärung und Beispielcodeblöcken. Für einen weiteren Verständnis wird empfohlen, den Code in der main.c-Datei zu modifizieren und auszuführen.