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 (P1)

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

SẢN PHẨM DỰ KIẾN

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

- GV yêu cầu HS đọc nội dung trang 38 sách CĐHT và trả lời câu hỏi sau:

Thầy giáo lớp Thanh An mời 5 bạn học sinh lên bảng, xếp ngẫu nhiên thành một hàng ngang, từ trái sang phải là các bạn có tên Thi, An, Hòa, Lâm, Mai. Em hãy giúp thầy giáo yêu cầu 5 bạn thực hiện lần lượt các bước trong hai giai đoạn sau để sắp xếp thành hàng tăng dần theo chiều cao từ trái sang phải.

- GV mời 5 bạn có chiều cao tương đối khác nhau lên bảng và thực hiện các bước hoạt động như mô tả trong sách CĐHT.

+ Giai đoạn 1: Ở giai đoạn này, với mỗi lượt, mỗi dãy được chia làm hai dãy nhỏ với mục tiêu sắp xếp tăng dần trên từng dãy nhỏ. Quá trình kết thúc khi mỗi dãy có đúng một bạn.

+ Giai đoạn 2: Ở giai đoạn này, với mỗi lượt, cứ hai dãy liên tiếp được tách ra từ Giai đoạn 1 theo trình tự lượt ngược lại 3, 2, 1 sẽ được kết hợp lại thành một dãy. Sau mỗi lượt, các bạn trong từng dãy nhỏ có chiều cao tăng dần.

- GV hướng dẫn HS phân tích và rút ra các đặc trưng của 3 bước cơ bản trong kĩ thuật chia để trị: Chia, Trị, Kết hợp.

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

- HS tìm hiểu thông tin sách CĐHT, thực hiện nhiệm vụ và thảo luận trả lời câu hỏi.

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

- Đại diện nhóm HS báo cáo.

- Một số HS nhóm khác nhận xét, bổ sung cho bạn.

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

- GV nhận xét kết quả thảo luận nhóm, thái độ làm việc của các HS.

- GV tổng quát lại kiến thức trọng tâm và yêu cầu HS ghi chép đầy đủ vào vở.

1. Ý tưởng thuật toán sắp xếp trộn

- Thầy giáo lớp Thanh An chia dần 5 bạn thành các dãy nhỏ giúp việc sắp xếp vị trí các bạn tăng dần theo chiều cao trở nên thuận lợi và dễ dàng. Cách làm trên của thầy giáo thể hiện ba bước cơ bản của kĩ thuật chia để trị cho hoạt động trên như sau:

1. Chia: Chia một dãy thành 2 dãy nhỏ.

2. Trị: Sắp xếp mỗi dãy nhỏ theo cách giống như sắp xếp ban đầu. Quá trình này kết thúc khi mỗi dãy nhỏ chỉ còn một bạn.

3. Kết hợp: Cứ hai dãy liên tiếp đã được sắp xếp kết hợp lại thành một dãy các bạn được sắp xếp theo chiều cao tăng dần. Bước này được làm lần lượt từ các dãy kích thước nhỏ đến lớn.

*Kết luận

- 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 ba giai đoạn cơ bản: Chia, Trị và Kết hợp.

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

SẢN PHẨM DỰ KIẾN

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

- GV yêu cầu HS đọc nội dung trang 40,41 và giới thiệu bài toán:

Cho dãy số A gồm n phần tử A₀, A₁,…,A­_n-1. Em hãy viết chương trình nhập vào số nguyên n và dãy số nguyên A có n phần tử A₀, A₁,…,A_n-1; sau đó sắp xếp dãy này theo thứ tự tăng dần dùng thuật toán sắp xếp trộn.

- GV hướng dẫn các bước giải toán một cách trực quan trên ví dụ.

- GV giới thiệu một ví dụ sắp xếp dãy số: 5, 4, 9, 8, 7, 1 dùng thuật toán trên.

- GV hướng dẫn HS thực hiện nội dung Thực hành trang 41 sách CĐHT.

Em hãy tìm hiểu các đoạn chương trình viết trên ngôn ngữ lập trình Python cho thuật toán sắp xếp trộn sau đây: Em hãy soạn thảo và chạy chương trình với các bộ dữ liệu thử nghiệm trong Bảng 1.

- GV hướng dẫn HS cài đặt lại thuật toán từ chương trình mẫu và chạy thông với các bộ dữ liệu vào khác nhau.

- Sau khi HS chạy chương trình mẫu, GV yêu cầu HS nêu các bước khi thực hiện thuật toán sắp xếp trộn.

- GV kết luận về các bước chính thực hiện thuật toán sắp xếp trộn.

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

- HS tìm hiểu thông tin sách CĐHT, thực hiện nhiệm vụ và thảo luận trả lời câu hỏi.

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

- Đại diện nhóm HS báo cáo.

- Một số HS nhóm khác nhận xét, bổ sung cho bạn.

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

- GV nhận xét kết quả thảo luận nhóm, thái độ làm việc của các HS.

- GV tổng quát lại kiến thức trọng tâm và yêu cầu HS ghi chép đầy đủ vào vở.

2. Thuật toán sắp xếp trộn

- Các bước của thuật toán sắp xếp trộn được thiết kế theo kĩ thuật đệ quy cho hàm sắp xếp trộn Merge_sort (A) như sau:

1. Chia: Chia dãy A thành hai dãy con (A₀, A₁,…,A_k) và (A_k, A_k+1,…,A_n-1) có số lượng phần tử chênh nhau không quá 1.

2. Trị: Sắp xếp mỗi dãy con bằng cách sử dụng lời gọi đệ quy Merge_sort () với đầu vào mới tương ứng cho dãy con cần sắp xếp. Hàm đệ quy dừng khi độ dài dãy cần sắp xếp bằng 1.

3. Kết hợp: Trộn hai dãy con đã được  sắp xếp lại thành một dãy duy nhất được sắp xếp tăng dần. Thuật toán kết hợp duy trì ba biến chạy, hai biến chạy cho dãy hai con, một biến chạy cho dãy được sắp xếp cuối cùng, tăng các biến chạy tương ứng với các vị trí trong dãy lần lượt từ trái qua phải, lấy ra phần tử nhỏ hơn trong hai giá trị tại vị trí hai biến chạy của hai dãy con và gán vào vị trí biến chạy của dãy sắp xếp cuối cùng.

*Kết luận

- Sắp xếp trộn là thuật toán đệ quy điển hình cho mô hình tổng quát của phương pháp chia để trị bao gồm ba bước chính là: chia nhỏ ra thành hai bài toán con; 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.