Giải Tin Học 7 trang 74
Lời giải chi tiết SGK Lớp 7 · Môn Tin Há»c · Trang 74–75
Bài 15: Thuật toán tìm kiếm nhị phân
Trang 74 chủ yếu là phần lý thuyết giới thiệu về thuật toán tìm kiếm nhị phân, bao gồm:
- Mục tiêu bài học
- Tình huống đặt vấn đề (cửa hàng bán giống cây trồng của An)
- Giới thiệu thuật toán tìm kiếm nhị phân
- Bảng danh sách khách hàng (Hình 15.1)
Trang 75 trình bày các bước minh họa thuật toán tìm kiếm nhị phân để tìm tên "Trúc" và có phần Hoạt động 1.
Hoạt động 1: Sắp xếp và tìm kiếm
Câu 1
Đề bài: 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 lặp để 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 lặp thực hiện của thuật toán tìm kiếm tuần tự với số bước lặp thực hiện của thuật toán tìm kiếm nhị phân.
Cách giải
Bước 1: Xác định số bước lặp của thuật toán tìm kiếm tuần tự
Thuật toán tìm kiếm tuần tự là duyệt từ đầu đến cuối danh sách, so sánh lần lượt từng phần tử.
Danh sách khách hàng theo thứ tự (cột Tên):
- An
- Bình
- Hoà
- Liên
- Mai
- Phương
- Trang
- Trúc ← Tìm thấy ở vị trí số 8
- Tước
→ Thuật toán tìm kiếm tuần tự cần 8 bước lặp (so sánh 8 lần) để tìm thấy "Trúc".
Bước 2: Xác định số bước lặp của thuật toán tìm kiếm nhị phân
Theo minh họa trong sách:
- Bước 1: So sánh "Trúc" với "Mai" (vị trí 5) → Tìm nửa sau
- Bước 2: So sánh "Trúc" với "Trang" (vị trí 7) → Tìm nửa sau
- Bước 3: So sánh "Trúc" với "Trúc" (vị trí 8) → Tìm thấy
→ Thuật toán tìm kiếm nhị phân chỉ cần 3 bước lặp.
Bước 3: So sánh
| Thuật toán | Số bước lặp |
|---|---|
| Tìm kiếm tuần tự | 8 bước |
| Tìm kiếm nhị phân | 3 bước |
Đáp án: - Thuật toán tìm kiếm tuần tự cần 8 bước lặp để tìm "Trúc". - Thuật toán tìm kiếm nhị phân chỉ cần 3 bước lặp. - Thuật toán tìm kiếm nhị phân nhanh hơn đáng kể (ít hơn 5 bước).
💡 Mẹo nhớ: "Nhị phân chia đôi, tìm nhanh gấp bội" – Mỗi bước, danh sách tìm kiếm giảm còn một nửa nên rất nhanh!
Câu 2
Đề bài: 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ách giải
Bước 1: Xác định điều kiện cần thiết
Quan sát ví dụ trong sách:
- Danh sách khách hàng đã được sắp xếp theo thứ tự chữ cái (A → B → H → L → M → P → T → T → T)
- Thuật toán so sánh giá trị cần tìm với giá trị ở giữa để quyết định tìm ở nửa trước hay nửa sau
Bước 2: Giải thích tại sao cần điều kiện này
- Nếu danh sách chưa sắp xếp, việc so sánh với phần tử ở giữa không có ý nghĩa
- Ta không thể biết giá trị cần tìm nằm ở nửa nào của danh sách
- Thuật toán sẽ cho kết quả sai
Bước 3: Kết luận
Đáp án: - Điều kiện: Danh sách phải được sắp xếp theo thứ tự (tăng dần hoặc giảm dần) trước khi thực hiện tìm kiếm nhị phân. - Nếu không thoả mãn: Thuật toán tìm kiếm nhị phân KHÔNG thể thực hiện được (hoặc sẽ cho kết quả sai).
💡 Mẹo nhớ: "Muốn nhị phân tìm đúng, danh sách phải xếp thứ tự trước!"
🎯 Ghi nhớ: - Tìm kiếm tuần tự: Duyệt từ đầu đến cuối, đơn giản nhưng chậm với danh sách lớn. - Tìm kiếm nhị phân: Chia đôi danh sách mỗi bước, nhanh hơn nhiều nhưng yêu cầu danh sách đã được sắp xếp. - Với danh sách n phần tử, tìm kiếm nhị phân chỉ cần khoảng log₂(n) bước, trong khi tìm kiếm tuần tự có thể cần đến n bước.