Giáo án chuyên đề Khoa học máy tính 11 kết nối Bài 10: Thực hành giải toán bằng kĩ thuật chia để trị

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

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

BÀI 10. THỰC HÀNH GIẢI TOÁN BẰNG 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 hoặc có thể sử dụng các phần mềm mô phỏng thuật toán để minh họa.

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:

- Đặt vấn đề nhận biết một dãy đã sắp xếp tăng dần hay giảm dần hay chưa sẽ dẫn đến bài toán tìm cặp nghịch đảo.

1. Nội dung: GV cho các nhóm HS trao đổi nội dung 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 vấn đề: Khi làm việc với danh sách/mảng, nhiều trường hợp đòi hỏi cần kiểm tra các danh sách mảng đã được sắp thứ tự để áp dụng thuật toán phù hợp.

- GV đặt câu hỏi yêu cầu HS thảo luận: Cho một dãy số, theo em làm thế nào để xác định dãy số đã được sắp xếp theo thứ tự tăng dần hoặc giảm dần?

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 hướng dẫn HS trả lời câu hỏi.

Gợi ý:

Dãy số đã được sắp xếp tăng dần nếu không có cặp nghịch đảo nào, ngược lại dãy số sẽ sắp xếp giảm dần nếu nó có n(n-1)/2 cặp nghịch đảo. Do vậy bài toán đếm cặp nghịch đảo cũng là một cách dùng để nhận biết một dãy số đã sắp xếp tăng dần hoặc giảm dần hay chưa.

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ề giải toán bằng kĩ thuật chia để trị. - Bài 10. Thực hành giải toán bằng 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: HS thiết kế và viết chương trình giải bài toán 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 thực hành giải toán bằng kĩ thuật chia để trị.
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 bài tập:

Nâng cấp chương trình của nhiệm vụ 1 với yêu cầu bổ sung: Cần đưa ra kết quả là số lượng các cặp nghịch đảo và toàn bộ dãy các cặp chỉ số nghịch đảo đã tìm thấy. Ví dụ với A = [4, 5, 2, 10, 4] thì chương trình sẽ đưa ra giá trị 4 và dãy [(4, 2), (5, 2), (5, 4), (1, 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ả:

Hàm merge(A,left,mid,right) sẽ trả về dãy các cặp nghịch đảo khi tiến hành "trộn" tại chỗ hai phần của cùng dãy A. Phần thay đổi chương trình nằm ở dòng lệnh 13.

Hàm chính getInvCount(A,left,right) sẽ trả về kết quả là dãy các phần tử nghịch đảo của dãy A trong đoạn chỉ số [left, right].

Đoạn chương trình chính có thể như sau:

Chú ý: Với yêu cầu mới này thì hàm merge() sẽ có thời gian chạy là O(n²), do đó công thức tính thời gian của bài toán sẽ là:

T(n) = 2T(n/2) + O(n²)

Từ công thức trên có thể tính được T(n) = O(n²).

Vậy bài toán tìm tất cả các cặp phần tử nghịch đảo làm theo kĩ thuật chia để trị không có thời gian tốt hơn là cách làm thông thường.

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 47.
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:

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