Hiểu cách biểu diễn thuật toán bằng sơ đồ khối và bằng liệt kê các bước. – Hiểu một số thuật toán thông dụng. Kĩ năng: – Biết xây dựng thuật toán của một số bài toán đơn giản. Thái độ: – Luyện khả năng tư duy lôgic khi giải quyết một vấn đề nào đó. | Bài 4 BÀI TOÁN VÀ THUẬT TOÁN tt I. MỤC TIÊU Kiến thức - Hiểu cách biểu diễn thuật toán bằng sơ đồ khối và bằng liệt kê các bước. - Hiểu một số thuật toán thông dụng. Kĩ năng - Biết xây dựng thuật toán của một số bài toán đơn giản. Thái độ - Luyện khả năng tư duy lôgic khi giải quyết một vấn đề nào đó. II. CHUẨN BỊ Giáo viên - Giáo án bảng vẽ sơ đồ khối - Tổ chức hoạt động nhóm. Học sinh SGK vở ghi. Đọc bài trước. III. HOẠT ĐÔNG DẠY - HỌC 1. Ổn định tổ chức Kiểm tra sĩ số lớp. 2. Kiểm tra bài cũ Hỏi Nêu ý tưởng thuật toán sắp xếp bằng tráo đổi Đáp Ý tưởng Với mỗi cặp số hạng đứng liền kề trong dãy nếu số trước lớn hơn số sau thì ta đổi chỗ chúng cho nhau. Việc đó được lặp lại cho đến khi không có sự đổi chỗ nào xảy ra nữa 3. Bài mới Hoạt động 1 Hướng dẫn tim thuật toán giải bài toán Nội dung Hoạt động của Giáo viên Hoạt động của Học sinh III. Một số ví dụ tt 3. Ví dụ 3 Bài toán tìm kiếm 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ố đó. a Thuật toán tìm kiếm tuần tự sequential search Xác định bài toán Đặt vấn đề Tìm kiếm là một việc thường xảy ra trong cuộc sống. Cho dãy A gồm 5 7 1 4 2 9 8 11 25 51. Tìm i với ai 2 Tổ chức các nhóm thảo luận i 5 Các nhóm thảo luận - Input Dãy A gồm N số nguyên khác nhau a1 a2 . aN và số nguyên k - 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. Ý tưởng - Tìm kiếm tuần tự là 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 khoá cho đến khi hoặc gặp một số hạng bằng khoá hoặc dãy đã được xét hết và không có giá trị nào bằng khoá. Trong trường hợp thứ hai dãy A không có số hạng nào bằng khoá. Thuật toán H. Hãy xác định bài toán GV hướng dẫn HS tìm thuật toán giải bài toán. đưa ra ý kiến Đ. Input N a1 a2 . aN k Output i hoặc thông báo không có i Cho các nhóm trình bày ý .
