Deutsche Lernausgabe

C-Funktionen: ggT und kgV eines Arrays

Kombinieren Sie einen rekursiven ggT mit Zeigerparametern, um zwei Ergebnisse zu berechnen.

Lesen Sie K positive Ganzzahlen. Schreiben Sie eine rekursive ggT-Funktion mit dem euklidischen Algorithmus und berechnen Sie schrittweise ggT und kgV des gesamten Arrays.

Die Funktion find_array_gcd_lcm erhält das Array und zwei Ausgabezeiger. Die Zeiger werden als Werte übergeben, doch durch Dereferenzieren lassen sich die Ergebnisobjekte beim Aufrufer ändern.

Eingabe

K, danach K positive Ganzzahlen.

Ausgabe

Eine Zeile: Array GCD: <ggT> | Array LCM: <kgV>.

Vorgaben

2 ≤ K ≤ 10; jeder Wert liegt zwischen 1 und 10⁶.
Das endgültige kgV passt in eine vorzeichenbehaftete 64-Bit-Ganzzahl; verwenden Sie long long.

Hinweise

gcd(a, b) ist gcd(b, a % b), mit dem Basisfall b == 0.
Berechnen Sie das kgV mit (a / gcd(a, b)) * b.
Initialisieren Sie beide Akkumulatoren mit dem ersten Arrayelement.

Quellcode

#include <stdio.h>

// Recursive Euclidean algorithm
long long gcd(long long a, long long b) {
    // TODO: Base case and recursive call
    return 0;
}

long long lcm(long long a, long long b) {
    // TODO: (a / gcd(a, b)) * b
    return 0;
}

// Function modifying outputs via pointers
void find_array_gcd_lcm(int k, long long arr[], long long *out_gcd, long long *out_lcm) {
    // TODO: Loop through array and accumulate overall GCD and LCM
}

int main(void) {
    int k;
    if (scanf("%d", &k) != 1 || k < 2) return 1;

    long long arr[10];
    for (int i = 0; i < k; i++) {
        scanf("%lld", &arr[i]);
    }

    long long result_gcd = 0;
    long long result_lcm = 0;

    find_array_gcd_lcm(k, arr, &result_gcd, &result_lcm);

    printf("Array GCD: %lld | Array LCM: %lld\n", result_gcd, result_lcm);
    return 0;
}

Im Compiler öffnen

Erklärung der Lösung

Implementieren Sie den rekursiven ggT und durchlaufen Sie dann die übrigen Werte, um beide Akkumulatoren zu aktualisieren. Schreiben Sie die Ergebnisse nach *out_gcd und *out_lcm.

Division vor Multiplikation verkleinert den Zwischenwert, ersetzt aber keine Prüfung der Typgrenzen. Die Vorgaben garantieren hier ein darstellbares endgültiges kgV.

Jeder ggT benötigt logarithmisch viele Schritte in Bezug auf den kleineren Operanden und eine logarithmische Rekursionstiefe.

Lösungscode

#include <stdio.h>

// Recursive Euclidean algorithm
long long gcd(long long a, long long b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

// Compute LCM preventing overflow by dividing before multiplying
long long lcm(long long a, long long b) {
    if (a == 0 || b == 0) return 0;
    return (a / gcd(a, b)) * b;
}

// Compute GCD and LCM for an array using pointers
void find_array_gcd_lcm(int k, long long arr[], long long *out_gcd, long long *out_lcm) {
    if (k <= 0) return;

    long long current_gcd = arr[0];
    long long current_lcm = arr[0];

    for (int i = 1; i < k; i++) {
        current_gcd = gcd(current_gcd, arr[i]);
        current_lcm = lcm(current_lcm, arr[i]);
    }

    *out_gcd = current_gcd;
    *out_lcm = current_lcm;
}

int main(void) {
    int k;
    if (scanf("%d", &k) != 1 || k < 2 || k > 10) return 1;

    long long arr[10];
    for (int i = 0; i < k; i++) {
        if (scanf("%lld", &arr[i]) != 1) return 1;
    }

    long long result_gcd = 0;
    long long result_lcm = 0;

    find_array_gcd_lcm(k, arr, &result_gcd, &result_lcm);

    printf("Array GCD: %lld | Array LCM: %lld\n", result_gcd, result_lcm);
    return 0;
}

Häufige Fragen

Warum bleiben Code und manche Ausgaben englisch?

C-Schlüsselwörter, Bezeichner, Programmkommentare und erwartete Ausgaben bleiben wie im Original, damit der Code ausführbar und die Tests konsistent bleiben. Erklärungen und Aufgabenstellungen sind übersetzt.