BÀI 15. THUẬT TOÁN TÌM KIẾM NHỊ PHÂN

PHẦN I. HỆ THỐNG CÂU HỎI, BÀI TẬP TRONG SGK

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?

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

LUYỆN TẬP

Luyện tập 1: Cho danh sách tên các nước sau đây:

Bolivia, Albania, Scotland, Canada, Vietnam, Iceland, Portugal, Greenland, Germany

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. 5 PHÚT TRẢ LỜI CÂU HỎI, BÀI TẬP SGK

KHỞI ĐỘNG

Đáp án CH1: An cần soạn thảo danh sách khách hàng trên máy tính với tên khách hàng được sắp xếp theo thứ tự chữ cái. 

1. THUẬT TOÁN TÌM KIẾM NHỊ PHÂN

Đáp án HD1:

1. Thuật toán tìm kiếm tuần tự phải thực hiện 8 lần trong khi thuật toán tìm kiếm nhị phân chỉ thực hiện 3 lần.

2. Danh sách khách hàng cần sắp xếp theo thứ tự từ nhỏ đến lớn. Nếu không sắp xếp thì thuật toán tìm kiếm nhị phân không thực hiện được.

Đáp án CH1: 

- Bước 1: Xét vị trí số 5. So sánh “Hoà” và “Mai”. Vì “H” đứng trước “M” trong bảng chữ cái nên bỏ đi nữa sau danh sách.

- Bước 2: Xét vị trí số 3. So sánh “Hòa” và “Hòa”, vì hai giá trị bằng nhau nên thuật toán kết thúc.

- Sau 2 bước đã tìm thấy tên khách hàng tên “Hoà” nên thuật toán kết thúc.

2. SẮP XẾP VÀ TÌM KIẾM

Đáp án HD2:

Các em tìm 1 bạn chơi cùng mình.

Đáp án CH1: 

Trong thực tế trong quản lý học sinh, danh sách học sinh luôn được sắp xếp theo chữ cái đầu của tên để dễ tìm kiếm.

LUYỆN TẬP

Đáp án LT1: 

a) Albania, Bolivia, Canada, Germany, Greenland, Iceland, Portugal, Scotland, Vietnam.

b) 

• Bước 1: Xét vị trí thứ 5. So sánh “Greenland” và “Iceland” vì “G” đứng trước “I” trong bảng chữ cái nên bỏ đi nữa đầu danh sách.
• Bước 2: Xét vị trí thứ 7. So sánh Portugal và “Iceland” vì “P” đứng sau “I” trong bảng chữ cái nên bỏ đi nữa sau danh sách.
• Bước 3: Xét vị trí thứ 6. So sánh “Iceland” và “Iceland” vì hai giá trị bằng nhau nên thuật toán kết thúc.
• Sau 3 bước đã tìm thấy tên nước “Iceland” nên thuật toán kết thúc.

Đáp án LT2: 

- Xem xét từ vị trí giữa sách. So sánh tên cần tìm với tên ở vị trí xét.

- Nếu kí tự đầu của tên đứng trước vần N thì tên cần tìm ở nửa sau danh sách.

- Nếu kí tự đầu của tên đứng sau vần N thì tên cần tìm ở nửa trước của danh sách.

- Nếu tên trùng nhau thì dừng lại. Nếu chưa tìm thấy thì tiếp tục tìm như bước trên.

VẬN DỤNG

Đáp án VD: 

Theo cách tìm kiếm nhị phân. Giả sử cuốn từ điển có khoảng 300 nghìn mục từ. Nếu tra một từ trong từ điển bằng cách tìm kiếm nhị phân thì sau một lần chia đôi, phạm vi tìm kiếm giảm đi.