Bài giảng Môn Tin học lớp 10 - Bài 6: Giải các bài toán trên máy tính

Click to edit Master title style Click to edit Master text styles Second level Third level Fourth level Fifth level 11/4/2014 ‹#› GiẢI BÀI TOÁN TRÊN MÁY TÍNH Em hãy nêu các bước làm một bài toán trên giấy? 1. Xác định giả thiết, kết luận 2. Lựa chọn hoặc thiết kế cách giải 3. Viết lời giải 4. Chỉnh sửa sai sót 5. Nộp bài Các bước giải một bài toán trên giấy Các bước giải một bài toán trên máy tính 1. Xác định bài toán 2. Lựa chọn hoặc thiết kế thuật toán 3. Viết chương trình 4. Hiệu chỉnh 5. Viết tài liệu 1. Xác định bài toán Xác định mối quan hệ giữa Input và Output. Xác định Input Xác định Output Ví dụ: Tìm UCLN của hai số nguyên dương M và N 	Input: Số nguyên dương M,N 	Output: UCLN của M và N 	Mối quan hệ: UCLN là số nguyên dương lớn nhất mà M và N cùng chia hết. Một bài toán có thể có bao nhiêu thuật toán để giải? Bài toán Có thể có nhiều thuật toán để giải Chỉ giải một bài toán Một thuật toán có thể giải bao nhiêu bài toán?  ta cần chọn hoặc thiết kế thuật toán tốt nhất. 2. Lựa chọn hoặc thiết kế thuật toán Đây là bước quan trọng nhất để giải một bài toán. a. Lựa chọn hoặc thiết kế thuật toán Lựa chọn thuật toán - Khi có từ một thuật toán trở lên. Thiết kế thuật toán khi chưa có thuật toán. Thuật toán 1: Sử dụng phép trừ Nếu M=N thì UCLN(M,N)=N Nếu MN thì UCLN(M,N)=UCLN(M-N,N) Ví dụ 1: Tìm UCLN của hai số nguyên dương M, N Thuật toán 2: Sử dụng phép chia Nếu M chia hết cho N thì UCLN(M,N)=N Nếu MN thì LN(M,N)=UCLN(N,phần dư của M chia N) M = 30, N = 8 M = 30, N = 8 UCLN(30,8) = UCLN(8,6) UCLN(8,6) = UCLN(6,2); UCLN(6,2) = 2; UCLN(30,8) = UCLN(22,8) UCLN(22,8) = UCLN(14,8) UCLN(14,8) = UCLN(6,8) UCLN(6,8) = UCLN (6,2) UCLN(6,2) = UCLN(4,2) UCLN(4,2) = UCLN (2,2) UCLN(2,2) = 2 Tiêu chí thời gian Tiêu chí lựa chọn thuật toán + Thời gian + Hiệu quả về không gian + Tính khả thi khi cài đặt thuật toán b. Diễn tả thuật toán Ví dụ: Tìm ƯCLN của hai số nguyên dương M và N Bước 1: Nhập M, N; Bước 2: Nếu M =N thì xuất N rồi kết thúc; Bước 3: Nếu MN M←M-N N←N-M Xuất M và kết thúc. Đ S Đ S Liệt kê Sơ đồ khối 3. Viết chương trình Viết chương trình trong NNLT nào ta cần phải tuân theo đúng quy định ngữ pháp của NNLT đó Lựa chọn cấu trúc dữ liệu và NNLT để mô tả các thao tác của thuật toán. Thử lại chương trình bằng cách thực hiện bài toán với một số bộ Test tiêu biểu nếu sai thì sửa sau đó thử lại Test là các bộ input tiêu biểu mà đã biết trước Output 4. Hiệu chỉnh Ví dụ: Với chương trình giải phương trình bậc 2: 	ax2 + bx + c =0 (a≠0) Ta có bộ test là các trường hợp a, b, c làm cho 	∆ > 0 ; ∆ =0; ∆ 4 và N là số nguyên tố Input : N=1 Output: không là số nguyên tố Input: N=2 Output: Là số nguyên tố 	Input: N=11 	Output: là số nguyên tố 	Input: N=12 	Output: không là số nguyên tố Input: N=3 Output: Là số nguyên tố Test 2. Trường hợp N=3	 Test 5. Trường hợp N>4 và N không là số nguyên tố 5. Viết tài liệu Mô tả chi tiết bài toán, thuật toán, thiết kế chương trình, kết quả thử nghiệm và hướng dẫn sử dụng. Các bước giải bài toán trên máy tính 1. Xác định bài toán 2. Lựa chọn hoặc thiết kế thuật toán 3. Viết chương trình 4. Hiệu chỉnh 5. Viết tài liệu Câu hỏi trắc nghiệm Câu 1: Giải bài toán trên máy tính được tiến hành qua mấy bước? A. 2 bước	B. 3 bước	 C. 4 bước	 D. 5 bước Câu 2: Tiêu chí lựa chọn hoặc thiết kế thuật toán là? Hiệu quả về thời gian	B. Hiệu quả về không gian C. Khả thi khi cài đặt	D. Tất cả đều đúng Câu 3: Viết chương trình là? A. Biểu diễn thuật toán	 B. Dùng NNLT để diễn đạt bài toán C. Dùng NNLT và cấu trúc dữ liệu thích hợp để diễn tả thuật toán D. Tất cả đều đúng D. 5 bước D. Tất cả đều đúng C. Dùng NNLT và cấu trúc dữ liệu thích hợp để diễn tả thuật toán