Edisi pembelajaran bahasa Indonesia. Kode dan keluarannya tetap seperti aslinya.

Fungsi rekursif: FPB dan KPK array

Gabungkan algoritma Euclid dengan parameter keluaran melalui pointer.

Baca K bilangan bulat positif. Implementasikan gcd(a, b) secara rekursif melalui gcd(b, a % b) dengan kasus dasar b == 0. Hitung kelipatan persekutuan terkecil menggunakan (a / gcd(a, b)) * b.

Implementasikan find_array_gcd_lcm dengan parameter k, arr, out_gcd, dan out_lcm. Gabungkan elemen array secara bertahap ke kedua hasil dan tulis melalui pointer keluaran. Pertahankan label Array GCD: dan Array LCM: tanpa terjemahan.

Masukan

Baris pertama: K. Baris kedua: K integer positif yang dipisahkan spasi.

Keluaran

Array GCD: <FPB> | Array LCM: <KPK>

Batasan

2 <= K <= 10
1 <= arr[i] <= 1.000.000
KPK akhir muat dalam long long bertanda 64-bit.

Petunjuk

Saat b == 0, kembalikan a; jika tidak, panggil gcd(b, a % b).
Lakukan pembagian sebelum perkalian saat menghitung KPK.

Kode C

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

Buka di kompiler

Solusi dan penjelasan

Inisialisasi kedua akumulator dengan elemen pertama lalu gabungkan dengan setiap elemen berikutnya. Algoritma Euclid mengurangi operand kedua sampai nol.

Membagi dengan FPB sebelum mengalikan menghindari hasil antara yang terlalu besar. Jaminan rentang dalam soal tetap diperlukan: rumus ini tidak menghapus risiko overflow untuk semua masukan.

C meneruskan nilai pointer; penulisan ke *out_gcd dan *out_lcm mengubah objek pemanggil. Setiap perhitungan FPB bersifat logaritmik terhadap operand lebih kecil dan memakai kedalaman rekursi logaritmik.

Kode solusi

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

Pertanyaan umum

Mengapa kode dan keluarannya tetap dalam bahasa Inggris?

Kata kunci, pengenal, dan teks yang diperiksa tes dipertahankan agar program tidak berubah. Penjelasan dan kontrol telah diterjemahkan.