Giáo án chuyên đề Khoa học máy tính 11 cánh diều CĐ 2 Bài 4: Kĩ thuật chia để trị trong thuật toán sắp xếp trộn (P2)

Hoạt động 3: Tìm hiểu mô hình tổng quát của phương pháp chia để trị

1. a) Mục tiêu: Nêu được mô hình giải bài toán của thuật toán chia để trị.
2. b) Nội dung: HS thảo luận, đọc sách CĐHT trang 43-45 để tìm hiểu mô hình tổng quát của phương pháp chia để trị.
3. c) Sản phẩm: Nêu được các bước của phương pháp chia để trị và ưu điểm, hạn chế của kĩ thuật này.
4. d) Tổ chức thực hiện:

1. HOẠT ĐỘNG LUYỆN TẬP
2. a) Mục tiêu: HS củng cố lại kiến thức về kĩ thuật chia để trị trong thuật toán sắp xếp trộn.
3. b) Nội dung: HS hoạt động cá nhân trả lời câu hỏi liên quan đến kĩ thuật chia để trị trong thuật toán sắp xếp trộn.
4. c) Sản phẩm: Hướng dẫn trả lời câu hỏi liên quan đến kĩ thuật chia để trị trong thuật toán sắp xếp trộn.
5. d) Tổ chức thực hiện

Bước 1: Chuyển giao nhiệm vụ

- GV cho HS trả lời nhanh các câu hỏi trắc nghiệm về các nội dung liên quan đến kĩ thuật chia để trị trong thuật toán sắp xếp trộn.

Câu 1. Sắp xếp trộn là một thuật toán đệ quy điển hình của phương pháp chia để trị tổng quát bao gồm các giai đoạn nào?

1. Chia, Trị, Kết hợp.
2. Chia, Trị, Phân tích.
3. Chia, Trị, Giải bài toán.
4. Chia, Trị, Sắp xếp trộn.

Câu 2. Để trộn hai dãy đã sắp xếp tăng dần thành một dãy sắp xếp tăng dần người ta dùng hàm gì?

1. Reduce().
2. Merge().
3. Split().
4. Enumerate().

Câu 3. Ưu điểm của kĩ thuật chia để trị là gì?

1. Bài toán nào cũng có thể phân chia thành các bài toán con để có thể thực hiện được kĩ thuật chia để trị.
2. Đảm bảo chương trình thực hiện nhanh vì có thể phân chia thành các bài toán con.
3. Đảm bảo tìm ra nghiệm đúng của chương trình.
4. Đảm bảo tìm ra nghiệm đúng và thường cho thời gian thực hiện nhanh.

Câu 4. Ý tưởng chính của thuật toán sắp xếp trộn là gì?

1. Chia đôi dãy cần sắp xếp, đưa bài toán ban đầu về hai bài toán sắp xếp trên dãy có kích thước nhỏ hơn và kết hợp kết quả của hai bài toán thành kết quả của bài toán ban đầu.
2. Chia dãy ban đầu thành bốn phần, đưa bài toán ban đầu về bốn bài toán sắp xếp trên dãy có kích thước nhỏ hơn và kết hợp kết quả của bốn bài toán thành kết quả của bài toán ban đầu.
3. Giữ nguyên bài toán ban đầu và tìm kết quả của bài toán.
4. Chia đôi dãy cần sắp xếp, đưa bài toán ban đầu về hai bài toán sắp xếp trên dãy có kích thước nhỏ hơn và đưa ra kết quả.

Câu 5. Hạn chế của kĩ thuật chia để trị là gì?

1. Chia bài toán thành kích thước nhỏ hơn.
2. Thời gian thực hiện chương trình nhanh.
3. Luôn đảm bảo tìm ra nghiệm đúng.
4. Không phải bài toán nào cũng có thể phân chia thành các bài toán con.

- GV hướng dẫn HS giải nội dung Luyện tập trang 45 sách CĐHT

Em hãy cho biết trong mô tả thuật toán sắp xếp trộn và trong chương trình cài đặt ở trên cần thay đổi thế nào để sắp xếp một dãy theo thứ tự giảm dần của giá trị.

Bước 2: Thực hiện nhiệm vụ:

- HS đọc câu hỏi và trả lời câu hỏi trắc nghiệm khách quan.

Bước 3: Báo cáo, thảo luận:

