Show  Làm quen cách viết các chương trình đơn giản, cách sử dụng: Mô tả bài toánViết chương trình nhập vào 2 số nguyên dương a và b. Tìmước số chung lớn nhất và bội số chung nhỏ nhất của a và b. Bạn đang xem: Thuật toán ước chung lớn nhất
a. Lựa chọn thuật toán Lựa chọn một thuật toán tối ưu. Ví dụ: Nếu M = N - Đúng ƯCLN = M (hoặc N) ? Kết thúc; - Sai Xét: nếu M > N - Đúng ? M = M – N; - Sai N = N – M; Quá trình này được lặp lại cho đến khi M = N. Bạn đang xem nội dung tài liệu Bài toán đặt vấn đề Tìm ước số chung lớn nhất (ưcln) của hai số nguyên dương M và N, để tải tài liệu về máy bạn click vào nút TẢI VỀ ở trên Bài toán đặt vấn đề Với các giá trị: M = 25; N = 5. M = 88; N = 121. M = 997; N = 29. M = 2006; N=1998.Tìm ước số chung lớn nhất (ưCLN) của hai số nguyên dương M và N.Hãy chỉ ra những ưu điểm của việc giải bài toán bằng máy tính so với cách giải toán thông thường? Bài 6. Giải bài toán trên máy tínhCác bước thực hiện Bước 1: Xác định bài toán Xác định hai thành phần INPUT, OUTPUT.INPUT: M , N là hai số nguyên dương.OUTPUT: ưCLN(M, N).Ví dụ: Bước 2: Lựa chọn hoặc thiết kế thuật toán Nếu M = N - Đúng ưCLN = M (hoặc N) Kết thúc; - Sai Xét: nếu M > N - Đúng M = M – N; - Sai N = N – M; Quá trình này được lặp lại cho đến khi M = N. a. Lựa chọn thuật toán Lựa chọn một thuật toán tối ưu.Ví dụ: b. Diễn tả thuật toán Theo hai cách: Cách 1: Liệt kê các bước. Cách 2: Vẽ sơ đồ khối.Cách 1: Liệt kê các bước B1: Nhập M, N;B2: Nếu M = N lấy ưCLN = M (hoặc N), chuyển đến B5;B3: Nếu M >N thì M M - N rồi quay lại B2; B4: N N – M rồi quay B2;B5: Đưa ra kết quả ưCLN; Kết thúc. ĐĐSSCách 2: Diễn tả thuật toán bằng sơ đồ khối 5101010551525321LượtNhập M ,NM =N ?M > N ?N N - MM M - NĐưa ra M ; Kết thúc M= 25, N = 1025 = 10 ?25 >10M 25 - 1015 = 10 ?15 >10M 15 - 105 = 10 ?5 > 10 ?N = 10 - 55 = 5 ?ƯSLN (25,10) = 5MNNhập M,NM=N?M>N?Đưa ra M, kết thỳcM←M-NN←N-MM=25,N=1025=10?25>10?15←25-10ĐĐSSMô phỏng thuật toán tìm ƯCLN5101010551525321LượtNhập M ,NM =N ?M > N ?N N - MM M - NĐưa ra M ; Kết thúc M= 25 ,N = 1025 = 10 ?25 >10M 25 - 1015 = 10 ?15 >10M 15 - 105 = 10 ?5 > 10 ?N = 10 - 55 = 5 ?ƯCLN (25,10) = 5MNBước 3: Viết chương trình Sử dụng ngôn ngữ lập trình để diễn đạt đúng thuật toán. Là tổng hợp giữa việc: Lựa chọn cách tổ chức dữ liệu. Bước 4: Hiệu chỉnh TEST:M = 8; N = 8 ưCLN = 8M = 25; N = 10 ưCLN = 5M = 88; N = 121 ưCLN = 11M = 17; N = 13 ưCLN = 1Thử chương trình bằng cách thực hiện nó với một số bộ INPUT tiêu biểu (TEST) để kiểm tra kết quả, nếu có sai sót thì hiệu chỉnh lại.Bước 5: Viết tài liệuMô tả chi tiết về bài toán, thuật toán, chương trình và kết quả thử nghiệm, hướng dẫn cách sử dụng. Từ tài liệu này, người sử dụng đề xuất các khả năng hoàn thiện thêm.Bước 2: Lựa chọn hoặc thiết kế thuật toán. Bước 1: Xác định bài toán. Bước 3: Viết chương trình. Bước 4: Hiệu chỉnh.Bước 5: Viết tài liệu.Các bước giải bài toán trên máy tính File đính kèm:
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à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 = 12 Output : 4 Có rất nhiều cách để giải quyết bài toán này, trong bài viết chúng ta sẽ đi qua 3 cách để triển khai bài toán. Từ đó, lựa chọn ra cách tối ưu nhất. Bài viết này được đăng tại [free tuts .net] 1. Tìm UCLN sử dụng vòng lặpĐây là cách đơn giản nhất để cài đặt thuật toán tìm UCLN. Đối với thuật toán này chúng ta sẽ đi lặp lần các giá trị từ min(A, B) về 0 và kiểm tra giá trị một. Các bước triển khai thuật toán này sẽ như sau: Chúng ta sẽ sử dùng vòng lặp for đẻ giải quyết bài tòán này.
Trình bài bài toán với ngôn ngữ C/C++ sẽ như sau : #include <bits/stdc++.h> using namespace std; //Hàm tìm ước chung lớn nhất int 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 << UCLN(A, B); } Đâ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 triển khai thuật toán sẽ như sau:
Trình bài bài toán với ngôn ngữ C/C++ sẽ như sau : #include <bits/stdc++.h> using namespace std; //Hàm tìm UCLN int 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 << UCLN(A, B); } Thuật toán sẽ thực hiện lần lượt các bước như sau. Giả sử A = 100, B = 30. 100 = 100 - 30 70 = 70 - 30 40 = 40 - 30 //Đến đây là B < A nên nó sẽ lấy B = B - A 30 = 30 - 10 20 = 20 - 10 A = B = 10 reutrn 10 Ngoài thực hiện trừ A và B, chúng ta có thể thay dấu trừ thành chia dư. Kết quả trả về tương tự. 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 EuclidGiả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 chúng ta sẽ đề cập giải thuật ở 2 khía cạnh cơ bản và mở rộng. Thuật toán Euclid[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 <bits/stdc++.h> 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 << UCLN(A, B); } Đâ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 <bits/stdc++.h> 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 << "UCLN(16, 10) = " << d << endl; cout << "x, y: " << x << ", " << y << endl; return 0; } 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)). 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<iostream> #include<algorithm> using namespace std; int main() { int A,B; A = 20; B = 12; cout << __gcd(A, B); } Đâ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 hỗ trợ khác cho giải các bài toán như max, min, sort,...Chúng ta có thể tham khảo 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 hay được sử dụng cũng như rât hữu ích trong quá trình giải các bài toán tìm kiếm. Rất mong bài viết sẽ hữu ích cho bạn !
|
