Kế hoạch bài dạy Tin học Lớp 7 Sách Kết nối tri thức - Tiết 13, Bài 15: Thuật toán tìm kiếm nhị phân - Năm học 2022-2023 - Lê Thị Hương

Nội dung tài liệu: Kế hoạch bài dạy Tin học Lớp 7 Sách Kết nối tri thức - Tiết 13, Bài 15: Thuật toán tìm kiếm nhị phân - Năm học 2022-2023 - Lê Thị Hương

1. Giáo án dự thi giáo viên giỏi huyện Ngày soạn: 04/12/2022 Ngày dạy: 07/12/2022 TIẾT 13: BÀI 15 THUẬT TOÁN TÌM KIẾM NHỊ PHÂN 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ỏ 2. Năng lực: 2.1. Năng lực chung Thực hiện bài học này sẽ góp phần hình thành và phát triển một số thành tố năng lực chung của học sinh như sau: - Năng lực tự học: HS có khả năng tự đọc SGK, kết hợp với gợi ý và dẫn dắt của GV để trả lời các câu hỏi. - Năng lực giao tiếp và hợp tác: HS có khả năng hoạt động nhóm để hoàn thành các nhiệm vụ học tập. - Năng lực giải quyết vấn đề và sáng tạo: HS đưa ra thêm một số ví dụ về các tìm kiếm nhị phân 2.2. Năng lực Tin học Thực hiện bài học này sẽ góp phần hình thành và phát triển một số thành tố năng lực Tin học của học sinh như sau: Năng lực A (NLa): - Phát triển năng lực sử dụng và quản lý các phương tiện công nghệ thông tin và truyền thông. Năng lực C (NLc): - Nhận biết các hoạt động sử dụng tìm kiếm nhị phân. - Viết được thuật toán dưới dạng liệt kê hoặc sơ đồ khối. - Lập được các bước mô phỏng thuật toán. Năng lực D (NLd): Lê Thị Hương năm học 2022-2023
2. Giáo án dự thi giáo viên giỏi huyện - Năng lực ứng dụng công nghệ thông tin và truyền thông trong học và tự học. Năng lực E (NLe): - Năng lực hợp tác trong môi trường số. 3. Phẩm chất: Nghiêm túc, tập trung, tích cực chủ động. 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, máy chiếu vật thể. 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 1 :KHỞI ĐỘNG (MỞ ĐẦU) - Mục tiêu: Tạo hứng thú học tập cho học sinh - Nội dung: Hs dựa vào hiểu biết để trả lời câu hỏi - Sản phẩm: Từ yêu cầu Hs vận dụng kiến thức để trả lời câu hỏi GV đưa ra - Tổ chức thực hiện: GV giới thiệu và dẫn dắt vào bài - GV cho học sinh quan sát danh sách khách hàng và đưa ra câu hỏi ? Dùng thuật toán tìm kiếm tuần tự em hãy mô tả cách tìm khách hàng tên “ Trúc” - Hs trả lời - GV nhận xét ? Để tìm khách hàng tên “ Trúc” em đã thực hiện bao nhiều bước? - Hs trả lời GV: Cho đưa ra tình huống cho học sinh nghiên cứu và tìm ra cách giải quyết tình huống đó: 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 Lê Thị Hương năm học 2022-2023
3. Giáo án dự thi giáo viên giỏi huyện HS: Trả lời câu hỏi GV: Đánh giá kết quả. Vậy thuật toán tìm kiếm nhị phân là thuật toán như thế nào chúng ta cùng nhau tìm hiểu trong bài học ngày hôm nay 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 2: Tìm hiểu thuật toán tìm kiếm nhị phân - Mục Tiêu: Nắm được nội dung thuật toán tìm kiếm nhị phân - 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 - Sản phẩm: Hs hoàn thành tìm hiều kiến thức - Tổ chức thực hiện: Hoạt động của GV và HS Sản phẩm dự kiến - Ý tưởng thuật toán tìm kiếm nhị 1.THUẬT TOÁN TÌM KIẾM NHỊ PHÂN phân: - Ý tưởng thuật toán tìm kiếm nhị phân: - GV cho học sinh quan sát các + Danh sách khách hàng đã được sắp xếp theo thứ tự bước tìm kiếm nhị phân tìm khách chữ cái hàng có tên “ Trúc” trong hình 15.1 sgk và yêu cầu học sinh trả lời câu + So sánh giá trị cần tìm với giá trị ở vị trí giữa danh hỏi sách. ? Chỉ ra vị trí đầu? vị trí cuối? cách + Nếu giá trị cần tìm bằng giá trị ở giữa thì tìm thấy và tìm vị trí ở giữa? 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. - Hs quan sát và trả lời + Lặp lại quá trình đó cho đến khi tìm thấy hoặc hết - GV nhận xét danh sách. - Minh họa Lê Thị Hương năm học 2022-2023
4. Giáo án dự thi giáo viên giỏi huyện Hoạt động của GV và HS Sản phẩm dự kiến Bước 1. Xét vị trí ở giữa của dãy, đó là vị trí số 5 Bước 2. Xét vị trí ở giữ của nửa sau của dãy là vị trí số 7 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 * GV giao nhiệm vụ học tập: * Bước 1: Chuyển giao nhiệm vụ: GV: Tổ chức các hoạt động HĐ1 1. Em hãy cho biết thuật toán tìm Lê Thị Hương năm học 2022-2023
5. Giáo án dự thi giáo viên giỏi huyện Hoạt động của GV và HS Sản phẩm dự kiến kiếm tuần tự phải thực hiện 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 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 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? HS: Thảo luận, trả lời * Bước 2: Thực hiện nhiệm vụ: + HS: Suy nghĩ, tham khảo sgk trả lời câu hỏi + GV: quan sát và trợ giúp các cặp. * Bước 3: Báo cáo, thảo luận: + HS: Lắng nghe, ghi chú, một HS phát biểu lại các tính chất. + Các nhóm nhận xét, bổ sung cho nhau. * Bước 4: Kết luận, nhận định: GV chính xác hóa và gọi 1 học sinh nhắc lại kiến thức - Mô tả thuật toán tìm kiếm nhị phân bằng ngôn ngữ * GV dẫn dắt cho học sinh phát tự nhiên: biểu mô tả thuật toán tìm kiếm nhị phâ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ấy và thuật toán kết thúc. ? Nếu giá tìm bạn có tên “Ngọc” trong danh sách hình 15.1 ta làm Bước 2. Xác định vị trí giữa của vùng tìm kiếm. Vị trí như thế nào? này chia vùng tìm kiếm thành hai nửa: nửa trước và nửa sau vị trí giữa. - Hs trả lời Bước 3. Nếu giá trị cần tìm bằng giá trị của vị trí giữa - GV chốt bước 1 thì kết luận “giá trị cần tìm xuất hiện tại vị trí giữa” và ? Bước tiếp theo chúng ta thực hiện Lê Thị Hương năm học 2022-2023
6. Giáo án dự thi giáo viên giỏi huyện Hoạt động của GV và HS Sản phẩm dự kiến như thế nào? kết thúc - Hs trả lời Bước 4. Nếu giá trị cần tìm nhỏ hơn giá trị của vị trí - GV chốt kt giữa 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 (nếu giá trị cần tìm lớn hơn giá trị của vị trí giữa) vùng tìm kiếm mới được thu hẹp lại, chỉ còn nửa sau của dãy. Bước 5. Lặp lại từ Bước 1 đến Bước 4 cho đến khi tìm thấy giá trị cần tìm (Bước 3) hoặc vùng tìm kiếm không còn phần tử nào (Bước 1) Lưu ý: “nửa trước” và “nửa sau” không gồm phần tử giữa - GV ? Vậy Thuật toán tìm kiếm nhị phân có đặc điểm như thế nào? Ghi nhớ: 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. Bắt đầu từ - Hs trả lời vị trí ở giữa danh sách. - GV chốt kiến thức trọng tâm. - Tại mỗi bước, so sánh giá trị cần tìm với giá trị của vị trí giữa danh sách, nếu lớn hơn thì tìm trong nửa sau của danh sách, nếu nhỏ hơn tìm trong nửa trước của danh sách, nếu bằng thì dừng lại. - Chừng nào chưa tìm thấy và chưa hết danh sách thì còn tìm tiếp Vận dụng * GV giao nhiệm vụ học tập ? Em hãy viết các bước thực hiện thuật toán tìm kiếm GV chia học sinh theo nhóm nhị phân để tìm khách hàng tên “Hòa” trong danh sách - GV yêu cầu học sinh làm phiếu ở hình 15.1 bài tập * HS thực hiện nhiệm vụ Thực hiện yêu cầu của GV. * Báo cáo, thảo luận - Hết thời gian làm bài. GV chữa 1 Lê Thị Hương năm học 2022-2023
7. Giáo án dự thi giáo viên giỏi huyện Hoạt động của GV và HS Sản phẩm dự kiến nhóm đại diện - Hs nhóm khác nhận xét - GV đưa ra đáp án. Yêu cầu HS chấm chéo cho nhóm bạn. * Kết luận, nhận định - GV nhận xét kết quả thực hiện nhiệm vụ, chốt kết quả cuối cùng. 3. HOẠT ĐỘNG 3 :LUYỆN TẬP a) Mục tiêu: - HS vận dụng được kiến thức về thuật toán tìm kiếm nhị phân để tìm ra nước Iceland. - liệt kê các bước tìm kiếm tên các nước Iceland trong danh sách đã sắp xếp theo thuật toán tìm kiếm nhị phân. b) Nội dung: Làm bài tập cá nhân c) Sản phẩm: Làm bài tập vào vở ghi. d) Tổ chức thực hiện: Hoạt động của GV và HS Dự kiến sản phẩm * GV giao nhiệm vụ học tập Bài 1. Cho danh sách tên các nước - GV chiếu lên bảng rồi gọi học sinh lên sau đây: Bolivia, Albania, Scotland, Canada, Vietnam, làm Iceland, Portugal, Greenland, - Hs bên dưới làm vào vở Germany. * HS thực hiện nhiệm vụ a) Em hãy sắp xếp danh sách tên các nước theo thứ tự trong bảng Thực hiện yêu cầu của GV. chữ cái * Báo cáo, thảo luận b) Em hãy liệt kê các bước tìm - Hết thời gian làm bài. GV yêu cầu HS kiếm tên các nước Iceland trong danh sách đã sắp xếp theo thuật ngồi cùng bàn đổi vở cho nhau. toán tìm kiếm nhị phân. - GV đưa ra đáp án. Yêu cầu HS chấm bài Lê Thị Hương năm học 2022-2023
8. Giáo án dự thi giáo viên giỏi huyện Hoạt động của GV và HS Dự kiến sản phẩm cho bạn. * Kết luận, nhận định - GV nhận xét kết quả thực hiện nhiệm vụ, chốt kết quả cuối cùng. 4. HOẠT ĐỘNG 4: VẬN DỤNG a. Mục tiêu: Vận dụng các kiến thức vừa học quyết các vấn đề học tập và thực tiễn. b. Nội dung:. c. Sản phẩm: HS vận dụng các kiến thức vào giải quyết các nhiệm vụ đặt ra. d. Tổ chức thực hiện: Gv đưa câu hỏi về nhà: Bài 2(sgk t77) 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 đó. 5. HOẠT ĐỘNG 5 : HDVN - Hướng dẫn học bài cũ: - Hướng dẫn chuẩn bị bài mới xem trước phần 2 sắp xếp và tìm kiếm PHỤ LỤC PHIẾU HỌC TẬP ? 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 “ Hoà” trong danh sách ở hình 15.1 Bước 1: Bước 2 Bước 3 . Lê Thị Hương năm học 2022-2023
9. Giáo án dự thi giáo viên giỏi huyện Người soạn Lê Thị Hương Lê Thị Hương năm học 2022-2023