Bài giảng Tin học 7 - Bài 15: Thuật Toán tìm kiếm nhị phân

Nội dung text: Bài giảng Tin học 7 - Bài 15: Thuật Toán tìm kiếm nhị phân

1. TIN HỌC 7 Bài 15: THUẬT TOÁN TÌM KIẾM NHỊ PHÂN
2. Bài 15: THUẬT TOÁN TÌM KIẾM NHỊ PHÂN
3. Bài 15: THUẬT TOÁN TÌM KIẾM NHỊ PHÂN 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?
4. Bài 15: THUẬT TOÁN TÌM KIẾM NHỊ PHÂN 1. THUẬT TOÁN TÌM KIẾM NHỊ PHÂN Khi danh sách khách hàng ngày càng nhiều, để thuận lợi cho việc tìm kiếm, An đã giúp mẹ 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. Giả sử An cần tìm địa chỉ của khách hàng tên là “Trúc” trong danh sách khách hàng như Hình 15.1.1
5. THẢO LUẬN NHÓM
6. Câu 1: Khi danh sách đã được sắp xếp, An không cần tìm từ đầu mà so sánh ngay giá trị cần tìm với giá trị của vị trí ở giữa danh sách. Đáp án Câu 2: Hoạt động được lặp lại trong giải pháp của An: - Nếu giá trị cần tìm bằng giá trị ở giữa thì tìm thấy và dừng lại - Nếu lớn hơn thì chỉ cần tìm ở nửa sau của danh sách - Nếu nhỏ hơn thì tìm ở nửa đầu của danh sách. Lặp lại quá trình đó cho đến khi tìm thấy hoặc hết danh sách  Như vậy, tại mỗi bước lặp, thuật toán tìm kiếm thu hẹp danh sách tìm kiếm chỉ còn một nửa. Do đó thuật toán này có tên là tìm kiếm nhị phân (chia đôi).
7. Bài 15: THUẬT TOÁN TÌM KIẾM NHỊ PHÂN Các bước để An tìm khách hàng tên “Trúc” trong danh sách ở Hình 15.1 theo thuật toán tìm kiếm nhị phân như sau: Bước 1. Xét vị trí ở giữa của dãy, đó là vị trí số 5
8. Bài 15: THUẬT TOÁN TÌM KIẾM NHỊ PHÂN Bước 2. Xét vị trí ở giữa của nửa sau của dãy là vị trí số 7
9. Bài 15: THUẬT TOÁN TÌM KIẾM NHỊ PHÂN Bước 3. Xét vị trí ở giữa của nửa sau còn lại của dãy, đó là vị trí số 8 Vì sau bước 3 đã tìm thấy tên khách hàng nên thuật toán kết thúc.
10. Bài 15: THUẬT TOÁN TÌM KIẾM NHỊ PHÂN
11. Bài 15: THUẬT TOÁN TÌM KIẾM NHỊ PHÂN Đáp án: Câu 1: Thuật toán tìm kiếm tuần tự phải thực hiện 8 bước để tìm khách hàng tên “Trúc” trong danh sách ở H15.2, trong khi thuật toán tìm kiếm nhị phân chỉ thực hiện 4 bước. Như vậy thuật toán tìm kiếm nhị phân nhanh hơn. Câu 2: Trước khi thực hiện thuật toán tìm kiếm nhị phân, danh sách tên khách hàng cần được sắp xếp. Nếu không được sắp xếp, thuật toán tìm kiếm nhị phân không thể thu hẹp phạm vi tìm kiếm vì giá trị cần tìm có thể ở vị trí bất kì trong danh sách.
12. Bài 15: THUẬT TOÁN TÌM KIẾM NHỊ PHÂN
13. THẢO LUẬN NHÓM
14. Bài 15: THUẬT TOÁN TÌM KIẾM NHỊ PHÂN - Vị trí giữa của vùng tìm kiếm = phần nguyên của(vị trị đầu +vị trí cuối)/2 - Điều kiện để dừng tìm kiếm là khi tìm thấy giá trị cần tìm hoặc vùng tìm kiếm không còn phần tử nào. - 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 theo thứ tự từ nhỏ đến lớn.Bắt đầu từ vị trí ở giữa danh sách. + Tại mỗi bước lặp, so sánh giá trị cần tìm với giá trị của vị trí giữa danh sách, nếu bằng thì dừng lại, nếu nhỏ hơn thì tìm trong nửa trước của danh sách, nếu lớn hơn thì tìm trong nửa sau của danh sách. + Khi nào chưa tìm thấy và vùng tìm kiếm còn phần tử thì còn tìm tiếp.
15. Em hãy 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 đó?
16. THANK YOU