CHỦ ĐỀ 5: BÀI 15: THUẬT TOÁN TÌM KIẾM NHỊ PHÂN
Trang bìa
Trang bìa
Ảnh
TIN HỌC 7
CHỦ ĐỀ 5: BÀI 15: THUẬT TOÁN TÌM KIẾM NHỊ PHÂN
Ảnh
Mục tiêu bài học
Mục tiêu bài học
Ảnh
Hình vẽ
Giải thích được thuật toán tìm kiếm nhị phân. Biểu diễn và mô phỏng được hoạt động của thuật toán tìm kiếm nhị phân trên một bộ dữ liệu vào có kích thước nhỏ. Giải thích được mối liên quan giữa sắp xếp và tìm kiếm, nêu được ví dụ minh họa..
Học xong bài này, em sẽ:
Khởi động
Khởi động
Hình vẽ
Khởi động
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?
Ảnh
1. Thuật toán tìm kiếm nhị phân
1. Kiến thức mới 1
1. Kiến thức mới 1
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 theo 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.
Ảnh
- Ý 2 (1. Kiến thức mới 1)
Hình vẽ
Giả sử: An cần tìm địa chỉ của khách hàng tên là " Trúc" trong danh sách. Khi danh sách được sắp xếp, An không cần tìm từ đầu mà so sánh giá trị cần tìm với giá trị của vị trí ở giữa danh sách.
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.
=> 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.
- Các bước tìm kiếm khách hàng tên 'Trúc"
Bước 1: Xét vị trí ở giữa của dãy, đó là vị trí số 5
- Các bước tìm kiếm khách hàng tên 'Trúc"
Ảnh
- Bước 3 và 4 ( - Các bước tìm kiếm khách hàng tên 'Trúc")
Bước 2: Xét vị trí ở giữa của nửa sau của dãy là vị trí số 7
Ảnh
Ảnh
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ác hàng nên thuật toán kết thúc.
2. Hoạt động 2: Sắp xếp và tìm kiếm
Ảnh
Hình vẽ
2. Hoạt động 2: Sắp xếp và tìm kiếm
1. 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. 2. 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ã đ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?
3. Kiến thức mới 2
Hình vẽ
3. Kiến thức mới 2
Mô tả thuật toán tìm kiếm nhị phân bằng ngôn ngữ tự nhiên:
Bước 1: Nếu vùng tìm kiếm không có phần tử nào thì kết luận không tìm thất và thuật toán kết thúc. Bước 2: Xác định vị trí giữa của vùng tìm kiếm. Bước 3: Nếu giá trị cần tìm bằng giá trị của vị trí giữa thì kết luận "giá trị cần tìm xuất hiện tại vị trí giữa' và kết thúc. Bước 4: Nếu giá trị cần tìm nhỏ hơn giá trị của vị trí giữa thì vùng tìm kiếm mới được thu hẹp lại, chỉ còn nửa trước của dãy. Ngược lại vùng tìm kiếm mới được thu hẹp, chỉ còn nửa sau của dãy.
- Bước 5
Ảnh
Hình vẽ
Bước 5: Lặp lại từ Bước 1 đến Bước 3 cho đến khi tìm thấy giá trị cần tìm (Bước 3) hoặc vùng tìm kiền không còn phần tử nào (Bước 1).
Ảnh
4. Kết luận
Hình vẽ
4. Kết luậ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. Chừng nào chưa tìm thất và vùng tìm kiếm còn phần tử thì còn tiếp.
Thuật toán tìm kiếm nhị phân:
5. Câu hỏi
Ảnh
5. Câu hỏi
Em hãy 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 "Hòa" trong danh sách ở Hình 15.1.
2. Sắp xếp và tìm kiếm
1. Kiến thức mới
Hình vẽ
1. Kiến thức mới
Xét trường hợp: Một khách hàng nào đó, mẹ An quên chưa ghi vào sổ do đó tên khách hàng không có trong danh sách.
Để tìm kiếm tên khách hàng này:
Thuật toán tìm kiếm tuần tự: 9 bước lặp để xét hết danh sách và kết luận " không tìm thấy". Thuật toán tìm kiếm nhị phân: 4 bước lặp để xét hết danh sách và kết luận " không tìm thấy".
=> Thuật toán tìm kiếm nhị phân thực hiện tìm kiếm nhanh hơn thuật toán tuần tự.
2. Kết luận
Hình vẽ
2. Kết luận
Sắp xếp giúp cho việc tìm kiếm được nhanh hơn.
Ảnh
3. Hoạt động 2: Trò chơi tìm số
3. Hoạt động 2: Trò chơi tìm số
Hình vẽ
Hai bạn chơi A, B và 10 tấm thẻ ghi 10 số khác nhau (các số đều nhỏ hơn 20). Yêu cầu: Bạn B sử dụng thuật toán tìm kiếm để tìm một số nhỏ hơn 20 trong các tấm thẻ của bạn A. Hoán đổi vị trí A và B trong lượt chơi tiếp theo.
Ảnh
4. Câu hỏi
4. Câu hỏi
Ảnh
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.
3. Luyện tập
Câu 1
Ảnh
Câu 1:
Cho danh sách tên các nước sau: Bolivia, Albania, Scotland, Canada, Vietnam, Iceland, Portugal, Greenland, 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 lặp 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 lặp thực hiện tìm kiếm ở phần b với số bước lặp thực hiện tìm kiếm ở phần Luyện tập của bài 14.
Câu 2
Ảnh
Câu 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 đó.
4. Vận dụng
Vận dụng
Ảnh
Vận dụng
Em hãy 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 đó?
Dặn dò
1. Dặn dò
Ảnh
Dặn dò
Ôn lại bài vừa học. Làm bài tập trong SBT. Chuẩn bị bài mới:"Chủ đề 5: Bài 16: Thuật toán tìm kiếm sắp xếp".
2. Kết bài
Ảnh
Ảnh
Ảnh