Chương trình C++ tìm Ước chung lớn nhất (GCD)

Ước chung lớn nhất (GCD) của hai số là số lớn nhất chia hết cho cả hai số đó.

Ví dụ: Giả sử chúng ta có hai số 45 và 27.

45 = 5 * 3 * 3
27 = 3 * 3 * 3

Vậy GCD của 45 và 27 là 9.

Chương trình tìm GCD của hai số như sau:

Ví dụ 1: Thuật toán Euclid đệ quy

#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 = 105, b = 30;
    cout << "GCD of " << a << " and " << b << " is " << gcd(a, b);
    return 0;
}

Đầu ra

GCD of 105 and 30 is 15

Trong chương trình trên, gcd() là một hàm đệ quy. Nó có hai tham số là a và b. Nếu b bằng 0, thì a được trả về. Ngược lại, hàm gọi đệ quy chính nó với b và a % b.

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

Ví dụ 2: Thuật toán trừ liên tiếp (đệ quy)

#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 = 105, b = 30;
    cout << "GCD of " << a << " and " << b << " is " << gcd(a, b);
    return 0;
}

Đầu ra

GCD of 105 and 30 is 15

Trong chương trình này, gcd() cũng là hàm đệ quy. Nếu a hoặc b bằng 0, trả về 0. Nếu bằng nhau, trả về a. Nếu a > b, gọi đệ quy với a-b, b; ngược lại gọi với a, b-a.

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