Chương trình C++ tìm ước chung lớn nhất (GCD) bằng đệ quy

Ước chung lớn nhất (GCD - Greatest Common Divisor) của hai số là số lớn nhất chia hết cả hai.

Ví dụ: Hai số 45 và 27 (sửa: 63 và 42)

63 = 7 × 3 × 3
42 = 7 × 3 × 2
GCD của 63 và 42 là 21

Chương trình tìm GCD bằng đệ quy:

Ví dụ (Phép trừ)

#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 của " << a << " và " << b << " là " << gcd(a, b);
  return 0;
}

Kết quả đầu ra

GCD của 63 và 42 là 21

Trong chương trình, gcd() là hàm đệ quy với tham số a, b. 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 và b. Nếu b > a, gọi đệ quy với a và 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);
}

Phương pháp khác tìm GCD đệ quy (thuật toán Euclid):

Ví dụ (Thuật toán Euclid)

#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 của " << a << " và " << b << " là " << gcd(a, b);
  return 0;
}

Kết quả đầu ra

GCD của 63 và 42 là 21

Trong chương trình này, gcd() đệ quy. Nếu b == 0, trả về a. Ngược lại gọi đệ quy với b và a % b:

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