Giáo án Bài 14. Thuật toán tìm kiếm tuần tự

Huy động kinh nghiệm sẵn có của HS về cách tìm một số trong dãy; xác định vấn đề cần giải quyết: có cách nào tìm số một cách có hệ thống và không cần sắp xếp dãy trước hay không.

GV đưa dãy mẫu 4, 7, 9, 2 lên bảng và hỏi: “Để biết số 9 có trong dãy hay không, em sẽ kiểm tra như thế nào?”. HS trả lời tự do, sau đó GV hỏi tiếp: “Nếu dãy là 2, 9, 7, 4 hoặc dãy nào khác mà chưa sắp xếp, cách làm có thay đổi không?”.

HS nêu được cách làm tự nhiên là xét lần lượt từ phần tử đầu tiên đến phần tử cuối, khi gặp số cần tìm thì dừng. HS nhận thấy không cần sắp xếp dãy trước. Vấn đề cần giải quyết: viết cách làm này thành các bước rõ ràng, có thể lặp lại cho mọi dãy.

Hình thành cho HS khái niệm và các bước của thuật toán tìm kiếm tuần tự; biết lập bảng vết và xác định số lần so sánh, vị trí trả về khi tìm thấy lần đầu.

HS làm việc theo nhóm 4 người với Phiếu học tập số 1, theo dõi bài giảng và ví dụ trên trang NeoEdu. Nhiệm vụ: tìm số 9 trong dãy 4, 7, 9, 2 bằng tìm kiếm tuần tự, vị trí đánh số từ 1, dừng ở lần khớp đầu tiên. Nhóm lập bảng vết với các cột: vị trí, giá trị đang xét, kết quả so sánh (bằng/khác), quyết định tiếp theo. Câu hỏi gợi mở: (1) Bắt đầu từ vị trí nào? (2) Khi so sánh 4 với 9 thì làm gì? (3) Khi nào thuật toán dừng? (4) Có cần xét số 2 không, vì sao?

Bảng vết của nhóm: (1, 4, khác), (2, 7, khác), (3, 9, bằng). Kết quả: có 3 lần so sánh, trả vị trí 3, không xét số 2 vì đã dừng ở lần khớp đầu. Kiến thức HS rút ra: tìm kiếm tuần tự so sánh lần lượt từ đầu dãy; không đòi hỏi dãy được sắp xếp; khi gặp phần tử bằng mục tiêu thì dừng và báo vị trí.

Giúp HS hiểu trường hợp không có phần tử cần tìm: phải duyệt hết danh sách và trả “không thấy”; nhận biết điều kiện áp dụng của thuật toán.

HS làm việc theo cặp đôi. Nhiệm vụ 1: tìm số 8 trong dãy 4, 7, 9, 2 và lập bảng vết đầy đủ. Nhiệm vụ 2: trả lời câu hỏi: “Khi nào em được kết luận là không thấy?”, “Nếu dừng khi mới xét 2 phần tử thì có đúng không?”, “Dãy có cần sắp xếp không?”. HS có thể xem lại ví dụ trên trang NeoEdu.

Bảng vết: (1, 4, khác), (2, 7, khác), (3, 9, khác), (4, 2, khác). Có 4 lần so sánh, cả 4 phần tử đều khác, kết quả là “không thấy”. Kiến thức HS rút ra: chỉ kết luận không có khi đã duyệt hết danh sách; không trả nhầm phần tử cuối cùng; thuật toán không yêu cầu danh sách được sắp xếp.

Củng cố khái niệm, số lần so sánh, vị trí trả về và trường hợp không thấy thông qua các câu hỏi và bài lập bảng vết.

Phần A (cá nhân, 4 phút): HS làm các câu hỏi 2 đến 7 trên bảng phụ hoặc slide (trắc nghiệm, đúng/sai, ghép, sắp xếp bước). Phần B (cặp đôi, 6 phút): HS làm Phiếu học tập số 2 gồm bài 8 và bài 9 của bài học. Có thể làm bài tương tác trên trang NeoEdu để đối chiếu.

Đáp án phần A: Câu 2: A (không bắt buộc sắp xếp, chỉ cần duyệt lần lượt). Câu 3: B (so sánh với 4, 7, 9 là 3 lần). Câu 4: Đúng (chưa duyệt hết thì có thể còn mục tiêu phía sau). Câu 5: Sai (đề này quy định vị trí bắt đầu từ 1). Câu 6: Mục tiêu là giá trị cần tìm; So sánh là kiểm tra phần tử có bằng mục tiêu; Không thấy là duyệt hết không có giá trị khớp. Câu 7: Bắt đầu từ vị trí 1 → So sánh 4 với 9 rồi chuyển tiếp vì khác → So sánh 7 với 9 rồi chuyển tiếp vì khác → So sánh 9 với 9 và báo vị trí 3 rồi dừng. Đáp án phần B (Phiếu số 2): Bài 8: vết (1, 4, khác), (2, 7, khác), (3, 9, bằng); có 3 so sánh; trả vị trí 3; khi tìm 8 thì cả 4 phần tử đều khác, trả không thấy. Bài 9: dãy 9, 4, 9, tìm 9 dừng ở lần đầu cho kết quả vị trí 1 với 1 so sánh; nếu cần mọi vị trí thì tiếp tục duyệt đến hết và ghi vị trí 1 và 3.

Vận dụng thuật toán tìm kiếm tuần tự vào một tình huống thực tế giả định, lập bảng vết và kiểm tra lại kết quả, đồng thời giải thích điều kiện áp dụng.

Nhóm 4 HS nhận danh sách mã sản phẩm giả định trong kho: K12, T07, M45, A90, H03, Q58 (dữ liệu giả định, không phải dữ liệu thực tế). Nhiệm vụ: (1) Tìm mã M45 và ghi vị trí; (2) Tìm mã Z99 và kết luận; (3) Giải thích vì sao không cần sắp xếp danh sách mã trước khi tìm; (4) Mỗi thành viên kiểm tra lại kết quả của nhóm bằng cách đọc lại bảng vết.

Bảng vết mẫu: (1, K12, khác), (2, T07, khác), (3, M45, bằng) → vị trí 3, 3 so sánh. Với Z99: 6 lần so sánh, đều khác, kết quả “không thấy”. Giải thích: thuật toán chỉ cần so sánh lần lượt, không cần danh sách sắp xếp; kiểm tra lại bằng cách đọc lại bảng vết từ đầu đến cuối.