Câu hỏi 1: Việc kinh doanh mở rộng, số lượng khách hàng của cửa hàng bán giống cây trồng nhà An lên đến hàng trăm người. Việc tìm kiếm tên khách hàng trong danh sách thật khó khăn. Em có gợi ý gì cho bạn An để việc tìm kiếm được dễ dàng hơn không?
1. THUẬT TOÁN TÌM KIẾM NHỊ PHÂN
Hoạt động 1:
1. Em hãy cho biết thuật toán tìm kiếm tuần tự phải thực hiện bao nhiêu bước để tìm được khách hàng tên “Trúc” trong danh sách ở Hình 15.1? Em hãy so sánh số bước thực hiện của thuật toán tìm kiếm tuần tự với số bước thực hiện của thuật toán tìm kiếm nhị phân.
2. Theo em trước khi thực hiện thuật toán tìm kiếm nhị phân, danh sách khách hàng cần thoả mãn điều kiện gì? Nếu không thoả mãn điều kiện đó, thuật toán tìm kiếm nhị phân có thực hiện được không?
Câu hỏi 1: Em hãy viết các bước thực hiện thuật toán tìm kiếm nhị phân để tìm khách hàng tên “Hoà” trong danh sách ở Hình 15.1
2. SẮP XẾP VÀ TÌM KIẾM
Hoạt động 2:
Chuẩn bị: Hai bạn chơi A, B và 10 tấm thẻ ghi 10 số khác nhau (các số đều nhỏ hơn 20). Ví dụ, 10 số trên các tấm thẻ là 2, 3, 5, 6, 8, 9, 11, 15, 16, 18. Giả sử A giữ 10 tấm thẻ và B là người tìm kiếm.
Yêu cầu: Bạn B sử dụng thuật toán tìm kiếm nhị phân để tìm một số nhỏ hơn 20 trong các tấm thẻ của bạn A.
Cách chơi:
Bước 1. A úp lần lượt 10 chiếc thẻ lên bàn theo thứ tự các số từ bé đến lớn.
Bước 2. B cho A biết con số mình cần tìm.
Bước 3. B chọn tấm thẻ ở vị trí giữa.
Bước 4. A hé mở tấm thẻ và trả lời B bằng cách nói một trong ba cụm từ: “bằng nhau”, “lớn hơn” hoặc “bé hơn” tuỳ thuộc vào kết quả so sánh số bạn B cần tìm với số ở vị trí giữa của dãy.
Bước 5. Tuỳ vào câu trả lời của A mà B chọn nửa dãy tiếp theo để tìm kiếm.
Bước 6. Lặp lại các bước 3, 4, 5 cho đến khi B tìm thấy số cần tìm hoặc đã tìm hết dãy số.
Bước 7. Hoán đổi vị trí của A và B trong lượt chơi tiếp theo.
Câu hỏi 1: Em hãy nêu ví dụ trong thực tế cho thấy mối liên quan giữa sắp xếp và tìm kiếm
a) Em hãy sắp xếp danh sách tên các nước theo thứ tự trong bảng chữ cái.
b) Em hãy liệt kê các bước tìm kiếm tên nước Iceland trong danh sách đã sắp xếp theo thuật toán tìm kiếm nhị phân.
c) Em hãy so sánh số bước thực hiện tìm kiếm ở phần b với số bước thực hiện tìm kiếm ở Câu 2 phần Luyện tập của bài 14.
Luyện tập 2: Em hãy cho ví dụ một bài toán tìm kiếm trong thực tế mà có thể thực hiện bằng thuật toán tìm kiếm nhị phân? Hãy thực hiện thuật toán tìm kiếm nhị phân để giải quyết bài toán đó.
VẬN DỤNG
Em tìm một từ tiếng Anh trong quyển từ điển theo cách nào? Tại sao em lại dùng cách đó?
PHẦN II .Lời giải tham khảo
KHỞI ĐỘNG
Câu hỏi 1: Việc kinh doanh mở rộng, số lượng khách hàng của cửa hàng bán giống cây trồng nhà An lên đến hàng trăm người. Việc tìm kiếm tên khách hàng trong danh sách thật khó khăn. Em có gợi ý gì cho bạn An để việc tìm kiếm được dễ dàng hơn không?
Giải thích: Để việc tìm kiếm được dễ dàng hơn, An cần tổ chức danh sách khách hàng theo một trật tự nhất định, ví dụ như sắp xếp theo thứ tự bảng chữ cái. Khi danh sách đã được sắp xếp, An có thể áp dụng thuật toán tìm kiếm nhị phân thay vì tìm kiếm tuần tự. Thuật toán tìm kiếm nhị phân sẽ giảm số bước tìm kiếm đáng kể so với cách duyệt từng phần tử của danh sách.
1. THUẬT TOÁN TÌM KIẾM NHỊ PHÂN
Hoạt động 1:
Thuật toán tìm kiếm tuần tự phải thực hiện bao nhiêu bước để tìm được khách hàng tên “Trúc” trong danh sách ở Hình 15.1? Em hãy so sánh số bước thực hiện của thuật toán tìm kiếm tuần tự với số bước thực hiện của thuật toán tìm kiếm nhị phân.
Giải thích:
Thuật toán tìm kiếm tuần tự sẽ duyệt qua từng phần tử trong danh sách từ đầu đến cuối. Nếu khách hàng “Trúc” ở vị trí cuối cùng trong danh sách có nnn phần tử, thì cần thực hiện nnn bước.
Thuật toán tìm kiếm nhị phân chia danh sách thành hai nửa mỗi lần so sánh, do đó số bước cần thiết là \(\log_2(n)\) (làm tròn lên nếu số không nguyên).
Ví dụ: Nếu danh sách có 16 khách hàng:
Tìm kiếm tuần tự có thể cần tối đa 16 bước.
Tìm kiếm nhị phân chỉ cần \(\log_2(16) = 4\)bước.
Kết luận: Thuật toán tìm kiếm nhị phân hiệu quả hơn rất nhiều so với tìm kiếm tuần tự, đặc biệt khi danh sách lớn.
Theo em trước khi thực hiện thuật toán tìm kiếm nhị phân, danh sách khách hàng cần thoả mãn điều kiện gì? Nếu không thoả mãn điều kiện đó, thuật toán tìm kiếm nhị phân có thực hiện được không?
Giải thích:
Điều kiện tiên quyết của thuật toán tìm kiếm nhị phân là danh sách phải được sắp xếp theo thứ tự tăng dần hoặc giảm dần.
Nếu danh sách không được sắp xếp, thuật toán không thể xác định nửa nào của danh sách cần loại bỏ ở mỗi bước, dẫn đến việc tìm kiếm không thực hiện được.
Câu hỏi 1: Em hãy viết các bước thực hiện thuật toán tìm kiếm nhị phân để tìm khách hàng tên “Hoà” trong danh sách ở Hình 15.1.
Các bước thực hiện:
Sắp xếp danh sách khách hàng theo thứ tự bảng chữ cái.
Xác định phần tử ở vị trí giữa danh sách.
So sánh tên “Hoà” với tên ở vị trí giữa: Nếu bằng nhau, kết thúc và trả về vị trí. Nếu nhỏ hơn, loại bỏ nửa sau và lặp lại trên nửa trước. Nếu lớn hơn, loại bỏ nửa trước và lặp lại trên nửa sau.
Lặp lại quá trình cho đến khi tìm thấy tên “Hoà” hoặc danh sách chỉ còn một phần tử.
2. SẮP XẾP VÀ TÌM KIẾM
Hoạt động 2:
Yêu cầu: Bạn B sử dụng thuật toán tìm kiếm nhị phân để tìm một số nhỏ hơn 20 trong các tấm thẻ của bạn A.
Cách chơi chi tiết:
Ban đầu, bạn A sắp xếp 10 tấm thẻ theo thứ tự tăng dần.
Bạn B yêu cầu tìm một số cụ thể (ví dụ: số 9).
Bạn B lấy tấm thẻ ở vị trí giữa (tấm thẻ thứ 5, nếu đánh số từ 1 đến 10).
So sánh số 9 với số trên tấm thẻ ở vị trí giữa: Nếu số 9 bằng số trên tấm thẻ, kết thúc. Nếu số 9 nhỏ hơn, tìm kiếm trong nửa đầu của dãy. Nếu số 9 lớn hơn, tìm kiếm trong nửa sau của dãy.
Tiếp tục quy trình cho đến khi tìm thấy số 9 hoặc không tìm thấy.
Câu hỏi 1: Em hãy nêu ví dụ trong thực tế cho thấy mối liên quan giữa sắp xếp và tìm kiếm.
Giải thích: Một ví dụ thực tế là việc tìm một từ trong từ điển. Từ điển được sắp xếp theo thứ tự bảng chữ cái, giúp ta dễ dàng áp dụng cách tìm kiếm nhanh chóng bằng cách lật đến giữa sách, so sánh và thu hẹp phạm vi tìm kiếm.
LUYỆN TẬP
Luyện tập 1:
a) Sắp xếp danh sách tên các nước theo thứ tự bảng chữ cái: Danh sách sắp xếp: Albania, Bolivia, Canada, Germany, Greenland, Iceland, Portugal, Scotland, Vietnam.
b) Các bước tìm kiếm tên nước Iceland trong danh sách đã sắp xếp:
Xác định vị trí giữa danh sách: Phần tử giữa là “Germany”.
So sánh “Iceland” với “Germany”: “Iceland” lớn hơn “Germany”, loại bỏ nửa đầu (Albania, Bolivia, Canada, Germany).
Xét nửa sau: Phần tử giữa là “Portugal”.
So sánh “Iceland” với “Portugal”: “Iceland” nhỏ hơn “Portugal”, loại bỏ nửa sau (Portugal, Scotland, Vietnam).
Còn lại danh sách nhỏ hơn: Greenland, Iceland. Phần tử giữa là “Iceland”.
Tìm thấy “Iceland”.
c) So sánh số bước tìm kiếm ở phần b với bài 14:
Bài 14 sử dụng tìm kiếm tuần tự, cần duyệt từ đầu đến cuối danh sách, mất 6 bước.
Bài 15 sử dụng tìm kiếm nhị phân, chỉ cần 3 bước.
Luyện tập 2:
Ví dụ: Tìm một cuốn sách theo mã số trong thư viện.
Nếu các mã số sách được sắp xếp, ta có thể áp dụng thuật toán tìm kiếm nhị phân để xác định mã số sách cần tìm.
VẬN DỤNG
Câu hỏi: Em tìm một từ tiếng Anh trong quyển từ điển theo cách nào? Tại sao em lại dùng cách đó?
Giải thích: Khi tìm một từ trong từ điển, em thường lật đến phần giữa để xác định phạm vi của từ cần tìm, sau đó tiếp tục thu hẹp phạm vi bằng cách so sánh với các từ khác. Cách này tương tự với thuật toán tìm kiếm nhị phân vì từ điển đã được sắp xếp theo thứ tự bảng chữ cái, giúp việc tìm kiếm nhanh và hiệu quả hơn.
