Á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
Á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.
Giải Chuyên đề Tin học 11 Bài 5: Thực hành tổng hợp ứng dụng chia để trị - Cánh diều
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.
Lời giải:
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.
Lời giải Chuyên đề Tin 11 Bài 5: Thực hành tổng hợp ứng dụng chia để trị hay, ngắn gọn khác: