Giáo án Bài 20 · KHMT. Thực hành bài toán tìm kiếm

Huy động kinh nghiệm HS về cách thu hẹp phạm vi tìm kiếm và dẫn dắt vào ý tưởng chia đôi khoảng tìm kiếm.

GV đưa ra dãy tăng dần gồm các số từ 1 đến 16 (chỉ hiện trên bảng dạng danh sách) và chọn một số bí mật. HS chơi theo lượt: mỗi lần đoán một số, GV chỉ trả lời 'lớn hơn', 'nhỏ hơn' hoặc 'đúng'. Sau đó GV đặt câu hỏi: 'Chiến lược nào giúp bạn loại được nhiều khả năng nhất sau mỗi lần đoán?'

HS nêu được chiến lược chọn số ở giữa khoảng còn khả năng và loại nửa khoảng sau mỗi lần so sánh. GV ghi lên bảng hai ý then chốt: dãy phải được sắp xếp tăng dần và mỗi lần so sánh loại bỏ phần không thể chứa mục tiêu.

Giải thích được bất biến của tìm nhị phân, vai trò của các cập nhật $l = m+1$ và $r = m-1$, và điều kiện dừng khi không tìm thấy.

HS làm việc theo cặp với Phiếu học tập số 1: truy vết chương trình mẫu tìm $13$ trong $[1,4,7,10,13,16]$, ghi giá trị $l$, $r$, $m$, $a[m]$ và quyết định ở từng bước. HS trả lời câu hỏi: 'Vì sao sau khi so sánh $a[m] < x$ ta đặt $l = m+1$ mà không đặt $l = m$?' và 'Điều gì xảy ra khi $l > r$?'

Vết thực hiện đúng: lần 1: $l=0$, $r=5$, $m=2$, $a[2]=7 < 13$, cập nhật $l=3$; lần 2: $l=3$, $r=5$, $m=4$, $a[4]=13$, trả về $4$. Kết luận HS ghi: bất biến là mục tiêu (nếu có) nằm trong $[l, r]$; $l = m+1$ bỏ vị trí $m$ đã kiểm tra và phần bên trái; khi $l > r$ khoảng rỗng, không còn phần tử nào để kiểm tra nên trả về $-1$.

Vận dụng vết thực hiện để dự đoán kết quả với dãy rỗng, dãy một phần tử, trường hợp không có giá trị và trường hợp dễ gây lặp vô hạn.

HS làm việc nhóm 4 với Phiếu học tập số 2: dự đoán và kiểm chứng kết quả của tim([], 3), tim([2], 2), tim([1,4,7,10], 6) và tim([1,2], 2) khi thay $l = m+1$ bằng $l = m$. HS cũng dùng máy tính chạy các ca này và so sánh với dự đoán. GV đặt câu hỏi: 'Với $[1,2]$ và $x = 2$, giá trị $l$ có thay đổi sau một vòng lặp không?'

Kết quả: tim([],3) cho $-1$ vì $r=-1$ nên không vào vòng lặp; tim([2],2) cho $0$ vì $l=r=0$ và $a[0]=2$; tim([1,4,7,10],6) cho $-1$ vì khoảng thu hẹp đến $r < l$ mà không gặp $6$; với $[1,2]$, $x=2$, ban đầu $l=0$, $r=1$, $m=0$, $a[0]=1<2$; nếu cập nhật $l=m$ thì $l$ vẫn bằng $0$, khoảng không thu hẹp và vòng lặp có thể lặp mãi. Với $l=m+1$ thì $l=1$, $m=1$, trả về $1$.

Củng cố điều kiện áp dụng, cập nhật khoảng tìm kiếm, điều kiện không thấy và thứ tự các bước giải bài toán tìm nhị phân.

