Giáo án Bài 19 · KHMT. Bài toán tìm kiếm

Xác định vấn đề: bài toán tìm kiếm cần trả lời được gì và cần quy định cách xử lí các trường hợp nào.

GV ghi dãy $[8,3,6,3]$ lên bảng và đặt lần lượt các câu hỏi:

• Trong dãy có số $3$ không? Nó nằm ở vị trí nào? Nếu xuất hiện hai lần thì trả lời thế nào?
• Tìm số $9$ trong dãy trên: máy tính nên trả về kết quả gì để người dùng biết là không có?
• Dãy $[2,4,6,8,10]$ đã được sắp xếp. Em có cách nào tìm số $8$ nhanh hơn việc xét từng phần tử không?
  HS trả lời miệng, GV ghi các ý chính lên bảng.

Dự kiến HS trả lời:

• Số $3$ có trong dãy, vị trí đầu tiên là $1$ (đếm từ $0$), vị trí thứ hai là $3$. Vì có hai kết quả nên cần quy ước trả về vị trí nào.
• Số $9$ không có trong dãy, cần quy ước trả về $-1$.
• Với dãy đã sắp xếp, có thể bỏ qua một nửa dãy sau mỗi lần so sánh.
  Kết luận ghi vở: Bài toán tìm kiếm cần xác định giá trị hoặc vị trí và cách xử lí khi không thấy hoặc khi phần tử lặp lại.

Giải thích được ý tưởng và điều kiện áp dụng của tìm kiếm tuyến tính; giải thích được vì sao chương trình trả về vị trí đầu tiên.

HS làm việc theo cặp với Phiếu học tập số 1. Cặp đọc hàm tim(a,x) duyệt bằng vòng for, dự đoán kết quả của tim([8,3,6,3],3), sau đó chạy chương trình trên máy để kiểm tra. Cặp trả lời các câu hỏi trong phiếu: vì sao có câu lệnh return ngay khi gặp phần tử; điều gì xảy ra khi không thấy; thuật toán có cần dãy được sắp xếp không.

Kiến thức HS rút ra:

• Ý tưởng: duyệt lần lượt $i$ từ $0$ đến $\mathrm{len(a)-1}$, so sánh $a[i]$ với $x$; khi $a[i]=x$ thì return $i$ ngay.
• Kết quả chạy chương trình với dãy $[8,3,6,3]$ và $x=3$ là $1$, vì return dừng ở lần gặp đầu tiên.
• Nếu duyệt hết dãy mà không gặp $x$ thì return $-1$.
• Tìm tuyến tính duyệt được dãy bất kì, không cần dãy được sắp xếp.

Giải thích được ý tưởng thu hẹp khoảng tìm kiếm của tìm nhị phân; nêu được điều kiện dãy phải sắp thứ tự và hạn chế với phần tử lặp.

Nhóm 4 HS làm Phiếu học tập số 2. Nhóm đọc chương trình tim(a,x) dùng biến l, r, m, chạy với a=[2,4,6,8,10] và x=8, lập bảng theo dõi giá trị l, r, m, a[m] qua từng vòng lặp. Sau đó nhóm trả lời: vì sao sau khi a[m] < x thì đặt l=m+1; nếu dãy không được sắp xếp thì điều gì xảy ra; với dãy [8,3,6,3] thì tìm nhị phân có đảm bảo trả về vị trí đầu tiên của 3 không.

Bảng trace dự kiến:

• Lượt 1: l=0, r=4, m=2, a[m]=6; 6 nhỏ hơn 8 nên đặt l=3.
• Lượt 2: l=3, r=4, m=3, a[m]=8; bằng 8 nên return 3.
  Kết quả in ra là 3.
  Kiến thức HS rút ra:
• Mỗi lần so sánh a[m] với x để loại một nửa khoảng tìm kiếm.
• Điều kiện bắt buộc: dãy phải được sắp theo thứ tự thích hợp; dãy [8,3,6,3] không được sắp nên không áp dụng được.
• Với phần tử lặp, tìm nhị phân cơ bản không bảo đảm trả về vị trí đầu tiên.

Vận dụng quy ước vị trí và trả về $-1$; phân biệt điều kiện áp dụng của hai thuật toán; viết và kiểm tra chương trình tìm kiếm.

