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

CHÀO MỪNG QUÝ THẦY - CÔ GIÁO VỀ DỰ GIỜ THĂM LỚP Sốp Cộp, ngày 28 tháng 10 năm 2014 LỚP 10B3 Cho bài toán: 	Hãy tìm ước số chung lớn nhất (ƯSCLN) của hai số nguyên dương M và N? Với: 	1) M=5; N=10;	(Nhóm 1) 	2) M=15; N= 20;	(Nhóm 2) 	3) M=97; N=65;	(Nhóm 3) 	4) M=240; N=450;	(Nhóm 4) Các nhóm ghi kết quả vào phiếu! Em có nhận xét gì về cách sử dụng máy tính để giải bài toán? Đứng trước một bài toán ta cần làm gì (hay quan tâm đến các yếu tố (thành phần) nào)? Bài toán: Cho dãy A gồm N số nguyên khác nhau: a1,a2,…,aN và một số nguyên k. Cần biết có hay không chỉ số i (1≤ i ≤N) mà ai=k. Nếu có hãy cho biết chỉ số đó. (Ví dụ 3. Bài toán tìm kiếm- SGK trang40) Hãy xác định bài toán trên? Xác định bài toán: - Input: Dãy A gồm N số nguyên khác nhau: a1,a2,…,aN và một số nguyên k; - Output: Chỉ số i mà ai=k hoặc thông báo dãy A không có số hạng nào có giá trị bằng k. Mô phỏng thuật toán: Với N=8 và k=19 Với i=6 thì ai=19. Ở lần duyệt thứ 2 thì aGiua =k=19. Vậy chỉ số cần tìm là i = Giua = 6 Tìm kiếm nhị phân Tìm kiếm tuần tự Mô phỏng thuật toán: Với N=8 và k=10 Với mọi i từ 1 đến 8 không có giá trị bằng 10. Ở lần duyệt thứ 4 thì Dau> Cuoi nên kết luận trong dãy A không có số hạng nào có giá trị là 10. Tìm kiếm nhị phân Tìm kiếm tuần tự Ví dụ (SGK Trang 48): Tìm ước chung lớn nhất (ƯCLN) của hai số nguyên dương M và N. *) Thuật toán bằng cách liệt kê các bước: 	Bước 1: Nhập M, N; 	Bước 2: Nếu M = N thì đưa ra ƯCLN(M,N) = M rồi kết thúc; 	Bước 3: Nếu M > N thì M ← M – N rồi quay lại bước 2; 	Bước 4: N ← N – M rồi quay lại bước 2. Mô phỏng việc thực hiện thuật toán: Tìm ƯSCLN(M,N)=? Với: 	M=10; N=25: M=10 N=25 N←N-M M=10 N=15 Lần duyệt thứ 1 N←N-M Lần duyệt thứ 2 M=10 N=5 M←M-N Lần duyệt thứ 3 M=5 N=5 =>ƯSCLN(10,25)= 5 Kết quả Nhập M và N Sơ đồ khối M=N? M>N? N←N-M M←M-N Đưa ra M rồi kết thúc Sai Sai Đúng Đúng Thuật toán: Tìm ước số chung lớn nhất của hai số nguyên dương M,N. Tài liệu phải mô tả đầy đủ và giải thích chi tiết về: Bài toán: Input và Output là gì? Thuật toán: 	 	+) Có những thuật toán nào khả thi? 	+) cuối cùng thuật toán được chọn là gì? 	+) Vì sao chọn thuật toán đó? 	+) Các bước thực hiện nó ra sao? 	… Thiết kế chương trình: Sử dụng ngôn ngữ lập trình nào? Kết quả thử nghiệm? - Hướng dẫn sử dụng. Câu hỏi củng cố Hãy ghép các đặc điểm tương ứng ở cột bên phải với các bước thực hiện giải bài toán trên máy tính ở cột bên trái? Đáp án đúng: 	 Trân trọng cảm ơn.