Édition pédagogique en français

Fonctions en C : PGCD et PPCM d’un tableau

Combinez un PGCD récursif et des paramètres pointeurs pour calculer deux résultats.

Lisez K entiers positifs. Écrivez un PGCD récursif avec l’algorithme d’Euclide et calculez progressivement le PGCD et le PPCM de l’ensemble du tableau.

La fonction find_array_gcd_lcm reçoit le tableau et deux pointeurs de sortie. Les pointeurs sont passés par valeur, mais leur déréférencement permet de modifier les objets de résultat chez l’appelant.

Entrée

K, puis K entiers positifs.

Sortie

Une ligne : Array GCD: <pgcd> | Array LCM: <ppcm>.

Contraintes

2 ≤ K ≤ 10 ; chaque valeur est comprise entre 1 et 10⁶.
Le PPCM final tient dans un entier signé de 64 bits ; utilisez long long.

Indices

gcd(a, b) vaut gcd(b, a % b), avec le cas de base b == 0.
Calculez le PPCM par (a / gcd(a, b)) * b.
Initialisez les deux accumulateurs avec le premier élément du tableau.

Code source

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

Ouvrir dans le compilateur

Explication de la solution

Implémentez le PGCD récursif, puis parcourez les autres valeurs pour mettre à jour les deux accumulateurs. Écrivez les résultats dans *out_gcd et *out_lcm.

Diviser avant de multiplier réduit la taille de l’intermédiaire, mais ne dispense pas de vérifier les bornes du type. Les contraintes garantissent ici un PPCM final représentable.

Chaque PGCD utilise un nombre logarithmique d’étapes par rapport au plus petit opérande, avec une profondeur de récursion logarithmique.

Code de la solution

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

Questions fréquentes

Pourquoi le code et certains résultats restent-ils en anglais ?

Les mots-clés C, les identifiants, les commentaires du programme et les sorties attendues restent ceux de la version originale pour conserver un code exécutable et des tests cohérents. Les explications et les consignes sont traduites.