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 =
12 trang |
Chia sẻ: quynhsim | Lượt xem: 725 | Lượt tải: 0
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 DOWNLOAD ở trên
Trường THPT Phan Đỡnh Phựng – Hà NộiBà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.Trường THPT Phan Đỡnh Phựng – Hà NộiHã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? Trường THPT Phan Đỡnh Phựng – Hà NộiBài 6. Giải bài toán trên máy tínhTrường THPT Phan Đỡnh Phựng – Hà NộiCá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ụ: Trường THPT Phan Đỡnh Phựng – Hà NộiBướ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ụ: Trường THPT Phan Đỡnh Phựng – Hà Nộib. 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. Trường THPT Phan Đỡnh Phựng – Hà NộiĐĐ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) = 5MNTrường THPT Phan Đỡnh Phựng – Hà NộiĐĐ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) = 5MNTrường THPT Phan Đỡnh Phựng – Hà NộiBướ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. Trường THPT Phan Đỡnh Phựng – Hà NộiBướ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.Trường THPT Phan Đỡnh Phựng – Hà NộiBướ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.Trường THPT Phan Đỡnh Phựng – Hà NộiBướ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:
- adfasd.ppt