Tìm Ước Chung Lớn Nhất Trong C

     

Trong bài này chúng ta sẽ tìm hiểu thuật toán tìm ước chung lớn nhất trong C++, bằng cách sử dụng vòng lặp, thuật toán Euclid và thuật toán loại trừ.

Bạn đang xem: Tìm ước chung lớn nhất trong c

*

*

Bài viết này được đăng tại

freetuts.net


, không được copy dưới mọi hình thức.

Đề bài: Nhập vào 2 số nguyên A và B, viết chương trình tìm ứng chung lớn nhất của 2 số đó.

Kết quả:

Input : A = 20, B = 12Output : 4Có rất nhiều cách để xử lý bài toán này, trong bài viết tất cả chúng ta sẽ đi qua 3 cách để tiến hành bài toán. Từ đó, lựa chọn ra cách tối ưu nhất .


1. Tìm UCLN sử dụng vòng lặp

Đây là cách đơn thuần nhất để setup thuật toán tìm UCLN. Đối với thuật toán này tất cả chúng ta sẽ đi lặp lần những giá trị từ min ( A, B ) về 0 và kiểm tra giá trị một .Các bước tiến hành thuật toán này sẽ như sau : Chúng ta sẽ sử dùng vòng lặp for đẻ xử lý bài tòán này .

Lặp từ min(A,B) về 0.Với mỗi vòng lặp kiểm tra A và B có chia hết cho i hay không? Nếu chia hết trả về i.

Trình bài bài toán với ngôn từ C / C + + sẽ như sau :

#include using namespace std;//Hàm tìm ước chung lớn nhấtint UCLN(int A, int B) { for(int i = min(A, B); i > 0; --i) { if (A % i == 0 && B % i ==0) return i; } //Không chạy tới đây vì A, B luôn chia hết cho 1}int main() { int A,B; A = 20; B = 12; cout Output: 4Đây là cách đơn giản nhất để giải quyết bài toán này, nhưng đố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)).

2. Tìm UCLN 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 tới khi hai số này bằng nhau. Lúc này ta sẽ tìm được ƯCLN của 2 số. Các bước tiến hành thuật toán sẽ như sau :

Kiểm tra liệu rằng A hoặc B có bằng 0 hay không ? Nếu bằng 0 trả về ƯCLN là A+B. Dừng chương trình.Lặp cho tới khi A = B. Với mỗi vòng lặp thì biến biến max(A, B) = giá trị max(A, B) – giá trị min(A, B).

Trình bài bài toán với ngôn từ C / C + + sẽ như sau :

#include using namespace std;//Hàm tìm UCLNint UCLN(int A, int B) { //Nếu A hoặc B = 0 thì UCLN = A+ B if (A == 0 || B == 0) return A + B; //Lặp cho tới khi A = B while(A != B) { //Lấy số lớn trừ số bé. if (A > B) { A -= B; }else{ B -= A; } } // Trả về UCLB // Lúc này A = B nên return về A hay B đều giống nhau return A;}int main() { int A,B; A = 20; B = 12; cout Output: 4Thuật toán sẽ thực hiện lần lượt các bước như sau. Giả sử A = 100, B = 30.

Xem thêm: Câu 28: Trong Access, Muốn Thay Đổi Khóa Chính Trong Bảng Ta Thực Hiện : D

100 = 100 - 3070 = 70 - 3040 = 40 - 30//Đến đây là B Ngoài thực thi trừ A và B, tất cả chúng ta hoàn toàn có thể thay dấu trừ thành chia dư. Kết quả trả về tựa như .

int UCLN(int A, int B) { while(A * B != 0) { if (A > B) { A %= B; }else{ B %= A; } } return A + B;}Đây là thuật toán tối ưu hơn so với thuật toán ban đầu, nhưng đây chưa phải là thuật toán tối ưu nhất.


3. Tìm UCLN sử dụng thuật toán Euclid

Giải thuật Euclid, hay Thuật toán Euclid, là một giải thuật giúp tính ước số chung lớn nhất ( ƯSCLN ) của hai số một cách hiệu suất cao. Trong phần này tất cả chúng ta sẽ đề cập giải thuật ở 2 góc nhìn cơ bản và lan rộng ra .


Thuật toán Euclid

là một giải thuật giúp chúng ta tìm ước chung lớn nhất của 2 số. Nó được triển khai dựa trên tính chất của UCLN đó là UCLN(A, B) = UCLN(B, A%B).

Giả sử chúng ta có 2 số A = 20, B = 12. Triển khai bằng thuật toán Euclid sẽ hoạt động như sau.

UCLN(20, 12) = UCLN(12, 20%12) = UCLN(12, 8)UCLN(12, 8) = UCLN(8, 12%8) = UCLN(8, 4)UCLN(8, 4) = UCLN(4, 8%4) = UCLN(4, 0)Vì B = 0 nên UCLN(4, 0) sẽ là 4Ý tưởng triển khai thuật toán này sẽ quy nạp cho tới khi A % B = 0. Trình bài bài toán với ngôn ngữ C/C++ sẽ như sau :

#include using namespace std;int UCLN(int A, int B) { if (B == 0) return A; return UCLN(B, A%B);}int main() { int A,B; A = 20; B = 12; cout Output: 4Đâ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(logmax(A,B)).

Thuật toán Euclid mở rộng (Extended Euclidean algorithm)

UCLN(A, B) có một tính chất khá đặc biệt đó là luôn biểu diễn được ở dạng Ax + By = UCLN(A, B) trong đó x, y là hai số nguyên. Đây là một 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.

#include using namespace std;int d, x, y;void extendedEuclid(int A, int B) { if (B == 0) { d = A; x = 1; y = 0; } else { extendedEuclid(B, A%B); int temp = x; x = y; y = temp - (A/B)*y; }}int main() { extendedEuclid(16, 10); cout Output: UCLN(20, 12) = 4 x, y: -1, 2Độ phức tạp của thuật toán này là O(log(max(A,B)).

Xem thêm: Thế Nào Là Khả Năng Hấp Phụ Của Đất Là Gì, Khả Năng Hấp Phụ Của Đất 1

4. Tìm UCLN bằng hàm có sẵn trong C/C++

Ngoài cách tự viết các hàm tìm uớc chung lớn nhất, chúng ta còn có thể sử dụng hàm __gcd có sẵn trong thư viện algorithm của C/C++.

#include#includeusing namespace std;int main() { int A,B; A = 20; B = 12; cout Output: 4Đây là cách nhanh nhất để giải bài toán trong C / C + +, ngoài tìm ước chung lớn nhất thư viện algorithm còn có nhiều hàm tương hỗ khác cho giải những bài toán như max, min, sort, ... Chúng ta hoàn toàn có thể tìm hiểu thêm thêm về thư viện algorithm .Trên đây là phần ra mắt cũng như tiến hành của những thuật toán tìm ước chung lớn nhất. Đây cũng là những thuật toán hay được sử dụng cũng như rât hữu dụng trong quy trình giải những bài toán tìm kiếm. Rất mong bài viết sẽ có ích cho bạn !