HS làm các bài tập 2 đến 7 của bài học theo nhóm đôi, ghi đáp án vào phiếu và giải thích ngắn gọn. Bài 2: tim([],3). Bài 3: tim([2],2). Bài 4: tim([1,4,7,10],6). Bài 5: cập nhật khi $a[m] < x$ trong dãy tăng. Bài 6: điều kiện kết thúc khi không tìm thấy. Bài 7: sắp xếp các bước phương pháp giải.

Đáp án: bài 2: $-1$ (không chạy vòng lặp vì $r=-1$); bài 3: $0$ ($l=r=0$ và so sánh bằng); bài 4: $-1$ (khoảng thu hẹp đến $r < l$, không có $6$); bài 5: A, $l = m+1$ (bỏ nửa trái và vị trí giữa); bài 6: Đúng, $l > r$ là khoảng không còn phần tử; bài 7: Đặt khoảng toàn dãy → Chọn giữa và so sánh → Thu hẹp bỏ phần không thể chứa → Dừng khi thấy hoặc khoảng rỗng.

Viết và kiểm thử được chương trình tìm nhị phân hoàn chỉnh; phân tích được lỗi khi dùng $l = m$ và đề xuất cách sửa.

Bài 1 và Bài 8: HS viết hàm tim(a, x) tìm $13$ trong $[1,4,7,10,13,16]$ với quy ước chỉ số từ $0$, trả về $-1$ nếu không thấy, rồi chạy kiểm thử theo dữ liệu mẫu. Bài 9: HS trả lời 'Nếu dùng $l = m$ thay $l = m+1$, có rủi ro gì? Cho ca.' và viết ca $[1,2]$, tìm $2$, cùng vết $l$, $r$, $m$.

Bài 1: kết quả $13$ nằm ở vị trí $4$ (quy ước đếm từ $0$). Bài 8: chương trình hoàn chỉnh có điều kiện lặp $l \le r$, cập nhật $l = m+1$ hoặc $r = m-1$, trả về $-1$ khi không thấy; khi chạy với dữ liệu mẫu in ra $4$. Thang chấm gợi ý: điều kiện dãy tăng và phạm vi tìm kiếm $0,2$ điểm; so sánh giữa và thu hẹp đúng $0,4$ điểm; tìm $13$ cho kết quả $4$ là $0,25$ điểm; dừng khi khoảng rỗng $0,15$ điểm. Bài 9: với $[1,2]$, $x=2$: $l=0$, $r=1$, $m=0$, $l=m$ giữ $l=0$, không tiến, có thể lặp mãi; sửa bằng $l=m+1$ là $0,3$ điểm.

Vận dụng tìm nhị phân vào bài toán thực tế tra cứu mã sản phẩm; đánh giá sản phẩm, kiểm tra điều kiện áp dụng và giải thích kết quả.

Tình huống: một cửa hàng lưu danh sách mã sản phẩm dạng số đã sắp xếp tăng dần, ví dụ $[101, 105, 118, 124, 130, 147]$. HS nhận một đoạn mã tra cứu có lỗi (dùng $l = m$) và danh sách mã chưa sắp xếp như $[130, 101, 147]$. HS phải: (1) sửa lỗi $l = m$ thành $l = m+1$; (2) kiểm tra xem dãy có đủ điều kiện áp dụng tìm nhị phân không; (3) thử tìm mã $124$ và mã $99$, giải thích kết quả. Nhiệm vụ về nhà: viết hàm tra cứu mã sản phẩm trên danh sách của lớp hoặc cửa hàng đã sắp xếp, kèm 3 ca kiểm thử.

Sản phẩm HS nộp: đoạn mã đã sửa với cập nhật $l = m+1$ và $r = m-1$; kết luận: dãy chưa sắp xếp $[130, 101, 147]$ không đủ điều kiện áp dụng, cần sắp xếp trước; tra cứu $124$ trên dãy đã sắp xếp cho chỉ số $3$; tra cứu $99$ cho kết quả $-1$ vì không có mã. Ghi chú: kết quả đúng theo quy ước đếm từ $0$.