Ngagrave;y soạn:hellip;/hellip;/hellip;

Ngagrave;y dạy:hellip;/hellip;/hellip;

BAgrave;I 10. THỰC HAgrave;NH GIẢI TOAacute;N BẰNG KĨ THUẬT CHIA ĐỂ TRỊ

1. MỤC TIEcirc;U
2. Về kiến thức

Sau bagrave;i học nagrave;y, HS sẽ:

• Biết caacute;ch thiết kế vagrave; viết chương trigrave;nh giải một số bagrave;i toaacute;n theo kĩ thuật chia để trị.
• Thực hagrave;nh viết chương trigrave;nh giải một số bagrave;i toaacute;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 caacute;c nguồn tagrave;i liệu học tập phugrave; hợp.
• Năng lực giải quyết vấn đề vagrave; saacute;ng tạo: Xaacute;c định vagrave; tigrave;m hiểu được caacute;c thocirc;ng tin liecirc;n quan đến vấn đề, đề xuất giải phaacute;p giải quyết vấn đề trong bagrave;i học.
• Năng lực giao tiếp vagrave; hợp taacute;c: Thực hiện tốt nhiệm vụ trong hoạt động nhoacute;m.

Năng lực tin học:

• Higrave;nh thagrave;nh, phaacute;t triển năng lực giải quyết vấn đề với sự hỗ trợ của cocirc;ng nghệ thocirc;ng tin vagrave; truyền thocirc;ng.

3. Phẩm chất:

• Higrave;nh thagrave;nh yacute; thức traacute;ch nhiệm, tiacute;nh cẩn thận khi lagrave;m việc nhoacute;m, phẩm chất lagrave;m việc chăm chỉ, chuyecirc;n cần để hoagrave;n thagrave;nh một nhiệm vụ.
• Coacute; yacute; thức vận dụng kiến thức, kĩ năng đatilde; học ở nhagrave; trường vagrave;o thực tiễn.

1. THIẾT BỊ DẠY HỌC VAgrave; HỌC LIỆU
2. Đối với giaacute;o viecirc;n

• SGK, SGV, Giaacute;o aacute;n;
• Maacute;y tiacute;nh đatilde; cagrave;i đặt Python vagrave; maacute;y chiếu;
• Higrave;nh ảnh, sơ đồ minh họa cho caacute;c bước thực hiện trecirc;n một mẫu dữ liệu đơn giản hoặc coacute; thể sử dụng caacute;c phần mềm mocirc; phỏng thuật toaacute;n để minh họa.

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

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

III. TIẾN TRIgrave;NH DẠY HỌC

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

- Đặt vấn đề nhận biết một datilde;y đatilde; sắp xếp tăng dần hay giảm dần hay chưa sẽ dẫn đến bagrave;i toaacute;n tigrave;m cặp nghịch đảo.

1. Nội dung: GV cho caacute;c nhoacute;m HS trao đổi nội dung Mở đầu.
2. Sản phẩm học tập: HS dựa vagrave;o kiến thức vagrave; hiểu biết caacute; nhacirc;n để đưa ra cacirc;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 lagrave;m việc với danh saacute;ch/mảng, nhiều trường hợp đograve;i hỏi cần kiểm tra caacute;c danh saacute;ch mảng đatilde; được sắp thứ tự để aacute;p dụng thuật toaacute;n phugrave; hợp.

- GV đặt cacirc;u hỏi yecirc;u cầu HS thảo luận: Cho một datilde;y số, theo em lagrave;m thế nagrave;o để xaacute;c định datilde;y số đatilde; đượ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ĩ vagrave; đưa ra cacirc;u trả lời.

Bước 3: Baacute;o caacute;o kết quả hoạt động vagrave; thảo luận

- GV hướng dẫn HS trả lời cacirc;u hỏi.

Gợi yacute;:

Datilde;y số đatilde; được sắp xếp tăng dần nếu khocirc;ng coacute; cặp nghịch đảo nagrave;o, ngược lại datilde;y số sẽ sắp xếp giảm dần nếu noacute; coacute; n(n-1)/2 cặp nghịch đảo. Do vậy bagrave;i toaacute;n đếm cặp nghịch đảo cũng lagrave; một caacute;ch dugrave;ng để nhận biết một datilde;y số đatilde; sắp xếp tăng dần hoặc giảm dần hay chưa.

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

