Với giải Thực hành 1 trang 47 Chuyên đề Tin học 11 Cánh diều chi tiết trong Bài 5: Thực hành tổng hợp ứng dụng chia để trị giúp học sinh dễ dàng xem và so sánh lời giải từ đó biết cách làm bài tập Chuyên đề Tin học 11. Mời các bạn đón xem:

Giải bài tập Chuyên đề Tin học 11 Bài 5: Thực hành tổng hợp ứng dụng chia để trị

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.