Trang bìa
Trang bìa
Ảnh
CHUYÊN ĐỀ 2. THỰC HÀNH THIẾT KẾ THUẬT TOÁN THEO KĨ THUẬT CHIA ĐỂ TRỊ
BÀI 4. KĨ THUẬT CHIA ĐỂ TRỊ TRONG THUẬT TOÁN SẮP XẾP TRỘN
Mở đầu
Bài học
Học xong bài này, em sẽ - Hiểu được các bước cần thực hiện khi giả bài toán sắp xếp dãy số bằng thuật toán sắp xếp trộn - Biết được cách cài đặt thuật toán sắp xếp trộn - Nêu được ý tưởng kĩ thuật chia để trị tổng quát bằng đệ quy - Biết được các bước cơ bản của kĩ thuật chia để trị để giải một bài toán
Ví dụ
Hình vẽ
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ị Gợi ý: 7 3 8 2 -> 3 7 2 8 -> 2 3 7 8
Ảnh
Ý tưởng thuật toán sắp xếp trộn
Bài toán
Hình vẽ
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 tăng dần theo chiều cao từ trái sang phải.
Ảnh
Giai đoạn 1
Giai đoạn 1: 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 1 bạn Lượt 1: Chia thành 2 dãy, Dãy 1 ( Thi, An), dãy 2 (Hòa, Lâm, Mai) Lượt 2: Chia mỗi dãy trên thành hai dãy nhỏ, lần lượt là (Thi), (An), (Hòa), (Lâm, Mai) Lượt 3: Chia dãy (Lâm, Mai) thành hai dãy, mỗi dãy có đúng 1 bạn (Lâm), (Mai)
Hình minh họa GĐ1
Ảnh
Giai đoạn 2
Giai đoạn 2: Với mỗi lượt, cứ hai dãy liên tiếp được tách ra từ GD1 theo trình tự ngược lại 3, 2, 1 sẽ được kết hợp thành một dãy. Sau mỗi lượt, các bạn có trong từng dãy nhỏ có chiều cao tăng dần: Lượt 1: Kết hợp dãy (Lâm), (Mai), Lâm cao hơn Mai, xếp Mai trước Lâm, ta được dãy (Mai, Lâm) Lượt 2: - Kết hợp dãy (Thi), (An), Thi cao hơn An, xếp An trước Thi, ta được dãy (An, Thi) - Kết hợp dãy (Hòa), (Mai, Lâm), Hòa cao hơn Mai, xếp Mai ở đầu dãy, Hòa cao hơn Lâm, xếp Lâm đứng cạnh Mai và Hòa đứng cạnh Lâm, ta được dãy (Mai, Lâm, Hòa) Lượt 3: Kết hợp dãy (An, Thi) và (Mai, Lâm, Hòa), An cao hơn Mai, xếp Mai đầu dãy, An thấp hơn Lâm, xếp An cạnh Mai; Thi thấp hơn Lâm, xếp Thi cạnh An, sau đó đến Lâm và Hòa. Ta được dãy ( Mai, An, Thi, Lâm, Hòa)
Hình minh họa GD2
Ảnh
Nhận xét
Nhận xét: 3 bước cơ bản của kĩ thuật chia để trị: 1. Chia: Chia một dãy thành hai 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 kết thúc khi mỗi dãy nhỏ chỉ còn 1 bạn. Mục tiêu mỗi lượt ở GD1 là chia dãy thành hai dãy nhỏ và thực hiện lặp lại bài toán sắp xếp trên từng dãy nhỏ. Sau mỗi lượt ở GD2, mô dãy nhỏ đều được sắp xếp tăng dâ và là kết quả của mục tiêu ở từng lượt GD1 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 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
Thuật toán sắp xếp trộn
Bài toán
Hình vẽ
Bài toán: Cho dãy A gồm n phần tử latex(A_0, A_1,...,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ử latex(A_0, A_1,...,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
Cách làm
1. Chia: Chia dãy A thành hai dãy con (latex(A_0,A_1,...,A_k)) và (latex(A_k,A_(k+1),...,A_(n+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 mỗi 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 hai dãy 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 viji 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
Ví dụ
Ảnh
Thực hành
Em hãy tìm hiê 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
Ảnh
Đoạn chương trình
Ảnh
Đoạn chương trình
Ảnh
Khái niệm
Hình vẽ
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: 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
Mô hình tổng quát
Các bước cơ bản
1. Chia: Chia bài toán đang giải ( bài toán cha) 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ư 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. Giải trực tiếp bài toán con khi kích thước bài toán đủ nhỏ, gọi là trường hợp cơ sở 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
Sơ đồ khối
Ảnh
Sơ đồ khối
Nếu bài toán con tiếp tục được chia đệ quy thành hai bài toán con nhỏ hơn, sơ đồ có dạng:
Ảnh
Nhận xét
Hình vẽ
Nhận xét: Kĩ thuật đệ quy thường được áp dụng trong các bước của thuật toán chia để trị. Mỗi bài toán con được giải bằng cách gọi cùng một thủ tục đệ quy giải bài toán cha với các tham số đầu vào có kích thước nhỏ hơn
Mã giả
Ảnh
Mô hình chung của phương pháp chia để trị giải một bài toán A có thể được thực hiện thông qua đoạn mã giả
Ưu- Nhược điểm
Hình vẽ
Ưu điểm: 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
Bài tập
Hội diễn văn nghệ của trường năm nay, lớp Thanh An tham gia biệu diễn kiêu vũ tập thể theo gặp (nam, nữ). Thầy giáo chủ nhiệm chọn ra n bạn nam có chiều cao latex(A_0,A_1,...,A(n-1)) đứng thành một hàng nàng và n bạn nữ có chiều cao latex(B_0,B_1,...,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 và nữ trong hà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, cứ xêp như vậy đến khi 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 1 số nguyên n, tiếp theo nhận vào n giá trị latex(A_0,A_1,...,A(n-1)) và n giá trị latex(B_0,B_1,...,B(n-1)) Cần in ra n cặp số latex(A_i, B_j (0 le i,j le n-1)) là cách xếp cặp (nam, nữ) theo mong muốn của thầy giáo ở trên
Bài tập
Bài tập trắc nghiệm
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ị?
Chia nhỏ bài toán; Kết hợp kê quả các bài toán con; Giải ừng bài toán con bằng đệ quy
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
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
Kết thúc
Tóm tắt bài học
Hình vẽ
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 Ý tưởng chính của thuật toán sắp xếp trộn là 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à cuối cùng kết hợp kết quả của hai bài toán lại thành kết quả của bài toán ban đầu Hàm Merge() 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
TÓM TẮT BÀI HỌC
Tạm biệt
Ảnh