bai toan va thuat toan tiet 4
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (75.32 KB, 2 trang )
<span class='text_page_counter'>(1)</span>Tuần 6 Tiết: 13. Ngày soạn: 03/10/2012 Ngày dạy: 05/10/2012. §4: BÀI TOÁN VÀ THUẬT TOÁN (Tiết 4) I. Mục tiêu: 1) Kiến thức: - HS luyện tập cách xác định bài toán và xây dựng ý tưởng. - HS luện tập cách biểu diễn thuật toán bằng ngôn ngữ liệt kê và sơ đồ khối 2) Kỹ năng: - Xây dựng được thuật toán giải bài toán đơn giản bằng ngôn ngữ liệt kê hoặc sơ đồ khối. 3) Thái độ: - Nghiêm túc trong học tập, say mê môn học II. Chuẩn bị của giáo viên và học sinh. 1) Giáo viên: - SGK, SGV, Bài soạn 2) Học sinh: - Vở ghi, SGK III. Tiến trình bài dạy: 1) Kiểm tra bài cũ: Em hãy cho biết có mấy cách biểu diễn thuật toán? Em hãy mô tả thuật toán sắp xếp bằng tráo đổi? 2) Nội dung: Hoạt động của giáo viên và học sinh Nội dung chính GV: Nêu ví dụ giả sử có một dãy số nguyên khac nhau, và một số nguyên k. hãy cho biết có hay không chỉ số I mà ai=k. Nếu có hãy cho biết chỉ số đó.. Ví dụ 3: Bài toán tìm kiếm Tìm kiếm là việc thường xảy ra trong cuộc sống, chẳng hạn cần tìm cuốn sách giáo khoa tin học 10 trên giá sách, cần tìm một học sinh trong danh sách lớp học,… Nói một cách tổng quát là cần tìm một đối tượng cụ thể nào đó trong tập các đối tượng cho trước. Ví dụ: Cho dãy A gồm các số: 5, 7, 1, 4, 2, 9, 8, 11, 25, 51. Với khóa k = 2, trong dãy trên có số hạng a5 có giá trị bằng k. vậy chỉ số cần tìm là i = 5; Với k = 6 thì không có số hạng nào có giá trị bằng k.. GV: Yêu cầu học sinh xác định bài toán?. *) Thuật toán tìm kiếm tuần tự.
<span class='text_page_counter'>(2)</span> HS: Xác định bài toán như sau: *) Xác định bài toán GV: Yêu cầu học sinh mô tả thuật toán - Input: Dãy A gồm N số nguyên khác theo cách liệt kê? nhau a1, a2, …, aN. - Output: Chỉ số i mà ai = k hoặc thông báo không có số hạng nào của dãy A có giá trị bằng k. b) Sơ đồ khối: Nhập N và a1, a2, .., aN; k i1. ai = k. ii+1 i > N?. Thông báo dãy A không có số hạng có giá trị bằng k rồi kết thúc. *) Ý tưởng: Tìm kiếm tuần tự được thực hiện một cách tự nhiên. Lần lượt từ số hạng thứ nhất, ta so sánh giá trị số hạng đang xét với khóa cho đến khi hoặc gặp một số hạng bằng khóa hoặc dãy đã được xét hết và không có giá trị nào bằng khóa. (Trong trường hợp thứ hai dãy A không có số hạng nào bằng khóa). *) Thuật toán: a) Cách liệt kê: B1: Nhập N, các số hạng a1, a2, …,aN và khóa k; B2: i 1; B3: Nếu ai = k thì thông báo chỉ số I, rồi kết thúc; B4: i i + 1; B5: Nếu i >N thì thông báo dãy A không có số hạng nào có giá trị bằng k, rồi kết thúc; B6: Quay lại bước 3.. 3) Củng cố, luyện tập: - Nhắc lại thuật toán cơ bản: Tìm kiếm tuần tự. 4) Hướng dẫn học sinh tự học ở nhà: Về nhà học bài và làm bài tập ở nhà. IV.Rút kinh nghiệm: …………………………………………………………………………………………… …………………………………………………………………………………………… …………………………………………………..
<span class='text_page_counter'>(3)</span>
