Bài giảng môn Tin học 7 (Kết nối tri thức) - Bài 14: Thuật toán tìm kiếm tuần tự - Võ Nhật Trường

Nội dung text: Bài giảng môn Tin học 7 (Kết nối tri thức) - Bài 14: Thuật toán tìm kiếm tuần tự - Võ Nhật Trường

1. GIẢI QUYẾT VẤN ĐỀ VỚI SỰ TRỢ GIÚP CỦA MÁY TÍNH  Tin 7 Bài 14. THUẬT TOÁN TÌM KIẾM TUẦN TỰ CHĂM NGOAN - HỌC TỐT Về kiến thức: -Giải thích được thuật toán tìm kiếm tuần tự. -Biểu diễn và mô phỏng được hoạt động của thuật toán tìm kiếm tuần tự trên một bộ dữ liệu vào có kích thước nhỏ.
2. Về năng lực: 2.1. Năng lực chung -Năng lực tự chủ, tự học: Học sinh chủ động và tích cực thực hiện nhiệm vụ học tập; vận dụng được những kiến thức, kĩ năng đã học để hoàn thành nhiệm vụ. -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 tuần tự. 2.2. Năng lực Tin học -Tư duy phân tích, thiết kế -Nhận biết các hoạt động sử dụng tìm kiếm tuần tự. -Viết được thuật toán dưới dạng liệt kê hoặc sơ đồ khối. -Lập được bảng mô phỏng thuật toán.
3. GIẢI QUYẾT VẤN ĐỀ VỚI SỰ TRỢ GIÚP CỦA MÁY TÍNH  Tin 7 Bài 14. THUẬT TOÁN TÌM KIẾM TUẦN TỰ CHĂM NGOAN - HỌC TỐT NỘI DUNG 1 Thuật toán tìm kiếm tuần tự. TRỌNG TÂM
4. KHÁM PHÁ
5. GIẢI QUYẾT VẤN ĐỀ VỚI SỰ TRỢ GIÚP CỦA MÁY TÍNH  Tin 7 Bài 14. THUẬT TOÁN TÌM KIẾM TUẦN TỰ CHĂM NGOAN - HỌC TỐT Gia đình bạn An bán giống cây trồng 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ở cây giống đế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é.
6. HOẠT ĐỘNG 1. Thuật toán tìm kiếm tuần tự.
7. GIẢI QUYẾT VẤN ĐỀ VỚI SỰ TRỢ GIÚP CỦA MÁY TÍNH  Tin 7 Bài 14. THUẬT TOÁN TÌM KIẾM TUẦN TỰ CHĂM NGOAN - HỌC TỐT 1. Thuật toán tìm kiếm tuần tự. *Công việc mà An cần làm có thể nêu thành bài toán tìm kiếm như sau: • Đầu vào: danh sách khách hàng: họ tên khách hàng cần tìm. • Đầu ra: địa chỉ của khách hàng cần tìm. *An thực hiện tìm kiếm lần lượt từ đầu đến cuối danh sách khách hàng. →Cách tìm kiếm này gọi là tìm kiếm tuần tự.
8. 1. Thuật toán tìm kiếm tuần tự. Với mỗi họ tên khách hàng trong danh sách, An kiểm tra xem có đúng họ tên khách hàng mà mẹ yêu cầu không. - Nếu đúng thì ghi ra địa chỉ và kết thúc công việc. - Nếu không đúng thì chuyển đến họ tên khách hàng tiếp theo. - Nếu tìm hết danh sách mà vẫn không thấy thì thông báo là không tìm thấy và kết thúc. *Như vậy, chừng nào chưa tìm thấy và chưa tìm hết thì còn tìm tiếp. → Đây chính là cấu trúc lặp. Hai điều kiện cần kiểm tra để dừng vòng lặp là: • Điều kiện thứ nhất: kiểm tra họ tên khách hàng có đúng là họ tên cần tìm không. • Điều kiện thứ hai: kiểm tra đã hết danh sách chưa.
9. 1. Thuật toán tìm kiếm tuần tự. Các bước thực hiện tìm kiếm địa chỉ khách hàng của An được mô tả ở sơ đồ khối trong Hình 14.1.
10. Nghiên cứu và thảo luận Tìm địa chỉ Lần Tên khách Có đúng khách hàng Có đúng là đã hết Địa chỉ lặp hàng cần tìm không? danh sách không? 1 Nguyễn An Sai? Sai? 2 Trần Bình Sai Sai 3 Hoàng Mai Sai Sai Xóm 2, Lục 4 Thanh Trúc Đúng Xuân, Hoà Hưng. 5 Nguyễn Hoà
11. GIẢI QUYẾT VẤN ĐỀ VỚI SỰ TRỢ GIÚP CỦA MÁY TÍNH  Tin 7 Bài 14. THUẬT TOÁN TÌM KIẾM TUẦN TỰ CHĂM NGOAN - HỌC TỐT 1. Thuật toán tìm kiếm tuần tự. Nghiên cứu và thảo luận Thuật toán Thuật toán tìm kiếm tuần tự thực hiện tìm Em hãy trình bày về lần lượt từ đầu đến cuối danh sách, chừng thuật toán tìm kiếm ? nào chưa tìm thấy và chưa tìm hết thì còn tuần tự? tìm tiếp.
12. 1. Thuật toán tìm kiếm tuần tự. Nghiên cứu và thảo luận Thuật toán 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 vị trí đầu tiên của danh sách. Em hãy -Bước 2. Nếu giá trị của phần tử ở vị trí đang xét bằng mô tả thuật giá trị cần tìm thì chuyển sang Bước 4, nếu không thì toán tìm chuyển đến vị trí tiếp theo. kiếm tuần -Bước 3. Kiểm tra đã hết danh? sách chưa. Nếu đã hết tự bằng danh sách thì chuyển sang Bước 5, nếu chưa thì lặp lại ngôn ngữ từ Bước 2. tự nhiên? -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.
13. Bài tập Câu hỏi Thuật toán tìm kiếm tuần tự thực hiện công việc gì? Lưu trữ dữ liệu. A B Sắp xếp dữ liệu theo chiều tăng dần. C Xử lí dữ liệu. Tìm kiếm dữ liệu cho trước trong một danh D sách đã cho.
14. Bài tập Câu hỏi Thuật toán tìm kiếm tuần tự thực hiện công việc như thế nào? Sắp xếp lại dữ liệu theo thứ tự bảng chữ cái. A Xem xét mục dữ liệu đầu tiên, sau đó xem xét từng mục dữ liệu B 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ì trong danh sách.
15. LUYỆN TẬP
16. Bài tập Câu hỏi Thuật toán tìm kiếm tuần tự yêu cầu danh sách tìm kiếm phải được sắp xếp? Đúng. A B Sai. C Cả A và B đều đúng. D Đáp án khác.
17. Bài tập Câu hỏi Mô tả thuật toán tìm kiếm tuần tự bằng ngôn ngữ tự nhiên gồm có mấy bước? 2 A B 3 C 4 D 5
18. Bài tập Câu hỏi Thuật toán tìm kiếm tuần tự một số trong dãy số A dừng khi nào? Nếu tìm thấy giá trị cần tìm trong dãy A. A Nếu tìm đến giá trị cuối trong dãy số mà không tìm thấy B giá trị cần tìm. Nếu tìm thấy giá trị cần tìm trong dãy A hoặc nếu tìm đến C giá trị cuối trong dãy số mà không tìm thấy giá trị cần tìm. D Đáp án khác.
19. Bài tập Câu hỏi Đâu là phát biểu đúng khi nói đến thuật toán tìm kiếm tuần tự? Thực hiện tìm lần lượt từ đầu đến cuối danh sách. A B Khi chưa tìm thấy và chưa tìm hết thì còn tìm tiếp. C Cả A, B đúng. D Cả A, B sai.
20. Bài tập Câu hỏi Để tìm kiếm một số trong dãy số bằng thuật toán tìm kiếm tuần tự, ta thực hiện: Lấy ngẫu nhiên một số trong dãy số để so sánh với số cần A tìm. So sánh lần lượt từ số đầu tiên trong dãy số với số cần B tìm. C Sắp xếp dãy số theo thức tự tăng dần. D So sánh số cần tìm với số ở giữa dãy số.