HS làm cá nhân các bài 2 đến 7, sau đó đối chiếu trong nhóm. Nhóm làm tiếp bài 8 và bài 9: viết chương trình tìm tuyến tính trả về vị trí đầu của $3$ trong $[8,3,6,3]$, sau đó sửa để tìm mọi vị trí. Nhóm có thể dùng bài tập tương tác trên trang NeoEdu để kiểm tra kết quả.
Bài tập:

• Bài 2: in tim([8,3,6],9).
• Bài 3: in tim([5,2,5],5).
• Bài 4: tìm nhị phân tim([2,4,6,8,10],8).
• Bài 5: điều kiện của tìm nhị phân là gì? A. Dãy được sắp theo thứ tự thích hợp; B. Dãy bất kì; C. Các phần tử bắt buộc khác nhau; D. Chỉ toàn số dương.
• Bài 6: trả về $-1$ có phải là phần tử cuối cần lấy không?
• Bài 7: sắp xếp các bước giải một bài tìm kiếm.
• Bài 8 và 9: viết và sửa chương trình.

Đáp án:

• Bài 2: $-1$, vì duyệt hết dãy không có $9$.
• Bài 3: $0$, vì dừng ở lần gặp đầu tiên tại vị trí $0$.
• Bài 4: $3$, vì lượt đầu $m=2$ có $a[2]=6<8$ nên $l=3$; lượt sau $m=3$ và $a[3]=8$.
• Bài 5: Đáp án A, vì nhị phân dựa vào thứ tự để loại một nửa dãy.
• Bài 6: Đúng, $-1$ chỉ là quy ước báo không thấy, không được dùng $a[-1]$ làm kết quả.
• Bài 7: Xác định mục tiêu và kiểu kết quả → Chọn thuật toán theo dữ liệu → Tìm và trả về vị trí hoặc $-1$ → Kiểm tra có hoặc không và xử lí lặp.
• Bài 8: chương trình mẫu:
  def tim(a,x):
  for i in range(len(a)):
  if a[i]==x:
  return i
  return -1
  print(tim([8,3,6,3],3))
  Kết quả in $1$. Thang chấm tham khảo: duyệt theo chỉ số $0$ đến $n-1$ (0,3 điểm); return ngay lần đầu (0,25 điểm); kết quả $1$ (0,25 điểm); trả $-1$ khi không thấy và giải thích (0,2 điểm). Chấp nhận phương án tương đương đúng.
• Bài 9: không return sớm, giữ danh sách kết quả:
  def tim_tat_ca(a,x):
  ket_qua=[]
  for i in range(len(a)):
  if a[i]==x:
  ket_qua.append(i)
  return ket_qua
  print(tim_tat_ca([8,3,6,3],3))
  Kết quả in [1, 3]; nếu không thấy thì trả về danh sách rỗng. Chấp nhận cách diễn đạt tương đương.

Vận dụng được điều kiện áp dụng để chọn thuật toán phù hợp với một tình huống thực tế và giải thích lựa chọn.

GV nêu tình huống: nhà trường có danh sách họ tên học sinh của lớp, chưa sắp xếp, và danh sách mã số học sinh đã sắp tăng dần. Cần tìm học sinh có tên 'Lê Minh' và mã số 1205 để tra cứu. HS nhận xét nên dùng thuật toán nào cho mỗi danh sách và cần xử lí thế nào khi không tìm thấy.
Nhiệm vụ về nhà: viết chương trình tìm mã số trong danh sách đã sắp xếp bằng tìm nhị phân, kiểm tra với ít nhất 3 trường hợp (có, không có, vị trí đầu và cuối dãy) trên trang NeoEdu.

Dự kiến sản phẩm:

• Danh sách họ tên chưa sắp xếp: dùng tìm tuyến tính, vì chỉ điều kiện duyệt được dãy bất kì là đủ.
• Danh sách mã số đã sắp tăng dần: có thể dùng tìm nhị phân, vì điều kiện sắp thứ tự được thoả mãn và thu hẹp khoảng nhanh.
• Khi không tìm thấy: trả về $-1$ và thông báo 'Không tìm thấy'.
• Bảng kiểm tra dữ liệu gồm: trường hợp có trong dãy, trường hợp không có, trường hợp ở đầu và cuối dãy.