Nederlandse leereditie

C-functies: ggd en kgv van een array

Combineer recursieve Euclides en pointerparameters om twee resultaten te berekenen.

Lees K positieve gehele getallen. Schrijf een recursieve ggd met Euclides en bereken stapsgewijs de grootste gemene deler en het kleinste gemene veelvoud van het hele array.

find_array_gcd_lcm ontvangt het array en twee uitvoerpointers. De pointers worden als waarden doorgegeven, maar door derefereren kun je resultaatobjecten van de aanroeper wijzigen.

Invoer

K, daarna K positieve gehele getallen.

Uitvoer

Eén regel: Array GCD: <ggd> | Array LCM: <kgv>.

Voorwaarden

2 ≤ K ≤ 10; elke waarde ligt tussen 1 en 10⁶.
Het uiteindelijke kgv past in een 64-bits geheel getal met teken; gebruik long long.

Hints

gcd(a, b) is gcd(b, a % b), met basisgeval b == 0.
Bereken het kgv als (a / gcd(a, b)) * b.
Initialiseer beide accumulatoren met het eerste element.

Broncode

#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;
}

Openen in de compiler

Uitleg van de oplossing

Implementeer recursieve ggd en doorloop de overige waarden om beide accumulatoren bij te werken. Schrijf de resultaten naar *out_gcd en *out_lcm.

Delen vóór vermenigvuldigen verkleint de tussenwaarde, maar vervangt geen grenscontrole. Hier garanderen de eisen een eindresultaat dat past.

Elke ggd gebruikt een logaritmisch aantal stappen ten opzichte van de kleinste operand, met logaritmische recursiediepte.

Oplossingscode

#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;
}

Veelgestelde vragen

Waarom blijven code en sommige resultaten Engels?

C-sleutelwoorden, namen, programmacommentaar en verwachte uitvoer blijven gelijk aan het origineel om uitvoerbare code en consistente tests te behouden. Uitleg en instructies zijn vertaald.