§ 4: BÀI TOÁN VÀ THUẬT TOÁN
(Tiếtt 5)

-Mục đích - yêu cầu:
Kiến thức: -Hiểu và thực hiện được thuật toán trong SGK bài toán tìm kiếm tuần tự
Kỹ năng: - áp dụng thuật toán tìm kiếm tuần tự để giải một số bài toán đơn giản.
Tháí độ: - Yêu thích môn học, ham học hỏi.
Phương pháp dạy học: - phương pháp tích cực, gợi mở, đối thoại.
Phương tiện dạy học: - Giáo án, SGK, SGV, phấn, thước, máy tính, máy chiếu
Nội dung các bước lên lớp:
ổn định tổ chức lớp: (1’)
kiểm tra bài cũ: (10’) GV đặt câu hỏi và gọi HS lên bảng trả lời Câu hỏi: Em hãy nêu ý tưởng của thuật toán sắp xếp tráo đổi? áp dung thuật toán để sắp xếp dãy số sau theo chiều tăng dần: 3 5 9 8 1 7 ( Chiếu Slide 1 - câu hỏi kiểm tra bài cũ ). HS: Trả lời câu hỏi. HS dưới lớp theo dõi bạn trả lời và nhận xét. GV: chiếu Slide 2 + 3 - Đáp án và nhận xét cho điểm.
Dạy bài mới: (30’) * Đặt vấn đề: Trong thực tế nhiều khi ta hay phải tìm kiếm một thứ gì đó như tra từ điển, tìm sách ở trên giá sách, tìm tên HS trong sổ điểm. Bài hôm nay chúng ta cùng tim hiểu một số dạng bài toán tìm kiếm và xem trong tin học sẽ xử lý các bài toán đó như thế nào?
Hoạt động 1: Tìm hiểu về bài toán tìm kiếm (10’)

Hoạt động của giáo viên
Hoạt động của học sinh

GV (Chiếu slide số 5): Ví dụ 3. Bài toán tìm kiếm
Bài toán:
Cho dãy A gồm N số nguyên khác nhau a1, a2aN và một số nguyên k.
Kiểm tra trong dãy trên có chỉ số i (1<=i<=N) mà ai=k hay không? nếu có thì hãy đưa ra chỉ số đó. GV giải thích: Số nguyên k được gọi là khoá tìm kiếm gọi tắt là khoá. Giả sử ta có dãy sau: 5 7 1 4 2 9 8 11 25 51 và k = 2 thì ta phải đưa ra kết luận là tại chỉ số i = 5 thì a5 = k hoặc k = 6 thì ta đưa ra kết luận là trong dãy không có số hạng nào của dãy có giá trị bằng k. GV: Cô có trò chơi như sau: (Chiếu Slide số 6)

GV: Bài toán tìm kiếm có 2 thuật toán: tìm kiếm tuần tự và tìm kiếm nhị phân. Sau đây chúng ta đi nghiên cứu thuật toán tìm kiếm tuần tự.

 - HS quan sát, nghe giảng
- HS: Quan sát và trả lời câu hỏi.

 Hoạt động 2: Xây dựng thuật toán tìm kiếm tuần tự (20’)


Hoạt động của giáo viên
Hoạt động của học sinh

Xác định bài toán :
GV : Dựa vào bài toán dã nêu ở trên em hãy xác định Input và Output của bài toán?.

GV : Nhận xét và bổ xung (chiếu Slide số 7) :

GV ( Chiếu Slide số 8). Từ ví dụ yêu cầu HS nêu ý tưởng về việc giải bài toán trên.
GV: