1. Cho danh sách tên các nước sau đây:
Bolivia, Albania, Scotland, Canada, Vietnam, Iceland, Portugal, Greendland, 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.
Thuật toán tìm kiếm nhị phân:
- Thực hiện trên danh sách đã được sắp xếp. Bắt đầu từ vị trí ở giữa danh sách.
- Tại mỗi bước, so sánh giá trị cần tìm với giá trị của vị trí giữa danh sách, nếu lớn hơn thì tìm trong nửa sau của danh sách, nếu nhỏ hơn thì tìm trong nửa trước của danh sách, nếu bằng thì dừng lại.
- Chừng nào chưa tìm thấy và chưa hết danh sách thì còn tìm tiếp.
a) Sắp xếp danh sách tên các nước theo thứ tự trong bảng chữ cái: Albania, Bolivia, Canada, Germany, Greendland, 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 theo thuật toán tìm kiếm nhị phân:
- Bước 1: Xét vị trí ở giữa dãy, đó là vị trí số 5
- Bước 2: Xét vị trí ở giữa của nửa sau của dãy là vị trí số 7
Advertisements (Quảng cáo)
- Bước 3: Vì nửa trước của dãy chỉ còn một tên, đó là vị trí số 6
- Vì sau bước 3 đã tìm thấy tên nước nên thuật toán kết thúc.
c) Số bước thực hiện tìm kiếm ở phần b ít hơn so 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.
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 kiến thức thực tế và thuật toántìm kiếm nhị phân để giải quyết
Ví dụ một bài toán tìm kiếm trong thực tế: Giáo viên muốn tìm tên bạn Chung trong danh sách lớp sau:
Các bước thực hiện thuật toán tìm kiếm nhị phân cho bài toán trên:
- Bước 1: Xét vị trí ở giữa dãy, đó là vị trí số 5
- Bước 2: Xét vị trí ở giữa của nửa đầu của dãy là vị trí số 3
- Vì sau bước 2 đã tìm thấy tên học sinh nên thuật toán kết thúc.