Thực hành 1 trang 47 Chuyên đề Tin học 11: Áp dụng trực tiếp thuật toán sắp xếp trộn ở trên để mô tả chi tiết phương pháp chia để trị giải bài toán đếm số lượng nghịch thế ở trên.
Khi chia mảng A thành hai mảng con T và P, số lượng nghịch thế từ những cặp phần tử mà một phần tử thuộc mảng T và một phần tử thuộc mảng P sẽ không thay đổi nếu ta sắp xếp các phần tử trong từng mảng T và P tăng dần. Nhận xét này giúp cho chúng ta có thể áp dụng trực tiếp các bước của thuật toán sắp xếp trộn ở trên như sau:
1. Chia: Sử dụng thuật toán chia của hàm Merge_sort(A).
2. Trị: Gọi đệ quy hàm Merge_sort(T)và Merge_sort(P) để giải từng bài toán con, đồng thời cập nhật kết quả đếm số lượng nghịch thế từng bài toán con vào một biến đếm.
3. Kết hợp: Sử dụng thuật toán trộn của hàm Merge(A), đồng thời cập nhật số lượng nghịch thế từ những cặp phần tử mà một phần tử thuộc mảng T và một phần tử thuộc mảng P, các phần tử trong hai mảng này đều đã được sắp xếp tăng dần.
Gợi ý: Trong hàm Merge(A), mỗi khi xảy ra điều kiện T[i]>P[j], nghĩa là các phần tử từ T[i+1] đến phần tử cuối cùng của mảng T đều lớn hơn P[j], số lượng nghịch thế cần được cập nhật thêm là len (T) −i, với len (T) là số lượng phần tử của mảng T.
Em hãy mô tả chi tiết kết quả từng bước trong các hướng dẫn 1, 2, 3 trên cho một trường hợp mảng số cụ thể, ví dụ thực hành trên mảng gồm 7 số có các giá trị lần lượt là 9, 44, 7, 2, 8, 17, 31.
Xem thêm lời giải bài tập Chuyên đề học tập Tin học lớp 11 Cánh diều hay, chi tiết khác:
Bài 3: Thực hành ứng dụng thuật toán tìm kiếm nhị phân bằng đệ quy
Bài 4: Kĩ thuật chia để trị trong thuật toán sắp xếp trộn