Giáo án Khoa học máy tính 11 cánh diều Chủ đề F(CS) Bài 7: Lập trình giải bài toán tìm kiếm

HOẠT ĐỘNG CỦA GV - HS

DỰ KIẾN SẢN PHẨM

Bước 1: GV chuyển giao nhiệm vụ học tập

Nhiệm vụ 1. Bài toán tìm kiếm

- GV yêu cầu dựa vào hiểu biết của bản thân: Nêu ví dụ một số bài toán tìm kiếm trong thực tế. (Yêu cầu HS phát biểu rõ ràng từng bài toán theo mẫu phát biểu bài toán tìm kiếm cụ thể mà phần khởi động đã đưa ra).

- Trên cơ sở các ví dụ vừa nêu, GV yêu cầu HS đọc mục 1a tr.117 SGK: Trình bày bài toán tìm kiếm theo nghĩa chung nhất.

Nhiệm vụ 2. Tìm kiếm tuần tự bằng hàm của Python

- GV chiếu minh họa kết quả chạy máy với ví dụ và giải thích: Với mảng a = [1, 2, 3, 4, 5, 6] như hình bên, câu lệnh print(a.index(3, 1, 4)) sẽ in ra màn hình kết quả là 2, cho biết vị trí của phần tử 3 trong đoạn [1, 4] ở mảng a.

- Từ ví dụ vừa nêu, GV yêu cầu HS đọc hiểu thông tin mục 1b tr.117 - 118 và trả lời: Trình bày phương thức tìm kiếm tuần tự hằng hàm của Python.

Bước 2: HS thực hiện nhiệm vụ học tập

- HS đọc và tìm hiểu thông tin mục 1 SGK trang 117, thực hiện nhiệm vụ được giao.

- GV hướng dẫn, theo dõi, hỗ trợ HS khi cần.

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- HS giơ tay trả lờ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ận xét câu trả lời của HS.

- GV kết luận và yêu cầu HS ghi chép đầy đủ vào vở.

1. Bài toán tìm kiếm

a) Khái niệm bài toán tìm kiếm

- Theo nghĩa chung nhất, bài toán tìm kiếm là: Cho một yêu cầu tìm kiếm và một tập hợp dữ liệu là phạm vi tìm kiếm. Hãy tìm mục (các mục) dữ liệu đáp ứng yêu cầu tìm kiếm đã cho hoặc khẳng định không có mục dữ liệu nào đáp ứng yêu cầu đó.

Ví dụ:

+ Cho mã cuốn sách, hãy tìm cuốn sách trong kho sách của thư viện.

+ Tìm một tên người trong danh sách khám bệnh…

b) Tìm kiếm tuần tự bằng hàm của Python

- Phương thức index thực hiện tìm kiếm theo cách tuần tự cho dãy xâu kí tự, mảng hoặc danh sách.

- Các trường hợp trả về khi dùng index

+ Nếu xuất hiện nhiều lần thì đưa ra chỉ số của lần xuất hiện đầu tiên.

Ví dụ:

a = [1, 3, 3, 4, 3, 5, 6]

print(a.index(3))

+ Báo lỗi “valueError” nếu không tìm thấy.

Ví dụ:

a = [1, 2, 3, 4, 5, 6]

print(a.index(5, 1, 4))

+ Phương thức index có hai tham số tùy chọn: lo, hi để hạn chế thực hiện tìm kiếm chỉ trong đoạn con của dãy số, bắt đầu từ chỉ số lo (lowest) và kết thúc ở hi (highest).

Cú pháp:

dãy_số.index(giá_trị, lo, hi)

HOẠT ĐỘNG CỦA GV - HS

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 đọc hiểu thông tin mục 2 tr.118, quan sát Hình 1 và Hình 2, thảo luận cặp đôi trả lời câu hỏi: Vận dụng kiến thức đã học ở bài trước, hãy xác định độ phức tạp thời gian của thuật toán trong để tìm kiếm tuần tự một số x.

Bước 2: HS thực hiện nhiệm vụ học tập

- HS đọc hiểu thông tin mục 2 SGK trang 118 và thực hiện nhiệm vụ.

- GV theo dõi, hỗ trợ HS trong quá trình học tập.

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- HS giơ tay trả lời câu hỏi: Độ phức tạp thời gian của thuật toán tìm kiếm tuần tự là O(n).

- Các HS còn lại nhận xét, bổ sung (nếu có).

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

- GV nhận xét kết quả trả lời của HS.

- GV tổng quát kiến thức và yêu cầu HS ghi chép đầy đủ vào vở.

2. Thuật toán tìm kiếm tuần tự

- Thực hiện tìm kiếm tuần tự bằng phép lặp duyệt từ đầu dãy số với điều kiện dừng khi “tìm thấy” hoặc “đã xét hết dãy số”.

Chi tiết dần từng bước thuật toán tìm kiếm tuần tự

Từ mô tả liệt kê các bước của thuật toán tìm kiếm tuần tự chuyển thành mã giả

HOẠT ĐỘNG CỦA GV - HS

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 đọc hiểu thông tin mục 3 tr.119 - 120, quan sát Hình 3, 4 trả lời câu hỏi Hoạt động: Dựa trên mô tả thuật toán tìm kiếm nhị phân cho ở Hình 3, em hãy nêu tóm tắt ý tưởng của thuật toán này.

Bước 2: HS thực hiện nhiệm vụ học tập

- HS đọc và tìm hiểu nhiệm vụ mục 3 SGK trang 119 - 120, thực hiện các nhiệm vụ được giao.

- GV hướng dẫn, theo dõi, hỗ trợ HS khi cần.

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- GV mời đại diện một số nhóm trình bày kết quả thảo luận: Ý tưởng của thuật toán tìm kiếm nhị phân:

+ So sánh x với phần tử chính giữa mảng A (nếu x là phần tử giữa thì dừng)

+ Nếu không: xác định xem x có thể thuộc nửa trái hay nửa phải của A.

+ Lặp lại 2 bước trên với nửa đã được xác định.

- GV mời HS nhóm 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ận xét kết quả thảo luận của HS, thái độ làm việc của HS trong nhóm.

- GV kết luận và yêu cầu HS ghi chép đầy đủ vào vở.

3. Thuật toán tìm kiếm nhị phân

- Nếu dãy số đã sắp xếp theo thứ tự thì có thể áp dụng thuật toán tìm kiếm nhị phân.

- Phép lặp lại thực hiện tìm kiếm nhị phân chia đôi dãy số tại điểm “giữa” có chỉ số (lo + hi)//2, bỏ bớt nửa dãy cho đến khi “tìm thấy” hoặc hết dãy.