โปรแกรม C++ หา GCD ของมากกว่าสองจำนวน (หรืออาร์เรย์)

ที่นี่เราจะดูวิธีหา GCD (Greatest Common Divisor) ของมากกว่าสองจำนวน การหา GCD ของสองจำนวนง่าย แต่ต้องการหา GCD ของมากกว่าสองจำนวน ต้องปฏิบัติตามกฎ associativity ของ GCD ตัวอย่างเช่น ถ้าอยากหา GCD ของ {w, x, y, z} จะเป็น {gcd(w,x), y, z} แล้ว {gcd(gcd(w,x), y), z} และสุดท้าย {gcd(gcd(gcd(w,x), y), z)} โดยใช้อาร์เรย์ทำได้ง่ายมาก

อัลกอริทึม

gcd(a, b)

begin
    if a is 0, then
        return b
    end if
    return gcd(b mod a, a)
end

getArrayGcd(arr, n)

begin
    res := arr[0]
    for i in range 1 to n-1, do
        res := gcd(arr[i], res)
    done
    return res;
end

ตัวอย่าง

#include<iostream>
using namespace std;

int gcd(int a, int b) {
    if (a == 0)
        return b;
    return gcd(b % a, a);
}

int getArrayGcd(int arr[], int n) {
    int res = arr[0];
    for(int i = 1; i < n; i++) {
        res = gcd(arr[i], res);
    }
    return res;
}

int main() {
    int arr[] = {4, 8, 16, 24};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "GCD of array elements: " << getArrayGcd(arr, n);
}

ผลลัพธ์

GCD of array elements: 4