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 để tìm kiếm được dễ dàng hơn không?
Bài 15: Thuật toán tìm kiếm nhị phân
Khởi động (SGK Kết nối tri thức với cuộc sống - Trang 74)
Thảo luận (1)
Hoạt động 1.1 (SGK Kết nối tri thức với cuộc sống - Trang 75)
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 khách hàng tên Trúc như ở 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 thuật toán tìm kiếm nhị phân.
Thảo luận (1)Hướng dẫn giải+ Phải thực hiện 8 lần để tìm được khách hàng tên “Trúc”.
+ Thuật toán tìm kiếm nhị phân chỉ thực hiện 3 lần lần để tìm được khách hàng tên “Trúc”.
(Trả lời bởi Tuyet)
Hoạt động 1.2 (SGK Kết nối tri thức với cuộc sống - Trang 75)
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 thỏa mãn điều kiện gì? Nếu không thỏa 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?
Thảo luận (1)Hướng dẫn giảiDanh 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ứ tự từ nhỏ đến lớn thì thuật toán tìm kiếm nhị phân không thực hiện được.
(Trả lời bởi Tuyet)
Câu hỏi mục 1 (SGK Kết nối tri thức với cuộc sống - Trang 76)
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 "Hòa" trong danh sách ở Hình 15.1.
Thảo luận (1)Hướng dẫn giảiB1: Xét vị trí ở giữa của dãy, đó là vị trí số 5
=> So sánh Hoà và Mai
+ “H” đứng trước “M” trong bảng chữ cái nên bỏ đi nữa sau danh sách.
B2: Xét vị trí ở giữa của nửa đầu của dãy là 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.
(Trả lời bởi Tuyet)
Câu hỏi mục 2 (SGK Kết nối tri thức với cuộc sống - Trang 77)
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.
Thảo luận (1)Hướng dẫn giảiTrong 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
VD :
Nguyễn Tích Trường An
Hải Anh
(Trả lời bởi Tuyet)
Luyện tập 1 (SGK Kết nối tri thức với cuộc sống - Trang 77)
Cho danh sách tên các nước sau đây:Bolivia, Albania, Scotland, Canada, Vietnam, Iceland, Portugal, Greendland, Germanya) 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.
Đọc tiếp
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.
Thảo luận (1)Hướng dẫn giảitham khảo
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
- 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.
(Trả lời bởi Mai Trung Hải Phong)
Luyện tập 2 (SGK Kết nối tri thức với cuộc sống - Trang 77)
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 đó.
Thảo luận (1)Hướng dẫn giảiVí 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.
(Trả lời bởi Mai Trung Hải Phong)
Vận dụng (SGK Kết nối tri thức với cuộc sống - Trang 77)
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 đó?
Thảo luận (1)Hướng dẫn giảitham khảo
Em tìm một từ tiếng Anh trong quyển từ điển bằng cách chia đổi quyển từ điển, tìm một từ bất kì ở giữa quyển từ điển và so sánh với từ cần tìm. Nếu tìm thấy từ đó thì sẽ kết thúc việc tìm kiếm. Nếu chưa em lại tiếp tục chia quyển từ điển theo nửa thích hợp, đến khi nào tìm được từ cần tìm thì kết thúc. Em dùng cách này vì nhanh chóng và thuận tiện hơn là tìm kiếm từng từ trong bảng chữ cái.
(Trả lời bởi Mai Trung Hải Phong)