-  Đại diện HS giơ tay phát biểu.

- Các HS khác nhận xét, góp ý, bổ sung.

Bước 4: Kết luận, nhận định:

-  GV chữa bài, chốt đáp án.

- GV nhận xét thái độ học tập, phương án trả lời của HS, ghi nhận và tuyên dương.

Đáp án

Luyện tập

Sự thay đổi nằm ở bước Kết hợp trong phần mô tả thuật toán và thay đổi hàm Merge(A, T, P) trong phần cài đặt.

1. HOẠT ĐỘNG VẬN DỤNG
2. a) Mục tiêu: Vận dụng kiến thức giải một số bài tập liên quan đến kĩ thuật chia để trị trong thuật toán sắp xếp trộn.
3. b) Nội dung: HS làm việc cá nhân thực hiện giải một số bài tập liên quan đến kĩ thuật chia để trị trong thuật toán sắp xếp trộn.
4. c) Sản phẩm: Gợi ý trả lời bài tập liên quan đến kĩ thuật chia để trị trong thuật toán sắp xếp trộn.
5. d) Tổ chức thực hiện:

Bước 1: Chuyển giao nhiệm vụ:

- GV yêu cầu HS làm việc cá nhân giải bài tập:

+ Câu hỏi Vận dụng trang 45 sách CĐHT.

Hội diễn văn nghệ của trường năm nay, lớp Thanh An tham gia biểu diễn khiêu vũ tập thể theo cặp (nam, nữ). Thầy giáo chủ nhiệm chọn ra n bạn nam có chiều cao A₀, A₁,...A_n-1, đứng thành một hàng ngang và n bạn nữ có chiều cao B₀, B₁,...B_n-1 đứng thành một hàng ngang để ghép thành n cặp (nam, nữ). Để tiện ghép cặp, thầy giáo sắp xếp lại vị trí đứng các bạn nam trong hàng theo thứ tự chiều cao tăng dần và vị trí đứng các bạn nữ trong hàng cũng theo thứ tự chiều cao tăng dần. Sau đó thầy giáo tiến hành ghép cặp bạn nam thấp nhất với bạn nữ thấp nhất, bạn nam thấp thứ hai với bạn nữ thấp thứ hai và cứ như vậy đến bạn nam cao nhất với bạn nữ cao nhất. Em hãy viết chương trình áp dụng thuật toán sắp xếp trộn đề giúp thầy giáo thực hiện công việc ghép cặp này.

Chương trình cần nhập vào một số nguyên n, tiếp theo nhập vào n giá trị A₀, A₁,...A_n-1 và n giá trị B₀, B₁,...B_n-1.

Chương trình cần in ra n cặp số A_i, B_j (0 ≤  i, j ≤  n-1) là cách xếp cặp (nam, nữ) theo mong muốn của thầy giáo ở trên.

+ Câu hỏi Tự kiểm tra trang 34 sách CĐHT.

Trong các câu sau đây, câu nào đúng khi mô tả trình tự các bước cơ bản của phương pháp chia để trị?

1. a) Chia nhỏ bài toán; Kết hợp kết quả các bài toán con; Giải từng bài toán con bằng đệ quy.
2. b) Giải bài toán; Chia nhỏ bài toán; Kết hợp các kết quả bài toán.
3. c) Chia nhỏ bài toán; Giải từng bài toán con bằng đệ quy; Kết hợp kết quả các bài toán con.

Bước 2: Thực hiện nhiệm vụ:

- HS suy nghĩ và giải bài tập liên quan đến kĩ thuật đệ quy trong chia để trị.

Bước 3: Báo cáo, thảo luận:

- HS xung phong trình bày bài làm của mình.

- HS khác nhận xét và bổ sung.

Bước 4: Kết luận, nhận định:

- GV chữa bài, chốt đáp án.

- GV nhận xét thái độ làm việc, sản phẩm, phương án trả lời của các học sinh, ghi nhận và tuyên dương.

Gợi ý trả lời:

Vận dụng

Chương trình mẫu như sau:

Câu hỏi tự kiểm tra

Đáp án a)

*HƯỚNG DẪN VỀ NHÀ

- Ghi nhớ kiến thức trong bài.

- Hoàn thành nội dung câu hỏi Vận dụng và Tự kiểm tra.

- Chuẩn bị Bài 5. Thực hành tổng hợp ứng dụng chia để trị.