Ướ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ố sau:45 và 27
63 = 7 * 3 * 3 42 = 7 * 3 * 2 So, the GCD of 63 and 42 is 21
Một chương trình để tìm GCD của hai số bằng cách sử dụng đệ quy được đưa ra như sau.
Ví dụ
#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;
} Đầu ra
GCD of 63 and 42 is 21
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 a hoặc b bằng 0, hàm trả về 0. Nếu a hoặc b bằng nhau, hàm trả về a. Nếu a lớn hơn b, hàm gọi đệ quy chính nó với các giá trị a-b và b. Nếu b lớn hơn a, hàm gọi đệ quy chính nó với các giá trị a và b-a.
Điều này được chứng minh bằng đoạn mã sau.
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);
} Một phương pháp khác để tìm GCD của hai số bằng cách sử dụng đệ quy 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 = 63, b = 42;
cout<<"GCD of "<< a <<" and "<< b <<" is "<< gcd(a, b);
return 0;
} Đầu ra
GCD of 63 and 42 is 21
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 lớn hơn 0, thì a được trả về hàm main (). Nếu không, hàm gcd () tự gọi đệ quy với các giá trị b và a% b.
Điều này được chứng minh bằng cách sử dụng đoạn mã sau.
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}