Ước chung lớn nhất (GCD – Greatest Common Divisor) của 2 số nguyên và là số nguyên lớn nhất thỏa mãn tính chất cả a và b đều chia hết cho d. Đây là một thuật toán được sử dụng khá phổ biến trong lập trình, trong bài viết này chúng tôi xin được chia sẻ với các bạn 4 thuật toán tìm ƯCLN của 2 số:
1. Thuật toán sử dụng phép trừ
int uc_tru(int a, int b){
if(a == 0 || b == 0) { return a;}
while (a!=b){
if (a > b) {a -= b;}
else {b -= a;}
}
return a;
}
2. Thuật toán sử dụng phép chia
int uc_chia(int a, int b){
while (a*b != 0) {
if (a > b) {
a %= b;
}
else {
b %= a;
}
}
return a + b;
}
3. Thuật toán sử dụng đệ quy
int uc_Dequy(int a, int b) {
int temp;
if(b == 0) return a;
return uc_Dequy(b, a % b);
}
4. Thuật toán sử dụng hàm có sẵn trong C++
Với thuật toán này, chúng ta cần khai báo thêm thư viện algorithm:
cout << "UCLN(" << a << ", " << b << ") = " << __gcd(a, b);
Tham khảo phần Code chúng tôi đã thực hiện:
#include<iostream>
#include <algorithm>
using namespace std;
// Thuat toan su dung phep tru:
int uc_tru(int a, int b){
if(a == 0 || b == 0) { return a;}
while (a!=b){
if (a > b) {a -= b;}
else {b -= a;}
}
return a;
}
// Thuat toan su dung phep chia:
int uc_chia(int a, int b){
while (a*b != 0) {
if (a > b) {
a %= b;
}
else {
b %= a;
}
}
return a + b; // Vi luc nay mot trong hai so a hoac b bang 0
}
// Thuat toan su dung de quy
int uc_Dequy(int a, int b) {
int temp;
if(b == 0) return a;
return uc_Dequy(b, a % b);
}
int main(){
int a, b;
cout << "Nhap 2 so:" << endl;
cout << "a = "; cin >> a;
cout << "b = "; cin >> b;
cout << endl << "Su dung phep tru: ";
cout << "UCLN(" << a << ", " << b << ") = " << uc_tru(a, b);
cout << endl << "Su dung phep chia: ";
cout << "UCLN(" << a << ", " << b << ") = " << uc_chia(a,b);
cout << endl << "Su dung De quy: ";
cout << "UCLN(" << a << ", " << b << ") = " << uc_Dequy(a, b);
cout << endl << "Su dung Ham co san: ";
cout << "UCLN(" << a << ", " << b << ") = " << __gcd(a, b);
return 0;
}
