Giáo án Tin học 7 Kết nối tri thức Chủ đề 5 Bài 15 Thuật toán tìm kiếm nhị phân

Bài 15. Thuật toán tìm kiếm nhị phân
Môn học: Tin Học; Lớp: 7
Thời gian thực hiện: 2 tiết I. MỤC TIÊU
1. Kiến thức:
- 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 hệ giữa sắp xếp và tìm kiếm, nêu được ví dụ minh họa.
2. Năng lực:
- Năng lực tự chủ và tự học
- Năng lực giao tiếp và hợp tác
- Năng lực sáng tạo và giải quyết vấn đề
3. Phẩm chất:
- Nghiêm túc, tập trung, tích cực chủ động.
- Rèn luyện phẩm chất chăm chỉ, kiên trì và cẩn thận.
II. THIẾT BỊ DẠY HỌC VÀ HỌC LIỆU 1. Giáo viên
- Chuẩn bị bài giảng, máy chiếu. - Sách giáo khoa.
- Một số tấm thẻ ghi con số, dùng cho hoạt động mô phỏng thuật toán tìm kiếm nhị phân. 2. Học sinh - Sách giáo khoa, vở ghi. - Kiến thức đã học.
III. TIẾN TRÌNH DẠY HỌC
1. HOẠT ĐỘNG KHỞI ĐỘNG (MỞ ĐẦU)


a) Mục tiêu: Tạo hứng thú học tập cho học sinh
b) Nội dung: HS dựa vào hiểu biết để giải quyết tình huống.
c) Sản phẩm: Cách giải quyết của HS.
d) Tổ chức thực hiện:
- GV cho HS đọc tình huống trong SGK trang 74.
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?
GV yêu cầu HS đưa ra cách giải quyết tình huống trên.
- HS đọc tình huống và trả lời: Gợi ý trả lời:
- Sắp xếp danh sách để tìm dễ hơn.
- Đưa danh sách vào phần mềm soạn thảo văn bản hoặc bảng tính và sử dụng
chức năng tìm kiếm của phần mềm để tìm kiếm.
- Từ câu trả lời của HS, GV nhấn mạnh nhu cầu cần có thuật toán tìm kiếm khác để
giải quyết bài tìm kiếm nhanh hơn và cách tìm kiếm nhanh hơn tìm trên một danh
sách đã được sắp xếp. - GV dẫn dắt vào bài:
Đối với danh sách đã sắp xếp, để tìm nhanh chóng, ta có thể sử dụng thuật
toán tìm kiếm nhị phân. Hôm nay, chúng ta tiến hành tìm hiểu Bài 15_Thuật toán
tìm kiếm nhị phân.
2. HÌNH THÀNH KIẾN THỨC MỚI
Hoạt động 1: Tìm hiểu thuật toán tìm kiếm nhị phân
a) Mục tiêu: Nắm được nội dung thuật toán tìm kiếm nhị phân
b) Nội dung: HS quan sát SGK để tìm hiểu nội dung kiến thức theo yêu cầu của GV


c) Sản phẩm: HS hoàn thành tìm hiểu kiến thức
d) Tổ chức thực hiện:
Hoạt động của GV và
Sản phẩm dự kiến HS
1. THUẬT TOÁN TÌM KIẾM NHỊ PHÂN
* Bước 1: Chuyển giao
- Ý tưởng thuật toán tìm kiếm nhị phân: nhiệm vụ:
+ Danh sách khách hàng đã được sắp xếp theo thứ tự chữ GV: Tổ chức các hoạt cái động
+ So sánh giá trị cần tìm với giá trị ở vị trí giữa danh sách. HĐ1
+ Nếu giá trị cần tìm bằng giá trị ở giữa thì tìm thấy và - GV yêu cầu HS đọc
dừng lại, nếu lớn hơn thì chỉ cần tìm ở nửa sau của danh hiểu phần kiến thức mới
sách, nếu nhỏ hơn thì tìm ở nửa đầu của danh sách. trong sách giáo khoa
+ Lặp lại quá trình đó cho đến khi tìm thấy hoặc hết danh trang 74-75 và diễn giải sách. hoạt động của thuật - Minh họa toán tìm kiếm nhị phân.
HS đọc hiểu và trả lời. - GV yêu cầu HS trao
đổi, thảo luận để trả lời hai câu hỏi sau: 1. Em hãy cho biết thuật toán tìm kiếm
tuần tự phải thực hiện
Bước 1. Xét vị trí ở giữa của dãy, đó là vị trí số 5 bao nhiêu bước để 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 thực hiện


Hoạt động của GV và
Sản phẩm dự kiến HS
của thuật toán tìm kiếm
tuần tự với số bước thực
hiện của thuật toán tìm kiếm nhị phân. 2. Theo em trước khi
Bước 2. Xét vị trí ở giữ của nửa sau của dãy là vị trí số 7
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
Bước 3. Xét vị trí ở giữa của nửa sau còn lại của dãy, đó tìm kiếm nhị phân có là vị trí số 8 thực hiện được không?
HS: Thảo luận, trả lời. - GV yêu cầu HS suy nghĩ, trả lời câu hỏi củng cố:
- Mô tả thuật toán tìm kiếm nhị phân bằng ngôn ngữ tự 1. Em hãy viết các bước nhiên:
thực hiện thuật toán tìm
Bước 1. Nếu vùng tìm kiếm không có phần tử nào thì kết kiếm nhị phân để tìm
luận không tìm thấy và thuật toán kết thúc. khách hàng tên “Hòa”
Bước 2. Xác định vị trí giữa của vùng tìm kiếm. Vị trí này trong danh sách ở hình
chia vùng tìm kiếm thành hai nửa: nửa trước và nửa sau vị 15.1. trí giữa. HS suy nghĩ, trả lời.
Bước 3. Nếu giá trị cần tìm bằng giá trị của vị trí giữa thì * Bước 2: Thực hiện