Ước chung lớn nhất (GCD) của hai số là số lớn nhất chia cả hai.
Ví dụ:Giả sử chúng ta có hai số là 63 và 21.
63 = 7 * 3 * 3 21 = 7 * 3
Vì vậy, GCD của 63 và 21 là 21.
Thuật toán Euclid đệ quy tính toán GCD bằng cách sử dụng một cặp số nguyên dương a và b và trả về b và a% b cho đến khi b bằng không.
Một chương trình để tìm GCD của hai số bằng thuật toán Euclid đệ quy được đưa ra như sau -
Ví dụ
#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 , b;
cout<<"Enter the values of a and b: "<<endl;
cin>>a>>b;
cout<<"GCD of "<< a <<" and "<< b <<" is "<< gcd(a, b);
return 0;
} Đầu ra
Kết quả của chương trình trên như sau -
Enter the values of a and b: 105 30 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ố, tức là a và b. Nếu b bằng 0, thì a được trả về hàm main (). Nếu không thì hàm gcd () sẽ gọi đệ quy chính nó với các giá trị b và a% b. Điều này được chứng minh bằng đoạn mã sau -
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
} Trong hàm main (), người dùng yêu cầu các giá trị của a và b. Khi đó hàm gcd () được gọi và giá trị GCD của a và b được hiển thị. Điều này được nhìn thấy bên dưới -
int main() {
int a , b;
cout<<"Enter the values of a and b: "<<endl;
cin>>a>>b;
cout<<"GCD of "<< a <<" and "<< b <<" is "<< gcd(a, b);
return 0;
}