Hội diễn văn nghệ của trường năm nay, lớp Thanh An tham gia biểu diễn khiêu vũ tập thể

Giải Chuyên đề Tin học 11 Cánh diều Bài 4: Kĩ thuật chia để trị trong thuật toán sắp xếp trộn

Vận dụng trang 45 Chuyên đề Tin học 11: Hội diễn văn nghệ của trường năm nay, lớp Thanh An tham gia biểu diễn khiêu vũ tập thể theo cặp (nam, nữ). Thầy giáo chủ nhiệm chọn ra n bạn nam có chiều cao A0, A1,...An-1, đứng thành một hàng ngang và n bạn nữ có chiều cao B0, B1,...Bn-1 đứng thành một hàng ngang để ghép thành n cặp (nam, nữ). Để tiện ghép cặp, thầy giáo sắp xếp lại vị trí đứng các bạn nam trong hàng theo thứ tự chiều cao tăng dần và vị trí đứng các bạn nữ trong hàng cũng theo thứ tự chiều cao tăng dần. Sau đó thầy giáo tiến hành ghép cặp bạn nam thấp nhất với bạn nữ thấp nhất, bạn nam thấp thứ hai với bạn nữ thấp thứ hai và cứ như vậy đến bạn nam cao nhất với bạn nữ cao nhất. Em hãy viết chương trình áp dựng thuật toán sắp xếp trộn đề giúp thầy giáo thực hiện công việc ghép cặp này.

Chương trình cần nhập vào một số nguyên n, tiếp theo nhập vào n giá trị A0, A1, An-1 và n giá trị B0, B1, Bn-1.

Chương trình cần in ra n cặp số Ai, Bj (0 < i, j < n-1) là cách xếp cặp (nam, nữ) theo mong muốn của thầy giáo ở trên.

Lời giải:

// Code from https://nguyenvanhieu.vn

#include

#include

// Gộp hai mảng con arr[l...m] và arr[m+1..r]

void merge(int arr[], int l, int m, int r)

{

int i, j, k;

int n1 = m - l + 1;

int n2 = r - m;

/* Tạo các mảng tạm */

int L[n1], R[n2];

/* Copy dữ liệu sang các mảng tạm */

for (i = 0; i < n1; i++)

L[i] = arr[l + i];

for (j = 0; j < n2; j++)

R[j] = arr[m + 1+ j];

/* Gộp hai mảng tạm vừa rồi vào mảng arr*/

i = 0; // Khởi tạo chỉ số bắt đầu của mảng con đầu tiên

j = 0; // Khởi tạo chỉ số bắt đầu của mảng con thứ hai

k = l; // IKhởi tạo chỉ số bắt đầu của mảng lưu kết quả

while (i < n1 && j < n2)

{

if (L[i] <= R[j])

{

arr[k] = L[i];

i++;

}

else

{

arr[k] = R[j];

j++;

}

k++;

}

/* Copy các phần tử còn lại của mảng L vào arr nếu có */

while (i < n1)

{

arr[k] = L[i];

i++;

k++;

}

/* Copy các phần tử còn lại của mảng R vào arr nếu có */

while (j < n2)

{

arr[k] = R[j];

j++;

k++;

}

}

/* l là chỉ số trái và r là chỉ số phải của mảng cần được sắp xếp */

void mergeSort(int arr[], int l, int r)

{

if (l < r)

{

// Tương tự (l+r)/2, nhưng cách này tránh tràn số khi l và r lớn

int m = l+(r-l)/2;

// Gọi hàm đệ quy tiếp tục chia đôi từng nửa mảng

mergeSort(arr, l, m);

mergeSort(arr, m+1, r);

merge(arr, l, m, r);

}

}

/* Hàm xuất mảng */

void printArray(int A[], int size)

{

int i;

for (i=0; i < size; i++)

printf("%d ", A[i]);

printf("\n");

}

int main()

{

int arr[] = {12, 11, 13, 5, 6, 7};

int arr_size = sizeof(arr)/sizeof(arr[0]);

printf("Given array is \n");

printArray(arr, arr_size);

mergeSort(arr, 0, arr_size - 1);

printf("\nSorted array is \n");

printArray(arr, arr_size);

return 0;

}// Code from https://nguyenvanhieu.vn

#include

#include

// Gộp hai mảng con arr[l...m] và arr[m+1..r]

void merge(int arr[], int l, int m, int r)

{

int i, j, k;

int n1 = m - l + 1;

int n2 = r - m;

/* Tạo các mảng tạm */

int L[n1], R[n2];

/* Copy dữ liệu sang các mảng tạm */

for (i = 0; i < n1; i++)

L[i] = arr[l + i];

for (j = 0; j < n2; j++)

R[j] = arr[m + 1+ j];

/* Gộp hai mảng tạm vừa rồi vào mảng arr*/

i = 0; // Khởi tạo chỉ số bắt đầu của mảng con đầu tiên

j = 0; // Khởi tạo chỉ số bắt đầu của mảng con thứ hai

k = l; // IKhởi tạo chỉ số bắt đầu của mảng lưu kết quả

while (i < n1 && j < n2)

{

if (L[i] <= R[j])

{

arr[k] = L[i];

i++;

}

else

{

arr[k] = R[j];

j++;

}

k++;

}

/* Copy các phần tử còn lại của mảng L vào arr nếu có */

while (i < n1)

{

arr[k] = L[i];

i++;

k++;

}

/* Copy các phần tử còn lại của mảng R vào arr nếu có */

while (j < n2)

{

arr[k] = R[j];

j++;

k++;

}

}

/* l là chỉ số trái và r là chỉ số phải của mảng cần được sắp xếp */

void mergeSort(int arr[], int l, int r)

{

if (l < r)

{

// Tương tự (l+r)/2, nhưng cách này tránh tràn số khi l và r lớn

int m = l+(r-l)/2;

// Gọi hàm đệ quy tiếp tục chia đôi từng nửa mảng

mergeSort(arr, l, m);

mergeSort(arr, m+1, r);

merge(arr, l, m, r);

}

}

/* Hàm xuất mảng */

void printArray(int A[], int size)

{

int i;

for (i=0; i < size; i++)

printf("%d ", A[i]);

printf("\n");

}

int main()

{

int arr[] = {12, 11, 13, 5, 6, 7};

int arr_size = sizeof(arr)/sizeof(arr[0]);

printf("Given array is \n");

printArray(arr, arr_size);

mergeSort(arr, 0, arr_size - 1);

printf("\nSorted array is \n");

printArray(arr, arr_size);

return 0;

}