Bài giảng Tin học Lớp 7 (Cánh diều) - Chủ đề F: Giải quyết vấn đề với sự trợ giúp của máy tính - Bài 1: Tìm kiếm tuần tự

Nội dung text: Bài giảng Tin học Lớp 7 (Cánh diều) - Chủ đề F: Giải quyết vấn đề với sự trợ giúp của máy tính - Bài 1: Tìm kiếm tuần tự

1. CHÀO MỪNG CÁC EM ĐẾN VỚI TIẾT HỌC HÔM NAY!
2. KHỞI ĐỘNG Giáo viên dạy Tin học lớp 7A trả kết quả bài kiểm tra và thông báo: “Trong lớp có duy nhất một bạn đạt điểm 10”. Xem danh sách lớp kèm cột điểm kiểm tra, em làm thế nào để biết ai được điểm 10?
3. CHỦ ĐỀ F: GIẢI QUYẾT VẤN ĐỀ VỚI SỰ TRỢ GIÚP CỦA MÁY TÍNH Một số thuật toán sắp xếp và tìm kiếm cơ bản BÀI 1: TÌM KIẾM TUẦN TỰ (1 Tiết)
4. NỘI DUNG BÀI HỌC 1. Tìm kiếm tuần tự một số trong dãy số 2. Thuật toán tìm kiếm tuần tự 3. Bài toán tìm kiếm
5. 1. Tìm kiếm tuần tự một số trong dãy số Đọc thông tin mục 1 SGK tr.78, và trả lời câu hỏi trong phần Ví dụ: Cho dãy số 18, 94, 42, 44, 06, 55, 12, 67. Hãy tìm xem số 44 ở trong dãy này không. Nếu có thì đưa ra vị trí đầu tiên tìm thấy. Dãy xuất phát:
6. Hướng dẫn Gọi số phải tìm là x (x = 44). Các bước thực hiện tìm kiếm: Bước Thực hiện 1 So sánh số ở đầu dãy với x: Vì a1 = 18 ≠ x nên chuyển sang xét số tiếp theo a2 trong dãy 2 So sánh số ở đang xét với x: Vì a2 = 94 ≠ x nên chuyển sang xét số tiếp theo a3 trong dãy 3 So sánh số ở đang xét với x: Vì a3 = 42 ≠ x nên chuyển sang xét số tiếp theo a4 trong dãy 4 So sánh số ở đang xét với x: Vì a4 = x = 44 Kết luận: Tìm thấy x ở vị trí thứ tư trong dãy; kết thúc thuật toán
7. Cả lớp cùng theo dõi video sau để hiểu rõ các bước thức hiện.
8. KẾT LUẬN Trường hợp đến hết dãy mà vẫn không tìm thấy số x cần tìm thì rút ra kết luận “trong dãy số, không có số nào bằng x” nghĩa là thuật toán đảm bảo tính đúng đắn. Ví dụ, nếu thay x = 30 trong ví dụ vừa nêu thì các bước tìm kiếm sẽ tiếp tục đến hết dãy (Bước 8) và cho kết luận “Không tìm thấy x trong dãy”
9. 2. Thuật toán tìm kiếm tuần tự Với dãy số đã cho ở ví dụ trên, em hãy thực hiện thuật toán được mô tả ở hình dưới và cho biết đó có phải là thuật toán tìm kiếm tuần tự hay không?
10. Theo em, trong thuật toán tìm kiếm tuần tự có những thao tác nào được lặp đi lặp lại và điều kiện để lặp lại là gì? ➢ Thao tác lặp đi lặp lại là bước 2. ➢ Điều kiện để lặp lại: Sẽ lặp đi lặp lại khi chưa tìm được kết quả và chưa xét hết dãy số.
11. KẾT LUẬN Ý tưởng của thuật toán tìm kiếm tuần tự: Xuất phát từ đầu dãy, nếu số ở đầu dãy không phải là số cần tìm thì chuyển sang số tiếp theo trong dãy xem có phải là số cần tìm không. Cứ như thế cho đến khi tìm thấy hoặc đã xét hết dãy. Cần áp dụng thuật toán tìm kiếm tuần tự khi dãy đầu vào không có thứ tự.
12. 3. Bài toán tìm kiếm Em hãy đọc mục 3 SGK tr.79,80 và trả lời câu hỏi: • Có mấy loại bài toán tìm kiếm? • Nêu ví dụ cụ thể để phân biệt các loại bài toán tìm kiếm. Bài toán tìm kiếm chia làm hai loại: ➢ Tìm kiếm trong dãy không sắp thứ tự ➢ Tìm kiếm trong dãy đã sắp thứ tự.
13. Bài toán tìm kiếm trong dãy không sắp thứ tự Ví dụ: Tập bài kiểm tra của lớp chưa được sắp xếp theo thứ tự bảng chữ cái đối với tên học sinh. Muốn tìm bài làm của em, giáo viên phải xem tên học sinh ghi trên từng bài, lần lượt từ bài đầu tiên cho đến khi tìm thấy bài của em. Khi dãy không sắp thứ tự cần thực hiện tìm kiếm tuần tự.
14. Bài toán tìm kiếm trong dãy đã sắp thứ tự Ví dụ: Danh sách tên học sinh trong lớp đã sắp thứ tự theo chữ cái trong từ điển thì ta có thể nhanh chóng tìm thấy bài kiểm tra của em. KẾT LUẬN ➢ Bài toán tìm kiếm chia làm hai loại: Tìm kiếm trong dãy không sắp thứ tự và tìm kiếm trong dãy đã sắp thứ tự. ➢ Khi dãy không sắp thứ tự thì cần thực hiện tìm kiếm tuần tự để đảm bảo không bỏ sót cho đến khi tìm thấy hoặc hết dãy và không tìm thấy.
15. LUYỆN TẬP Cho dãy số: Em hãy thể hiện từng bước của thuật toán giải bài toán “Tìm xem số 45 có trong dãy này không? Nếu có thì nằm ở vị trí nào?”.
16. Hướng dẫn Gọi số phải tìm là x (x = 45): • Bước 1. So sánh số ở đầu dãy với x, vì a1 = 27 ≠ x nên chuyển sang xét số tiếp theo a2 trong dãy. • Bước 2. So sánh số đang xét với x, vì a2 = 63 ≠ x nên chuyển sang xét số tiếp theo a3 trong dãy. • Bước 3. So sánh số đang xét với x, vì a3 = 12 ≠ x nên chuyển sang xét số tiếp theo a4 trong dãy. • Bước 4. So sánh số đang xét với x, vì a4 = 59 ≠ x nên chuyển sang xét số tiếp theo a5 trong dãy.
17. Hướng dẫn • Bước 5. So sánh số đang xét với x, vì a5 = 67 ≠ x nên chuyển sang xét số tiếp theo a6 trong dãy. • Bước 6. So sánh số đang xét với x, vì a6 = 45 = x. Kết luận: Tìm thấy x ở vị trí a6 trong dãy. Kết thúc thuật toán. Nếu trong dãy vẫn còn số 45 thì ta thực hiện tìm kiếm tương tự để lấy số 45 ở vị trí tiếp theo. Nếu hết thì ta sẽ dừng thuật toán. Vậy số 45 có nằm trong dãy cho trước. Số 45 nằm ở vị trí a6.
18. Trò chơi trắc nghiệm Câu 1. Trong thuật toán tìm kiếm tuần tự thao tác được lặp đi lặp lại là: A. Thao tác so sánh C. Thao tác thông báo B. Thao tác đếm số lần lặp D. Tất cả đáp án trên
19. Trò chơi trắc nghiệm Câu 2. Trong thuật toán tìm kiếm tuần tự có mấy khả năng xảy ra khi kết thúc tìm kiếm tuần tự: A. 1 C. 3 B. 2 D. 4