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

XIN MỜI CÁC EM

ĐẾN VỚI BÀI HỌC NGÀY HÔM NAY!

KHỞI ĐỘNG

Bài 2 giới thiệu kĩ thuật đệ quy trong phương pháp chia để trị. Nhiều bài được giải quyết dễ dàng bằng cách sử dụng kĩ thuật đệ quy. Ví dụ: Em hãy chia đôi dãy gồm bốn số (7, 3, 8, 2) làm hai nửa để thực hiện công việc sắp xếp bốn số này theo thứ tự tăng dần của giá trị.

7 3 8 2 -> 3 7 2 8 -> 2 3 7 8

Gợi ý

BÀI 4.

KĨ THUẬT CHIA ĐỂ TRỊ TRONG THUẬT TOÁN SẮP XẾP TRỘN

NỘI DUNG BÀI HỌC

1

Ý tưởng thuật toán

2

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

3

Mô hình tổng quát của phương pháp chia để trị

PHẦN 1. Ý TƯỞNG THUẬT TOÁN

Hoạt động 1

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.

Thực hiện các bước hoạt động

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.

Thực hiện các bước hoạt động

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.

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.

Thể hiện ba bước cơ bản của kĩ thuật chia để trị

Bước chia

Giai đoạn 1: Chia một dãy thành 2 dãy nhỏ.

Bước trị

Giai đoạn 2: 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.

Kết hợp

Giai đoạn 3: 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.

PHẦN 2. THUẬT TOÁN SẮP XẾP TRỘN

Bài toán: Cho dãy số A gồm n phần tử A0, A1,…,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ử A0, A1,…,An-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.

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 (A0, A1,…,Ak) và (Ak, Ak+1,…,An-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.

Hình 3. Một ví dụ hoạt động của thuật toán sắp xếp trộn

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.

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.

THỰC HÀNH

Bảng 1. Một số bộ dữ liệu thử nghiệm cho thuật toán sắp xếp trộn

Hình 4. Chương trình sắp xếp trộn mảng A với hàm đệ quy Merge_sort()

Hình 5. Hàm Merge(A,T,P) trộn hai dãy T và P vào dãy A

PHẦN 3. MÔ HÌNH TỔNG QUÁT CỦA PHƯƠNG PHÁP CHIA ĐỂ TRỊ

KHÁI NIỆM

Chia để trị một mô hình giải toán theo hướng làm dễ bài toán đi bằng cách chia thành các phần nhỏ hơn và xử lí từng phần một.

CÁC BƯỚC CƠ BẢN

1. Chia: Chia bài toán đang giải thành một hay nhiều bài toán con giống bài toán cha chỉ khác nhau về kích thước bài toán.

2. Trị: Giải từng bài toán con theo cách giống như giải bài toán cha, mỗi bài toán cần giải sẽ dễ hơn do kích thước bài toán nhỏ hơn.

3. Kết hợp: Kết hợp lời giải các bài toán con lại thành lời giải của bài toán cha và tiếp tục như vậy đến khi thu được lời giải của bài toán ban đầu.

Hình 6. Sơ đồ thể hiện ba bước Chia, Trị, Kết hợp của thuật toán chia để trị giải bài toán A khi chia A thành hai bài toán con

Hình 7. Sơ đồ thể hiện ba bước Chia, Trị, Kết hợp của thuật toán chia để trị giải bài toán A khi chia bài toán cha thành hai bài toán con tại mỗi bước đệ quy

• Kĩ thuật đệ quy thường được áp dụng trong các bước của thuật toán chia để trị.

• Mô hình chung của phương pháp chia để trị giải một bài toán A được thể hiện thông qua đoạn mã giả như sau:

Nêu ưu điểm và hạn chế của kĩ thuật chia để trị?

Ưu điểm: là luôn đảm bảo tìm ra nghiệm đúng và thường cho thời gian thực hiện chương trình nhanh.

Nhược điểm: 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 để có thể thực hiện được kĩ thuật chia để trị.

LUYỆN TẬP

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?

A. Chia, Trị, Kết hợp.

B. Chia, Trị, Phân tích.

C. Chia, Trị, Giải bài toán.

D. Chia, Trị, Sắp xếp trộn.

A. Chia, Trị, Kết hợp.

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ì?

A. Reduce().

B. Merge().

C. Split().

D. Enumerate().

B. Merge().

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

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