Trong bài viết này, chúng ta sẽ tìm hiểu về thuật toán tìm ước chung lớn nhất trong C++ và cách tối ưu hóa bài toán này bằng cách sử dụng vòng lặp, thuật toán Euclid và thuật toán trừ.
Tổng quan về bài toán
Bài toán yêu cầu tìm ước chung lớn nhất của hai số nguyên A và B.
Cách tìm ước chung lớn nhất sử dụng vòng lặp
Đây là cách đơn giản để tìm ước chung lớn nhất. Chúng ta sẽ sử dụng vòng lặp for để lặp từ min(A, B) về 0 và kiểm tra từng giá trị.
Bước triển khai thuật toán này như sau:
- Lặp từ min(A, B) về 0.
- Kiểm tra xem A và B có chia hết cho giá trị hiện tại hay không. Nếu chia hết, trả về giá trị hiện tại.
Với ngôn ngữ C/C++, triển khai thuật toán sẽ như sau:
int gcd(int A, int B) { for (int i = min(A, B); i >= 1; i--) { if (A % i == 0 && B % i == 0) { return i; } } return -1; }Đây là cách đơn giản nhất để giải quyết bài toán này, tuy nhiên đối với dữ liệu lớn, việc xử lý bằng cách này không hoàn toàn tối ưu. Độ phức tạp của thuật toán này là O(min(A, B)).
Cách tìm ước chung lớn nhất bằng phương pháp trừ
Ý tưởng của thuật toán này là trừ hai số A và B cho nhau cho đến khi hai số này bằng nhau. Khi đó, chúng ta sẽ tìm được ước chung lớn nhất của hai số.
Bước triển khai thuật toán như sau:
- Kiểm tra xem A hoặc B có bằng 0 hay không. Nếu có, trả về tổng của hai số đó.
- Lặp cho đến khi A = B. Trong mỗi vòng lặp, ta thực hiện phép trừ giữa giá trị lớn hơn và giá trị nhỏ hơn.
Với ngôn ngữ C/C++, triển khai thuật toán sẽ như sau:
int gcd(int A, int B) { while (A != B) { if (A > B) { A -= B; } else { B -= A; } } return A; }Đây là cách tối ưu hơn so với thuật toán ban đầu, tuy nhiên vẫn chưa phải là thuật toán tối ưu nhất.
Cách tìm ước chung lớn nhất sử dụng thuật toán Euclid
Thuật toán Euclid là một giải thuật giúp tính ước số chung lớn nhất (ƯCLN) của hai số một cách hiệu quả. Chúng ta sẽ tìm hiểu về thuật toán này và cách tối ưu hóa nó.
Thuật toán Euclid
Thuật toán Euclid được triển khai dựa trên tính chất của ước chung lớn nhất, đó là ƯCLN(A, B) = ƯCLN(B, A%B).
Giả sử chúng ta có hai số A và B. Triển khai thuật toán Euclid sẽ hoạt động như sau:
- Lặp cho đến khi A % B = 0.
- Trong mỗi vòng lặp, A được gán bằng B, và B được gán bằng A%B.
Với ngôn ngữ C/C++, triển khai thuật toán sẽ như sau:
int gcd(int A, int B) { while (B != 0) { int temp = A; A = B; B = temp % B; } return A; }Đây là cách tối ưu nhất để giải các bài toán với dữ liệu lớn. Độ phức tạp của thuật toán này là O(log(max(A, B))).
Thuật toán Euclid mở rộng (Extended Euclidean algorithm)
Thuật toán Euclid mở rộng (Extended Euclidean algorithm) cho phép chúng ta tìm ra hai số nguyên x và y thỏa mãn phương trình Ax + By = ƯCLN(A, B). Đây là một phần mở rộng của thuật toán Euclid.
Độ phức tạp của thuật toán này là O(log(max(A, B)).
Cách tìm ước chung lớn nhất bằng hàm có sẵn trong C/C++
Ngoài việc tự viết các hàm tìm ước chung lớn nhất, chúng ta cũng có thể sử dụng hàm __gcd có sẵn trong thư viện algorithm của C/C++. Đây là cách nhanh nhất để giải bài toán trong C/C++.
#include int gcd(int A, int B) { return __gcd(A, B); } Ngoài tìm ước chung lớn nhất, thư viện algorithm còn cung cấp nhiều hàm hỗ trợ khác cho giải các bài toán như max, min, sort,... Chúng ta có thể tìm hiểu thêm về thư viện này.
Trên đây là phần giới thiệu và triển khai của các thuật toán tìm ước chung lớn nhất. Những thuật toán này rất hữu ích và được sử dụng trong quá trình giải các bài toán tìm kiếm. Hy vọng bài viết sẽ hữu ích cho bạn!