Cho một mảng A gồm n phần tử A0, A1,...An-1 hai phân tử bất kì có thể bằng nhau. Hãy tính số lượng những cặp hai phân tử mà không phải là nghịch thể trong mảng.

a) Vận dụng bài Thực hành 1 ở trên để mô tả chi tiết phương pháp chia để trị cho bài toán này.

a) Hướng dẫn: Sử dụng chương trình thuật toán sắp xếp trộn trong Bài 4 và phần hướng dân thuật toán trong Thực hành 1 đề hoàn thiện chương trình cho bài toán nảy.

Kiểm thử chương trình:

Em hãy nhập vào một số vị dụ mảng dầu vào và đưa ra kết quả để kiểm thử chương trinh có cho kết quả đúng hay không. Nếu kết quá kiểm thử trên một số bộ đữ liệu bị sai thi in ra các giá trị trung gian trong chương trình để quan sát sự thay đôi theo từng bước của thuật toán. Em hãy tạo một máng đâu vào có kích thước lớn (khoảng 1 triệu phần tử) và được sắp xếp giảm dần. Từ đó thử chạy chương trình với mảng đầu vào đó.