- GV nhận xeacute;t, đaacute;nh giaacute;, tuyecirc;n dương cacirc;u trả lời của HS.

- GV dẫn dắt vagrave;o nội dung bagrave;i mới: Hocirc;m nay, chuacute;ng ta sẽ vận dụng những kiến thức đatilde; học về giải toaacute;n bằng kĩ thuật chia để trị. - Bagrave;i 10. Thực hagrave;nh giải toaacute;n bằng kĩ thuật chia để trị.

1. HOẠT ĐỘNG HIgrave;NH THAgrave;NH KIẾN THỨC

Hoạt động: Thực hagrave;nh

1. Mục tiecirc;u: HS thiết kế vagrave; viết chương trigrave;nh giải bagrave;i toaacute;n theo kĩ thuật chia để trị.
2. Nội dung: GV yecirc;u cầu HS tigrave;m hiểu nhiệm vụ, tigrave;m hiểu yecirc;u cầu vagrave; caacute;c bước thực hiện.
3. Sản phẩm học tập: Caacute;c chương trigrave;nh magrave; HS viết ra.
4. Tổ chức hoạt động:

1. HOẠT ĐỘNG LUYỆN TẬP
2. Mục tiecirc;u: HS vận dụng kiến thức, hoagrave;n thagrave;nh bagrave;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 hagrave;nh giải toaacute;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 yecirc;u cầu HS thảo luận nhoacute;m đocirc;i, hoagrave;n thagrave;nh bagrave;i tập:

Nacirc;ng cấp chương trigrave;nh của nhiệm vụ 1 với yecirc;u cầu bổ sung: Cần đưa ra kết quả lagrave; số lượng caacute;c cặp nghịch đảo vagrave; toagrave;n bộ datilde;y caacute;c cặp chỉ số nghịch đảo đatilde; tigrave;m thấy. Viacute; dụ với A = [4, 5, 2, 10, 4] thigrave; chương trigrave;nh sẽ đưa ra giaacute; trị 4 vagrave; datilde;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 trigrave;nh giải bagrave;i toaacute;n.

- GV hướng dẫn, theo dotilde;i, hỗ trợ HS nếu cần thiết.

Bước 3: Baacute;o caacute;o kết quả hoạt động vagrave; thảo luận

- GV đại diện của 1 nhoacute;m lecirc;n bảng thực hiện trecirc;n maacute;y vagrave; chạy thử chương trigrave;nh.

- HS khaacute;c quan saacute;t, nhận xeacute;t, sửa bagrave;i (nếu coacute;).

Kết quả:

Hagrave;m merge(A,left,mid,right) sẽ trả về datilde;y caacute;c cặp nghịch đảo khi tiến hagrave;nh "trộn" tại chỗ hai phần của cugrave;ng datilde;y A. Phần thay đổi chương trigrave;nh nằm ở dograve;ng lệnh 13.

Hagrave;m chiacute;nh getInvCount(A,left,right) sẽ trả về kết quả lagrave; datilde;y caacute;c phần tử nghịch đảo của datilde;y A trong đoạn chỉ số [left, right].

Đoạn chương trigrave;nh chiacute;nh coacute; thể như sau:

Chuacute; yacute;: Với yecirc;u cầu mới nagrave;y thigrave; hagrave;m merge() sẽ coacute; thời gian chạy lagrave; O(n²), do đoacute; cocirc;ng thức tiacute;nh thời gian của bagrave;i toaacute;n sẽ lagrave;:

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

Từ cocirc;ng thức trecirc;n coacute; thể tiacute;nh được T(n) = O(n²).

Vậy bagrave;i toaacute;n tigrave;m tất cả caacute;c cặp phần tử nghịch đảo lagrave;m theo kĩ thuật chia để trị khocirc;ng coacute; thời gian tốt hơn lagrave; caacute;ch lagrave;m thocirc;ng thường.

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

- GV nhận xeacute;t, tuyecirc;n dương.

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

--------------- Cograve;n tiếp ---------------