Trong bài viết này, chúng ta sẽ cùng tìm hiểu về thuật toán tìm ước chung lớn nhất trong ngôn ngữ lập trình C++. Chúng ta sẽ khám phá cách triển khai thuật 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 loại trừ.
Hình ảnh minh họa
Tìm hiểu về bài toán
Chúng ta sẽ bắt đầu bài viết với đề bài của bài toán này. Đề bài yêu cầu chúng ta nhập vào 2 số nguyên A và B, sau đó viết chương trình để tìm ước chung lớn nhất của hai số đó.
Cách triển khai thuật toán
Bài toán này có rất nhiều cách để giải quyết, trong bài viết này chúng ta sẽ đi qua 3 cách triển khai phổ biến nhất và lựa chọn cách tối ưu nhất.
1. Tìm ước chung lớn nhất sử dụng vòng lặp
Cách đơn giản nhất để cài đặt thuật toán tìm ước chung lớn nhất là sử dụng vòng lặp. Đối với thuật toán này, chúng ta sẽ lặp từ min(A, B) về 0 và kiểm tra giá trị tại mỗi bước lặp.
Các bước triển khai thuật toán này như sau:
- Sử dụng vòng lặp for để giải quyết bài toán.
- Lặp từ min(A, B) về 0.
- Với mỗi bước lặp, kiểm tra xem A và B có chia hết cho i hay không? Nếu chia hết, trả về giá trị i.
Việc xử lý bài toán bằng cách này đơn giản, tuy nhiên đối với các dữ liệu lớn, cách triển khai 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)).
2. Tìm ước chung lớn nhất bằng phương pháp loại 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 đã tìm được ước chung lớn nhất của 2 số.
Cách 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 bằng 0, trả về ước chung lớn nhất là A+B và dừng chương trình.
- Lặp cho đến khi A = B. Trong mỗi bước lặp, giảm giá trị lớn hơn của A và B đi giá trị nhỏ hơn của chúng.
Thuật toán này tương đối tối ưu hơn so với thuật toán trước, tuy nhiên chưa phải là tối ưu nhất.
3. 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 hiệu quả giúp tính ước số chung lớn nhất của hai số. Trong phần này, chúng ta sẽ tìm hiểu về giải thuật Euclid ở hai khía cạnh cơ bản và mở rộng.
Thuật toán Euclid
Thuật toán Euclid giúp chúng ta tìm ước chung lớn nhất của hai số. Nó được triển khai dựa trên tính chất của ước chung lớn nhất (UCLN) đó là UCLN(A, B) = UCLN(B, A%B).
Giả sử chúng ta có hai số A = 20 và B = 12. Áp dụng thuật toán Euclid, chúng ta thực hiện các bước sau đây:
- Bước 1: Tính A%B = 8.
- Bước 2: Tính B%(A%B) = 4.
- Bước 3: Tính (A%B)%(B%(A%B)) = 0.
Thuật toán này là phương pháp tốt nhất để giải quyết 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
UCLN(A, B) có một tính chất đặc biệt, đó là luôn có thể biểu diễn được dưới dạng Ax + By = UCLN(A, B) trong đó x và y là hai số nguyên. Đây là phần mở rộng của thuật toán Euclid cho phép chúng ta tìm ra hai số x và y thỏa mãn tính chất này.
Độ phức tạp của thuật toán Euclid mở rộng cũng là O(log(max(A, B)).
4. Tìm ước chung lớn nhất bằng hàm có sẵn trong C/C++
Ngoài cách 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 ngôn ngữ C/C++. Đây là cách nhanh nhất để giải bài toán trong C/C++.
Ngoài việc 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 như max, min, sort,... Chúng ta có thể tham khảo thêm về thư viện algorithm để biết thêm chi tiết.
Đâ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. Các thuật toán này rất hữu ích và được sử dụng phổ biến trong quá trình giải các bài toán tìm kiếm. Hy vọng bài viết đã hữu ích cho bạn!
