Trong bài viết này, chúng ta sẽ khám phá "Thuật toán tìm ước chung lớn nhất trong C / C++" thông qua việc áp dụng kiến thức toán học cơ bản và kỹ năng lập trình. Cùng nhau tìm hiểu cách giải quyết bài toán này và sử dụng thuật toán thích hợp nhé!
Tìm hiểu về ước chung lớn nhất (UCLN)
Ứng dụng từ lý thuyết số, UCLN của hai số là số lớn nhất mà cả hai số đều chia hết cho nó. Ví dụ, với hai số 10 và 20, UCLN của chúng là 10, vì cả hai số đều chia hết cho 10.
Thuật toán tìm ước chung lớn nhất trong C / C++
Để giải quyết bài toán này, chúng ta có thể áp dụng nhiều cách thức khác nhau. Tiếp theo, mình sẽ giới thiệu hai cách đơn giản nhất để bạn có thể lựa chọn và sử dụng.
Tìm UCLN bằng vòng lặp for
Dưới đây là thuật toán tìm ước chung lớn nhất trong C / C++ sử dụng vòng lặp for, là cách tiếp cận cơ bản khi làm việc với vòng lặp.
Giải thích thuật toán:
- Khai báo biến
hcfđể lưu kết quả là UCLN của hàm trả về. - Sử dụng vòng lặp for để lặp từ 1 đến A hoặc từ 1 đến B, với bước nhảy
i++. - Bên trong vòng lặp, nếu A và B đều chia hết cho
i, gánhcf = i. Tiếp tục cho đến khi kết thúc vòng lặp, ta đượchcflà UCLN.
Tìm UCLN bằng cách sử dụng hàm có sẵn
Ngoài cách sử dụng vòng lặp for, chúng ta cũng có thể sử dụng hàm __gcd() có sẵn trong thư viện
Ví dụ, để tìm UCLN của hai số A = 10 và B = 20, chúng ta chỉ cần sử dụng hàm __gcd(A, B).
Áp dụng thuật toán tìm ước chung lớn nhất trong C / C++
Trong phần này, chúng ta sẽ áp dụng thuật toán tìm ước chung lớn nhất trong C / C++ để viết chương trình tìm UCLN của hai số do người dùng nhập. Để bạn có thể lựa chọn, mình sẽ áp dụng cả hai thuật toán.
Ví dụ 1: Tìm UCLN của hai số do người dùng nhập sử dụng vòng lặp for.
//Chương trình CKết quả:
//Chương trình C++Kết quả:
Ví dụ 2: Tìm UCLN của hai số do người dùng nhập sử dụng hàm có sẵn.
//Chương trình C++Kết quả:
Như vậy, chúng ta đã cùng nhau tìm hiểu về thuật toán tìm ước chung lớn nhất trong C / C++. Hãy luyện tập cùng nhiều ví dụ khác nhau để có thể sử dụng thuật toán một cách thành thạo. Chúc bạn thành công!
