Giải Tin Học 7 trang 77
Lời giải chi tiết SGK Lớp 7 · Môn Tin Há»c · Trang 77–78
Tóm tắt lý thuyết
Thuật toán tìm kiếm nhị phân:
- Chỉ thực hiện được trên danh sách đã sắp xếp (thường từ nhỏ đến lớn).
- Mỗi bước lặp đều so sánh giá trị cần tìm với phần tử ở vị trí giữa của vùng tìm kiếm:
- Bằng nhau → tìm thấy, dừng lại.
- Nhỏ hơn → tìm tiếp ở nửa trước.
- Lớn hơn → tìm tiếp ở nửa sau.
- Công thức vị trí giữa: $\text{giữa} = \left\lfloor \dfrac{\text{vị trí đầu} + \text{vị trí cuối}}{2} \right\rfloor$ (lấy phần nguyên).
- Sau mỗi bước, vùng tìm kiếm thu hẹp chỉ còn một nửa nên tìm rất nhanh.
- Ý nghĩa quan trọng: Sắp xếp giúp việc tìm kiếm thực hiện nhanh hơn.
Với chữ cái, kí tự đứng trước trong bảng chữ cái được xem là "nhỏ hơn" kí tự đứng sau.
Câu hỏi (trang 76): Tìm khách hàng tên "Hoà"
Đề: Viết các bước lặp 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.
Vì trang sách này không kèm Hình 15.1 nên mình không có danh sách cụ thể để áp số liệu. Tuy nhiên cách làm là:
- Vùng tìm kiếm ban đầu là toàn bộ danh sách đã sắp xếp theo bảng chữ cái.
- Xác định phần tử ở vị trí giữa, so sánh tên đó với "Hoà".
- Nếu "Hoà" đứng trước (nhỏ hơn) tên ở giữa → tìm trong nửa trước; nếu đứng sau (lớn hơn) → tìm trong nửa sau.
- Lặp lại đến khi gặp đúng "Hoà" (tìm thấy) hoặc vùng tìm kiếm hết phần tử (không tìm thấy).
Em chỉ cần điền tên thật ở Hình 15.1 vào quy trình trên là ra các bước lặp cụ thể.
Câu hỏi (trang 77): Mối liên quan giữa sắp xếp và tìm kiếm
Đề: 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.
Gợi ý trả lời:
- Từ điển: các từ được sắp xếp theo bảng chữ cái nên ta tra từ rất nhanh.
- Danh bạ điện thoại: tên sắp theo thứ tự ABC giúp tìm số nhanh.
- Sách trong thư viện: xếp theo mã số/chủ đề nên tìm dễ.
- Bảng điểm lớp: xếp theo tên hoặc số thứ tự nên tra cứu nhanh.
Điểm chung: nếu dữ liệu đã được sắp xếp thì ta áp dụng được tìm kiếm nhị phân, nhờ đó tìm nhanh hơn rất nhiều so với dò từng phần tử.
LUYỆN TẬP
Bài 1: Sắp xếp và tìm kiếm tên các nước
Đề: Cho danh sách tên các nước:
Bolivia, Albania, Scotland, Canada, Vietnam, Iceland, Portugal, Greenland, Germany
a) Sắp xếp theo thứ tự bảng chữ cái.
Danh sách sau khi sắp xếp (9 phần tử):
| Vị trí | Tên nước |
|---|---|
| 1 | Albania |
| 2 | Bolivia |
| 3 | Canada |
| 4 | Germany |
| 5 | Greenland |
| 6 | Iceland |
| 7 | Portugal |
| 8 | Scotland |
| 9 | Vietnam |
(Lưu ý: Germany và Greenland đều bắt đầu bằng "Ge", so sánh tiếp chữ thứ ba "r" giống nhau, chữ thứ tư "m" < "e"? Không, ta so sánh: Germany = G-e-r-m..., Greenland = G-r-e-e... → chữ thứ hai: cả hai là "e" và "r". Germany có chữ thứ hai là "e", Greenland chữ thứ hai là "r", mà "e" < "r" nên Germany đứng trước Greenland.)
b) Liệt kê các bước lặp tìm Iceland bằng tìm kiếm nhị phân.
Vùng tìm kiếm ban đầu: vị trí 1 → 9.
- Bước lặp 1: vị trí giữa $= \lfloor (1+9)/2 \rfloor = 5$ → Greenland. So sánh: Iceland > Greenland (I sau G) → tìm nửa sau, vùng còn 6 → 9.
- Bước lặp 2: vị trí giữa $= \lfloor (6+9)/2 \rfloor = 7$ → Portugal. So sánh: Iceland < Portugal (I trước P) → tìm nửa trước, vùng còn 6 → 6.
- Bước lặp 3: vị trí giữa $= \lfloor (6+6)/2 \rfloor = 6$ → Iceland. So sánh: bằng nhau → tìm thấy, kết thúc.
Kết quả: tìm thấy Iceland sau 3 bước lặp.
c) So sánh với tìm kiếm tuần tự (Bài 14).
Trong danh sách đã sắp xếp, Iceland nằm ở vị trí 6, nên tìm kiếm tuần tự phải duyệt lần lượt từ vị trí 1 đến 6, tức 6 bước lặp.
| Thuật toán | Số bước lặp |
|---|---|
| Tìm kiếm tuần tự | 6 |
| Tìm kiếm nhị phân | 3 |
Như vậy tìm kiếm nhị phân nhanh hơn (3 bước so với 6 bước), vì mỗi bước thu hẹp vùng tìm kiếm còn một nửa.
Bài 2: Ví dụ thực tế dùng tìm kiếm nhị phân
Đề: Cho ví dụ một bài toán tìm kiếm thực tế có thể giải bằng tìm kiếm nhị phân, rồi thực hiện thuật toán đó.
Ví dụ gợi ý: Tìm số trang có chứa từ "Internet" trong bảng tra cứu (mục lục từ khóa) ở cuối sách, biết các từ khóa đã xếp theo thứ tự bảng chữ cái.
Cách thực hiện:
- Mở vào trang giữa của bảng tra cứu, xem từ khóa ở đó.
- Nếu "Internet" đứng trước từ đó → tìm tiếp ở nửa đầu; đứng sau → tìm ở nửa sau.
- Lặp lại đến khi gặp đúng từ "Internet".
Một ví dụ số cụ thể: tìm số 15 trong dãy đã sắp xếp 2, 3, 5, 6, 8, 9, 11, 15, 16, 18 (10 phần tử, vị trí 1–10).
- Bước 1: giữa $=\lfloor(1+10)/2\rfloor=5$ → giá trị 8. 15 > 8 → nửa sau, vùng 6–10.
- Bước 2: giữa $=\lfloor(6+10)/2\rfloor=8$ → giá trị 15. Bằng nhau → tìm thấy ở vị trí 8.
Tìm thấy số 15 sau 2 bước lặp.
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 đó?
Trả lời:
Em sẽ tìm theo kiểu tìm kiếm nhị phân chứ không lật từng trang một. Cách làm:
- Mở vào khoảng giữa từ điển, xem chữ cái đầu của các từ ở trang đó.
- Nếu từ cần tìm có chữ cái đứng trước → lật về phía trước; nếu đứng sau → lật về phía sau.
- Tiếp tục chia đôi như vậy cho đến khi tìm thấy từ.
Lý do dùng cách này: Các từ trong từ điển đã được sắp xếp theo thứ tự bảng chữ cái. Nhờ đó mỗi lần mở, em loại bỏ được một nửa số trang không cần xét, nên tìm nhanh hơn rất nhiều so với việc dò từng trang từ đầu.
Tóm lại, thông điệp cốt lõi của bài là: dữ liệu sắp xếp sẵn cho phép dùng tìm kiếm nhị phân, và tìm kiếm nhị phân nhanh hơn tìm kiếm tuần tự vì mỗi bước cắt đôi phạm vi tìm kiếm. Em có cần mình vẽ minh họa từng bước tìm Iceland để dễ hình dung hơn không?