Viết Chương Trình Tìm Ước Chung Lớn Nhất Cài Đặt Với C

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

Bạn đang xem: Viết chương trình tìm ước chung lớn nhất

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

Kết quả:

Có rất là nhiều phương pháp để khắc phục bài toán này, trong nội dung tất cả chúng ta sẽ đi ngang qua 3 phương pháp để triển khai bài toán. Từ đó, lựa chọn ra cách tối ưu nhất.

Có rất là nhiều phương pháp để khắc phục bài toán này, trong nội dung tất cả chúng ta sẽ đi ngang qua 3 phương pháp để triển khai bài toán. Từ đó, lựa chọn ra cách tối ưu nhất.

Nội dung được đăng tại yome.vn

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

Đây là cách dễ dàng nhất để setup thuật toán tìm UCLN. So với thuật toán này tất cả chúng ta sẽ đi lặp lần các giá trị từ min(?, β) về 0 & kiểm soát giá trị một.

Các bước triển khai thuật toán này sẽ như sau: Tất cả chúng ta sẽ sử dùng vòng lặp for đẻ khắc phục bài tòán này.

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

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

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

#include using namespace std;//Hàm tìm ước chung lớn nhấtint UCLN(int ?, int β) { for(int ι = min(?, β); ι > 0; –i) { if (? % ι == 0 && β % ι ==0) return ι; } //Không chạy tới đây vì ?, β luôn chia hết cho 1}int main() { int ?,β; ? = 20; β = 12; cout
Output: 4
Đây là cách dễ dàng nhất để khắc phục bài toán này, nhưng so với dữ liệu lớn việc giải quyết bằng phương pháp này không hoàn toàn tối ưu. Độ cầu kỳ của thuật toán đó là Σ(min(?, β)).

Xem Thêm  Các loại lỗi trong Java với các ví dụ - chúng ta có thể bắt lỗi trong java không

2. Tìm UCLN bằng phương thức trừ

Sáng kiến của thuật toán đó là trừ hai số ? & β cho nhau tới khi hai số này bằng nhau. Hiện thời ta sẽ tìm được ƯCLN của 2 số. Các bước triển khai thuật toán sẽ như sau:

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

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

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

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

100 = 100 – 3070 = 70 – 3040 = 40 – 30//Đến đây là β
Ngoài thực hiện trừ ? & β, tất cả chúng ta có thể thay dấu trừ thành chia dư. Kết quả trả về tương đương.

int UCLN(int ?, int β) { while(? * β != 0) { if (? > β) { ? %= β; }else{ β %= ?; } } return ? + β;}
Đây là thuật toán tối ưu hơn đối 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.

Tham khảo thêm: Viết Về 4 Mùa Bằng Tiếng Anh Nói Về Các Mùa Trong Năm, Các Mùa Trong Năm Bằng Tiếng Anh

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 quả. Trong phần này tất cả chúng ta sẽ đề cập giải thuật ở 2 góc cạnh căn bản & mở rộng.

Xem Thêm  Các hàm xử lý chuỗi trong php - cat chuoi php

Thuật toán Euclid

<Thuật toán Euclidvàgt; là một giải thuật giúp tất cả chúng ta tìm ước chung lớn nhất của 2 số. Nó được triển khai dựa vào thuộc tính của UCLN này là UCLN(?, β) = UCLN(β, Aphần trămB).

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

UCLN(20, 12) = UCLN(12, 20phần trăm12) = UCLN(12, 8)UCLN(12, 8) = UCLN(8, 12phần trăm8) = UCLN(8, 4)UCLN(8, 4) = UCLN(4, 8phần trăm4) = UCLN(4, 0)Vì β = 0 nên UCLN(4, 0) sẽ là 4
Sáng kiến triển khai thuật toán này sẽ quy nạp cho tới khi ? % β = 0. Trình bài bài toán với từ ngữ C/C++ sẽ như sau :

#include using namespace std;int UCLN(int ?, int β) { if (β == 0) return ?; return UCLN(β, Aphần trămB);}int main() { int ?,β; ? = 20; β = 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 đó là Σ(logmax(?,β)).

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

UCLN(?, β) có một thuộc tính khá đặc biệt này là luôn trình diễn được ở dạng Ax + By = UCLN(?, β) trong đó Ҳ, 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 tất cả chúng ta tìm thấy hai số Ҳ & y đáp ứng thuộc tính.

#include using namespace std;int {d}, Ҳ, y;void extendedEuclid(int ?, int β) { if (β == 0) { {d} = ?; Ҳ = 1; y = 0; } else { extendedEuclid(β, Aphần trămB); int temp = Ҳ; Ҳ = y; y = temp – (?/β)*y; }}int main() { extendedEuclid(16, 10); cout
Output: UCLN(20, 12) = 4 Ҳ, y: -1, 2
Độ cầu kỳ của thuật toán đó là Σ(log(max(?,β)).

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, tất cả chúng ta còn tồn tại thể sử dụng hàm __gcd có sẵn trong thư viện algorithm của C/C++.

Xem Thêm  Cách đọc tệp văn bản bằng Python một cách hiệu quả - cách đọc tệp trong python

#include#includeusing namespace std;int main() { int ?,β; ? = 20; β = 12; cout
Output: 4
Đây là cách tốt 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 tồn tại nhiều hàm bổ trợ khác cho giải các bài toán như max, min, sort,…Tất cả chúng ta có thể tìm hiểu thêm về thư viện algorithm.

Trên đây là phần giới thiệu cũng như triển khai của các thuật toán tìm ước chung lớn nhất. Đây cũng là những thuật toán thường được sử dụng cũng như rât hữu hiệu trong tiến trình giải các bài toán tìm kiếm. Rất mong nội dung sẽ hữu hiệu cho bạn !

Σ(log⁡max(?,β))” role=”presentation” style=”box-sizing: border-box; margin: 0px; padding: 0px; display: inline; line-height: normal; font-size: 15px; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; font-family: -apple-system, BlinkMacSystemFont, “Segoe UI”, Helvetica, Arial, sans-serif, “Apple Color Emoji”, “Segoe UI Emoji”, “Segoe UI Symbol”; position: relative;” tabindex=”0″>

O(log⁡max(A,B))” role=”presentation” style=”box-sizing: border-box; margin: 0px; padding: 0px; display: inline; line-height: normal; font-size: 15px; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; font-family: -apple-system, BlinkMacSystemFont, “Segoe UI”, Helvetica, Arial, sans-serif, “Apple Color Emoji”, “Segoe UI Emoji”, “Segoe UI Symbol”; position: relative;” tabindex=”0″>

Comment đã đóng, nếu có khúc mắc hãy đặt thắc mắc tại hoicode.com để admin giải đáp.

Bài sau Bài tiếp

Bài sau Bài tiếp

——————-#####——————-

Khóa học liên quan nổi trội:

DANH SÁCH BÀI HỌC

Mục lục đề tài
MÃ GIẢM GIÁ Unica 50% Lấy Mã TinoHost 30% Lấy Mã INET 30% Lấy Mã

Liên hệ

Coupon

Khóa học

Giới thiệu

Mục lục đề tài

Admin Cường, làm chủ chính của trang web.

2020 – yome.vn. All Right Reserved Theme GoodNews, nền móng Codeigniter, VPS mua tại Tinohost

2020 – yome.vn. All Right Reserved Theme, nền móng, VPS mua tại Tinohost

BÀI VIẾT

Nếu bạn phát hiện lỗi sai backlinks, bài viết sai, hay một lỗi bất kể nào đó trên trang này thì hãy cho mình biết nhé. Cám ơn bạn!

Viết một bình luận