โปรแกรม C++ หาตัวหารร่วมมาก (GCD) ด้วย Recursion

GCD (Greatest Common Divisor) = ตัวหารร่วมมากที่สุดของสองจำนวน

ตัวอย่าง: 63 และ 42

63 = 7 × 3 × 3
42 = 7 × 3 × 2
GCD = 7 × 3 = 21

วิธี 1: Euclidean Algorithm แบบลบ (Subtraction)

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    if (a == 0 || b == 0)
        return 0;
    else if (a == b)
        return a;
    else if (a > b)
        return gcd(a-b, b);
    else
        return gcd(a, b-a);
}

int main() {
    int a = 63, b = 42;
    cout << "GCD of " << a << " and " << b << " is " << gcd(a, b);
    return 0;
}

ผลลัพธ์

GCD of 63 and 42 is 21

อธิบาย

int gcd(int a, int b) {
    if (a == 0 || b == 0) return 0;
    else if (a == b) return a;
    else if (a > b) return gcd(a-b, b);
    else return gcd(a, b-a);
}

ลบค่าน้อยออกจากค่ามากซ้ำจนเท่ากัน (หรือหนึ่งเป็น 0)

วิธี 2: Euclidean Algorithm แบบหาร (Modulo) - เร็วกว่า

#include <iostream>
using namespace std;

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

int main() {
    int a = 63, b = 42;
    cout << "GCD of " << a << " and " << b << " is " << gcd(a, b);
    return 0;
}

ผลลัพธ์

GCD of 63 and 42 is 21

อธิบาย

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

เรียกซ้ำด้วย (b, a%b) จน b=0 คืน a เป็น GCD วิธีนี้มีประสิทธิภาพมากกว่าวิธีลบ