Giải chi tiết chuyên đề Tin học Khoa học máy tính 11 Cánh diều mới bài 5: Thực hành tổng hợp ứng dụng chia để trị

Thực hành 1: Á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.

Hướng dẫn trả lờ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.

Thực hành 2 : Viết chương trình nhập vào một số nguyên dương n và n giá trị $A_{0},A_{1},…,A_{n-1}$ đôi một khác nhau, đưa ra số lượng nghịch thế của mảng vừa nhập vào.

Hướng dẫn trả lời: 

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 đầu vào và đưa ra kết quả để kiểm thử chương trình có cho kết quả đúng hay không.

Nếu kết quả kiểm thử trên một số bộ dữ liệu bị sai thì 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 (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 đó.

Bảng 1 là một số ví dụ thử nghiệm, em hãy tự tạo các ví dụ thử nghiệm khác.

Bảng 1: Một số bộ sữ liệu thử nghiệm cho Thực hành 2

Thực hành 3: Viết chương trình thực hiện thuật toán đơn giản bằng vòng lặp để đếm số lượng nghịch thế. Tiếp theo, em hãy đếm số bước thực hiện bởi thuật toán này so với thuật toán chia để trị ở trên trong một số ví dụ cụ thể.

Hướng dẫn trả lời: 

Bước 1. Cài đặt thuật toán đơn giản sử dụng hai vòng lặp lồng nhau duyệt qua tất cả các cặp hai phần tử của mảng dãy số để kiểm tra xem từng cặp hai phần tử có phải là nghịch thế hay không. Đồng thời thêm các biến đếm đặt trong vòng lặp thứ để tính số bước thực hiện của chương trình.

Bước 2. Bổ sung các biến đếm vào vị trí thích hợp trong hàm đệ quy của chương trình trong bài Thực hành 2 để tính số bước thực hiện của chương trình.

Vận dụng: Cho một mảng A gồm n phần tử $A_{0},A_{1},…,A_{n-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.

b) Viết chương trình nhập vào giá trị n và n giá trị $A_{0},A_{1},…,A_{n-1}$, đưa ra số lượng các cặp không phải là nghịch thể trong mảng A.

c) Tạo các bộ dữ liệu thử nghiệm để kiểm thử chương trình.

Hướng dẫn trả lời: 

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 đầu vào và đưa ra kết quả để kiểm thử chương trình có cho kết quả đúng hay không. Nếu kết quả kiểm thử trên một số bộ dữ liệu bị sai thì 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 đó.

b) void nhap(int a[], int &n);

void interchangesort(int a[], int n);
void swap(int &x, int &y);
void xuat(int a[],int n);
int main()
{
int a[1000],n,k;
nhap(a,n);
int pos[1000];
for (int i = 0; i < n; ++i)
pos = i;
interchangesort(a,n);
xuat(a,n);
cin>>k;
for (int i = 0; i <k; ++i)
cout<< pos;
}
void nhap(int a[], int &n)
{
cin>>n;
for(int i=0;i<n;i++)
cin>>a;
}
void interchangesort(int a[], int n)
{
for(int i=0;i<n-1;i++)
for(int j=i+1;j<n;j++)
if(a<a[j])
swap(a,a[j]);
}
void swap(int &x, int &y)
{
int t =x;
x=y;
y=t;
}
void xuat(int a[],int n)
{
for(int i=0;i<n;i++)
cout<<a<<" ";
}

c) Gợi ý:

Để tạo ra những bộ test data khác nhau, bạn có thể sử dụng nhiều tool khác nhau để tạo ra chúng. ví dụ: Test data được tạo bởi GSApps có thể được sử dụng để tạo ra các data thông minh trong hầu hết các cơ sở dữ liệu hoặc tập tin văn bản. Nó cho phép người sử dụng để:

Hoàn thành test ứng dụng bởi quá trình nhân bản cơ sở dữ liệu với dữ liệu thông minh.

Tạo dữ liệu industry-specific có thể dùng để chứng minh.

Bảo vệ dữ liệu riêng bằng cách tạo ra bản sao của dữ liệu và có ẩn các giá trị.

Đẩy nhanh quá trình tạo dữ liệu và kiểm thử.