Giáo án Chuyên đề Tin học 11 Kết nối tri thức Bài 10: Thực hành giải toán bằng kĩ thuật chia để trị

Giáo án Chuyên đề Tin học 11 Kết nối tri thức Bài 10: Thực hành giải toán bằng kĩ thuật chia để trị

Xem thử

Chỉ từ 200k mua trọn bộ Kế hoạch bài dạy (KHBD) hay Giáo án Chuyên đề Tin học 11 Kết nối tri thức chuẩn kiến thức, trình bày đẹp mắt, dễ dàng chỉnh sửa:

• B1: gửi phí vào tk: 1133836868 - CT TNHH DAU TU VA DV GD VIETJACK - Ngân hàng MB (QR)
• B2: Nhắn tin tới Zalo VietJack Official - nhấn vào đây để thông báo và nhận giáo án

I. MỤC TIÊU

1. 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.

II. THIẾT BỊ DẠY HỌC VÀ HỌC LIỆU

1. Đố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

A. HOẠT ĐỘNG KHỞI ĐỘNG

a. 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.

b. Nội dung: GV cho các nhóm HS trao đổi nội dung Mở đầu.

c. 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.

d. 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ị.

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

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

a. 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ị.

b. 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.

c. Sản phẩm học tập: Các chương trình mà HS viết ra.

d. Tổ chức hoạt động:

HOẠT ĐỘNG CỦA GV VÀ HS

DỰ KIẾN SẢN PHẨM

Bước 1: GV chuyển giao nhiệm vụ học tập - GV giới thiệu bài toán: Đếm số cặp nghịch đảo (inversion) của dãy số. Cho một dãy số A bất kì. Hãy đếm số cặp nghịch đảo của dãy số đó. Một cặp phần tử A[i] và A[j] được gọi là nghịch đảo nếu i < j và A[i] > A[j]. Ví dụ dãy A = [4, 5, 2, 10, 4] sẽ có 4 cặp nghịch đảo là: (4,2), (5,2), (5,4), (10,4). - GV nhắc lại, đây là bài toán HS đã được học ở Bài 26 của SGK Tin học 11 – Định hướng Khoa học máy tính. - GV nhắc lại lời giải bài toán đã được học và cùng HS thực hiện lời giải. - GV phân tích lời giải đã biết thì thời gian chạy của chương trình là O(n2). - GV giới thiệu cách thiết kế mới của bài toán theo kĩ thuật chia để trị và ý tưởng lời giải theo cách làm của thuật toán sắp xếp trộn đã học ở Bài 9. - GV yêu cầu HS thảo luận để hiểu được ý tưởng và cách làm của bài toán và tiến hành cài đặt chương trình. - GV kết luận về ưu điểm của thuật toán này chỉ chạy với thời gian O(nlogn), nhanh hơn so với cách làm đã biết. Bước 2: HS thực hiện nhiệm vụ học tập - HS chia nhóm, thảo luận thực hiện theo các bước SGK. - 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ả Nhiệm vụ. - HS xung phong thực hiện các nhiệm vụ và giải thích.

Thực hành Nhiệm vụ Cách 1. Phương pháp duyệt đơn giản Ý tưởng: - Duyệt lần lượt từng phần tử của dãy số. - Với mỗi phần tử đang xét A[i], thực hiện so sánh với tất cả các phần tử đứng sau nó A[j], nếu A[i] > A[j] ta sẽ tăng số cặp nghịch đảo lên 1 đơn vị. Chương trình 1 Thuật toán trên sử dụng hai vòng for lồng nhau tại dòng 4 và 5, do đó thời gian chạy là O(n2). Cách 2. Sử dụng phương pháp chia để trị dựa trên thuật toán sắp xếp trộn mergeSort Ý tưởng: Thực hiện thuật toán sắp xếp trộn trên dãy đã cho, trong quá trình trộn sẽ đồng thời tiến hành đếm số các cặp phần tử nghịch đảo. Các bước chính thực hiện giải bài toán này như sau: - Chia dãy thành hai phần bằng nhau cho đến khi mỗi dãy chỉ còn 1 phần tử. - Khi tiến hành hàm trộn hai dãy sẽ đồng thời đếm số các cặp nghịch đảo của hai dãy này. Kết quả vẫn tạo được dãy trộn như đã mô tả trong thuật toán sắp xếp trộn, vừa đếm được số nghịch đảo. - Gọi đệ quy đếm số cặp nghịch đảo cho hai nửa bên trái và bên phải, tính tổng số nghịch đảo khi trộn hai dãy. Kết quả sẽ thu được tổng số cặp nghịch đảo cần tìm. Chương trình chính như sau:

................................

................................

................................

Trên đây tóm tắt một số nội dung miễn phí trong bộ Kế hoạch bài dạy (KHBD) hay Giáo án Chuyên đề Tin học 11 mới nhất, để mua tài liệu đầy đủ, Thầy/Cô vui lòng xem thử:

Xem thử

Xem thêm các bài soạn Giáo án Chuyên đề Tin học lớp 11 Kết nối tri thức hay, chuẩn khác:

• Giáo án Chuyên đề Tin học 11 Bài 11: Bài toán tìm kiếm theo kĩ thuật duyệt

• Giáo án Chuyên đề Tin học 11 Bài 12: Thực hành kĩ thuật duyệt cho bài toán tìm kiếm

• Giáo án Chuyên đề Tin học 11 Bài 13: Kĩ thuật duyệt quay lui

• Giáo án Chuyên đề Tin học 11 Bài 14: Thực hành kĩ thuật duyệt quay lui

• Giáo án Chuyên đề Tin học 11 Bài 15: Bài toán xếp hậu

---