Edizione didattica italiana

Funzioni in C: MCD e mcm di un array

Combina Euclide ricorsivo e parametri puntatore per calcolare due risultati.

Leggi K interi positivi. Scrivi un MCD ricorsivo con l’algoritmo di Euclide e calcola progressivamente MCD e minimo comune multiplo di tutto l’array.

find_array_gcd_lcm riceve l’array e due puntatori di output. I puntatori sono passati per valore, ma dereferenziandoli puoi modificare gli oggetti risultato del chiamante.

Input

K, poi K interi positivi.

Output

Una riga: Array GCD: <MCD> | Array LCM: <mcm>.

Vincoli

2 ≤ K ≤ 10; ciascun valore è tra 1 e 10⁶.
Il mcm finale è rappresentabile con un intero con segno di 64 bit; usa long long.

Suggerimenti

gcd(a, b) è gcd(b, a % b), con caso base b == 0.
Calcola il mcm come (a / gcd(a, b)) * b.
Inizializza entrambi gli accumulatori con il primo elemento.

Codice sorgente

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

Apri nel compilatore

Spiegazione della soluzione

Implementa MCD ricorsivo e visita gli altri valori aggiornando i due accumulatori. Scrivi i risultati in *out_gcd e *out_lcm.

Dividere prima di moltiplicare riduce il valore intermedio ma non elimina il controllo dei limiti. Qui i vincoli garantiscono un risultato finale rappresentabile.

Ogni MCD usa un numero logaritmico di passi rispetto all’operando minore, con profondità di ricorsione logaritmica.

Codice della soluzione

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

Domande frequenti

Perché il codice e alcuni risultati restano in inglese?

Parole chiave C, identificatori, commenti del programma e output attesi restano quelli originali per preservare codice eseguibile e test coerenti. Spiegazioni e istruzioni sono tradotte.