Rõ nét về file powerpoint trình chiếu. => Xem thêm
Ngày soạn:…/…/…
Ngày dạy:…/…/…
CHỦ ĐỀ 5: GIẢI QUYẾT VẤN ĐỀ VỚI SỰ TRỢ GIÚP CỦA MÁY TINH
BÀI 14: THUẬT TOÁN TÌM KIẾM TUẦN TỰ
I. MỤC TIÊU
Sau bài học này, HS sẽ:
III. TIẾN TRÌNH DẠY HỌC
- GV yêu cầu HS thảo luận theo cặp đôi và trả lời câu hỏi: Gia đình bạn An bán giống cây cho bà con nông dân trong vùng. Hôm nay có một khách hàng gọi điện đến mua cây giống và nhờ mẹ An chở giống cây đến nhà. Thông tin khách hàng được mẹ An ghi trong cuốn số lưu danh sách khách hàng gồm họ, tên, địa chỉ, số điện thoại. Em hãy cùng An giúp mẹ tìm địa chỉ từ danh sách khách hàng để chuyển cây giống nhé.
- GV hướng dẫn HS đọc thông tin Thuật toán tìm kiếm tuần tự và quan sát Sơ đồ khối mô tả thuật toán tìm kiếm tuần tự địa chỉ khách hàng SGK tr.71, 72.
- HS tiếp nhận, thực hiện nhiệm vụ.
- GV nhấn mạnh cho HS: Điều kiện của vòng lặp tìm kiếm là chừng nào chưa tìm thấy và chưa tìm hết thì còn tìm tiếp.
- GV dẫn dắt vài bài: Để giải thích được thuật toán tìm kiếm tuyến tính, biểu diễn và mô phỏng được hoạt động của thuật toán đó trên một bộ dữ liệu vào có kích thước nhỏ, chúng ta cùng tìm hiểu trong bài học ngày hôm nay – Bài 14: Thuật toán tìm kiếm tuần tự.
HOẠT ĐỘNG HÌNH THÀNH KIẾN THỨC
Hoạt động 1: Tìm địa chỉ
HOẠT ĐỘNG CỦA GIÁO VIÊN - HỌC SINH | DỰ KIẾN SẢN PHẨM | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Bước 1: GV chuyển giao nhiệm vụ học tập - GV yêu cầu HS quan sát, đọc Danh sách khách hàng được mẹ An ghi trong Bảng 14.1 như sau: Bảng 14.1. Danh sách khách hàng
- GV yêu cầu HS thực hiện nhiệm vụ: Em hãy kẻ Bảng 14.2 vào vở và điền các bước thực hiện thuật toán tìm kiếm tuần tự để tìm ra địa chỉ của khách hàng có tên là Thanh Trúc. Bảng 14.2. Các bước tìm địa chỉ khách hàng
- GV yêu cầu HS đọc thông tin Mô tả thuật toán tìm kiếm tuần tự bằng ngôn ngữ tự nhiên SGK tr.73 và yêu cầu HS trả lời câu hỏi: Em hãy nêu các bước mô tả thuật toán tìm kiếm tuần tự bằng ngôn ngữ tự nhiên. - GV chốt kiến thức: Thuật toán tìm kiếm tuần tự thực hiện lần lượt từ đầu đến cuối danh sách, chừng nào chưa tìm thấy và chưa tìm hết thì còn tìm tiếp. - GV yêu cầu HS thảo luận theo cặp đôi và trả lời câu hỏi củng cố kiến thức: 1. Thuật toàn tìm kiếm tuần tự thực hiện công việc gì? A. Lưu trữ dữ liệu. B. Sắp xếp dữ liệu theo chiều tăng dần. C. Xử lí dữ liệu. D. Tìm kiếm dữ liệu cho trước trong một danh sách đã cho. 2. Thuật toán tìm kiếm tuần tự thực hiện công việc như thế nào? A. Sắp xếp lại dữ liệu theo thứ tự của bảng chữ cái. B. Xem xét mục dữ liệu đầu tiên, sau đó xem xét từng mục dữ liệu tiếp theo cho đến khi tìm thấy mục dữ liệu được yêu cầu hoặc đến khi hết danh sách. C. Chia nhỏ dữ liệu thành từng phần để tìm kiếm. D. Bắt đầu tìm từ vị trí bất kì của danh sách. Bước 2: HS thực hiện nhiệm vụ học tập - HS quan sát sơ đồ, thảo luận theo cặp đôi và trả lời câu hỏi. - GV hướng dẫn, theo dõi, hỗ trợ HS nếu cần thiết. Bước 3: Báo cáo kết quả hoạt động và thảo luận - GV mời đại diện 2-3 HS trả lời. - GV mời HS khác nhận xét, bổ sung. Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập GV đánh giá, nhận xét, chuẩn kiến thức, chuyển sang nội dung mới. | 1. Tìm địa chỉ
Bước 4: Tìm thấy tên khách hàng hàng nên ghi ra địa chỉ của khách hàng và kết thúc thuật toán. - Các bước mô tả thuật toán tìm kiếm tuần tự bằng ngôn ngữ tự nhiên: + Bước 1: Xét phần tử đầu tiên của danh sách. + Bước 2: Nếu giá trị của phần tử đang xét bằng giá trị cần tìm thì chuyển sang Bước 4, nếu không thì thực hiện bước tiếp theo (Bước 3). + Bước 3: Kiểm tra đã hết danh sách chưa. Nếu đã hết danh sách thì chuyển sang Bước 5, nếu chưa thì lặp lại từ Bước 2. + Bước 4: Trả lời Tìm thấy và chỉ ra vị trí phần tử tìm được; Kết thúc. + Bước 5: Trả lời Không tìm thấy; Kết thúc. - Đáp án câu hỏi củng cố: 1. D. 2. B |
- GV giao nhiêm vụ cho HS: Trả lời câu hỏi phần Luyện tập SGK tr.73.
- HS tiếp nhận, thực hiện nhiệm vụ:
Các bước thực hiện thuật toán tìm kiếm tuần tự để tìm tên nước Iceland trong danh sách được mô tả trong bảng sau:
Lần lặp | Tên nước | Có đúng tên nước cần tìm không? | Có đúng là đã hết danh sách không? | Đầu ra |
1 | Bolivia | Sai | Sai |
|
2 | Albani | Sai | Sai |
|
3 | Scotland | Sai | Sai |
|
4 | Canada | Sai | Sai |
|
5 | Vietnam | Sai | Sai |
|
6 | Iceland | Đúng |
| Tìm thấy ở vị trí số 6 |
- GV nhận xét, đánh giá, chuẩn kiến thức.
- GV giao nhiêm vụ cho HS: Trả lời câu hỏi Vận dụng SGK tr.73.
- HS tiếp nhận, thực hiện nhiệm vụ:
Gợi ý: HS lập bảng liệt kê các bước tương tự mô phỏng trong SGK để thực hiện thuật toán tìm kiếm tuần tự.
- GV nhận xét, đánh giá, chuẩn kiến thức.
Hình thức đánh giá | Phương pháp đánh giá | Công cụ đánh giá | Ghi chú |
Đánh giá thường xuyên (GV đánh giá HS, HS đánh giá HS) | - Vấn đáp. - Kiểm tra viết, kiểm tra thực hành. | - Các loại câu hỏi vấn đáp, bài tập. |
|
Nâng cấp lên tài khoản VIP để tải tài liệu và dùng thêm được nhiều tiện ích khác