Giáo án chuyên đề Khoa học máy tính 11 kết nối Bài 8: Thực hành thiết kế thuật toán tìm kiếm theo kĩ thuật chia để trị

Ngày soạn:…/…/…

Ngày dạy:…/…/…

BÀI 8. THỰC HÀNH THIẾT KẾ THUẬT TOÁN TÌM KIẾM THEO KĨ THUẬT CHIA ĐỂ TRỊ

1. MỤC TIÊU
2. Về kiến thức

Sau bài học này, HS sẽ:

• Biết cách thiết kế và viết chương trình giải một số bài toán theo kĩ thuật chia để trị.
• Thực hành viết chương trình giải một số bài toán theo kĩ thuật chia để trị.

2. Năng lực

Năng lực chung:

• Năng lực tự chủ: Biết lựa chọn các nguồn tài liệu học tập phù hợp.
• Năng lực giải quyết vấn đề và sáng tạo: Xác định và tìm hiểu được các thông tin liên quan đến vấn đề, đề xuất giải pháp giải quyết vấn đề trong bài học.
• Năng lực giao tiếp và hợp tác: Thực hiện tốt nhiệm vụ trong hoạt động nhóm.

Năng lực tin học:

• Hình thành, phát triển năng lực giải quyết vấn đề với sự hỗ trợ của công nghệ thông tin và truyền thông.

3. Phẩm chất:

• Hình thành ý thức trách nhiệm, tính cẩn thận khi làm việc nhóm, phẩm chất làm việc chăm chỉ, chuyên cần để hoàn thành một nhiệm vụ.
• Có ý thức vận dụng kiến thức, kĩ năng đã học ở nhà trường vào thực tiễn.

1. THIẾT BỊ DẠY HỌC VÀ HỌC LIỆU
2. Đối với giáo viên

• SGK, SGV, Giáo án;
• Máy tính đã cài đặt Python và máy chiếu;
• Hình ảnh, sơ đồ minh họa cho các bước thực hiện trên một mẫu dữ liệu đơn giản.
• Sử dụng phần mềm mô phỏng thuật toán để minh họa thêm trong quá trình giảng dạy.

2. Đối với học sinh

• SGK, vở ghi.
• Điện thoại có cài sẵn phần mềm Python (nếu có).

III. TIẾN TRÌNH DẠY HỌC

1. HOẠT ĐỘNG KHỞI ĐỘNG
2. Mục tiêu:

- HS làm quen với các bài toán sẽ được học thiết kế trong bài.

- Kích thích sự tò mò cho người học.

1. Nội dung: GV cho các nhóm HS trao đổi câu hỏi Mở đầu.
2. Sản phẩm học tập: HS dựa vào kiến thức và hiểu biết cá nhân để đưa ra câu trả lời.
3. Tổ chức thực hiện:

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

- GV đặt câu hỏi yêu cầu HS thảo luận: Cho một dãy số A bất kì. Để xác định một số C cho trước xuất hiện trong dãy A bao nhiêu lần thì làm thế nào?

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

- HS lắng nghe, suy nghĩ và đưa ra câu trả lời.

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

- GV mời HS trả lời câu hỏi.

- Các HS khác nhận xét, nêu ý kiến khác (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, đánh giá, tuyên dương câu trả lời của HS.

- GV dẫn dắt vào nội dung bài mới: Hôm nay, chúng ta sẽ vận dụng những kiến thức đã học về thiết kế thuật toán tìm kiếm theo kĩ thuật chia để trị. - Bài 8: Thực hành thiết kế thuật toán tìm kiếm theo kĩ thuật chia để trị.

1. HOẠT ĐỘNG HÌNH THÀNH KIẾN THỨC

Hoạt động: Thực hành

1. Mục tiêu: Viết được chương trình thiết kế thuật toán tìm kiếm theo kĩ thuật chia để trị.
2. Nội dung: GV yêu cầu HS tìm hiểu nhiệm vụ, tìm hiểu yêu cầu và các bước thực hiện.
3. Sản phẩm học tập: Các chương trình mà HS viết ra.
4. Tổ chức hoạt động:

1. HOẠT ĐỘNG LUYỆN TẬP
2. Mục tiêu: HS vận dụng kiến thức, hoàn thành bài tập phần Luyện tập.
3. Nội dung: GV giao nhiệm vụ, HS thảo luận.
4. Sản phẩm học tập: HS thiết kế thuật toán tìm kiếm theo kĩ thuật chia để trị để giải các bài toán.
5. Tổ chức thực hiện:

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

- GV yêu cầu HS thảo luận nhóm đôi, hoàn thành các bài tập:

Chỉnh sửa nâng cấp chương trình của nhiệm vụ thực hành để đưa ra kết quả là vùng các phần tử có giá trị bằng C của dãy gốc, tức là yêu cầu đưa ra chỉ số đầu, chỉ số cuối và số lượng phần tử của vùng có giá trị bằng C.

Ví dụ nếu A = [0, 1, 2, 2, 2, 2, 4, 5, 5, 6], C = 2, thì kết quả trả lại là 2, 5, 4.

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

- HS thảo luận, viết chương trình giải bài toán.

- 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 đại diện của 1 nhóm lên bảng thực hiện trên máy và chạy thử chương trình.

- HS khác quan sát, nhận xét, sửa bài (nếu có).

Kết quả:

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

- GV nhận xét, tuyên dương.

1. HOẠT ĐỘNG VẬN DỤNG
2. Mục tiêu: HS vận dụng kiến thức, liên hệ với thực tế để giải quyết vấn đề.
3. Nội dung: GV tổ chức cho HS làm bài tập phần Vận dụng SGK trang 39.
4. Sản phẩm học tập: HS viết và chạy thử chương trình.
5. Tổ chức thực hiện:

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

- GV nêu yêu cầu bài toán:

Bài 1. Cho một dãy số bất kì (chưa được sắp xếp) và một số K, hãy tìm số lần xuất hiện của K trong dãy số trên. Yêu cầu sử dụng phương pháp chia để trị.

Bài 2. Cho một dãy số nguyên được sắp xếp theo thứ tự tăng dần. Hãy thiết kế hàm tìm trong dãy phần tử thứ i có giá trị bằng I (A[i] = i). Phần tử A[i] như vậy được gọi là phần tử cố định.

Bài 3. Cho trước dãy số A đã sắp xếp theo thứ tự tăng dần, cho trước hằng số C. Cần thiết lập hai hàm sau bằng kĩ thuật chia để trị:

– Hàm firstInd(A, left, right, C) sẽ tìm chỉ số của phần tử đầu tiên của dãy A có giá trị bằng C. Nếu không sẽ trả về -1.

– Hàm lastInd(A, left, right, C) sẽ tìm chỉ số của phần tử cuối cùng của dãy A có giá trị bằng C. Nếu không thấy sẽ trả về – 1.

Từ hai hàm đã thiết kế trên, đưa ra một cách giải khác cho bài toán trong nhiệm vụ 1. Lời giải này có độ phức tạp O(logn).

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

- HS thảo luận, viết chương trình giải bài toán.

- 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 đại diện của 1 nhóm lên bảng thực hiện trên máy và chạy thử chương trình.

- HS khác quan sát, nhận xét, sửa bài (nếu có).

Kết quả:

Bài 1. Hàm đệ quy được xây dựng như sau:

--------------- Còn tiếp ---------------