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ũ

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

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<stdlib.h>

#include<stdio.h>

// 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<stdlib.h>

#include<stdio.h>

// 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;

}

Lời giải Chuyên đề Tin 11 Bài 4: Kĩ thuật chia để trị trong thuật toán sắp xếp trộn hay, ngắn gọn khác:

• Khởi động trang 38 Chuyên đề Tin học 11: Bài 2 giới thiệu kĩ thuật đệ quy trong phương pháp chia để trị. Nhiều bài được giải quyết dễ dàng bằng cách sử dụng kĩ thuật đệ quy ....

• Hoạt động trang 38 Chuyên đề Tin học 11: Thầy giáo lớp Thanh An mời 5 bạn học sinh lên bảng, xếp ngẫu nhiên thành một hàng ngang, từ trái sang phải là các bạn có tên Thi, An, Hoà, Lâm, Mai ....

• Luyện tập trang 45 Chuyên đề Tin học 11: Em hãy cho biết trong mô tả thuật toán sắp xếp trộn và trong chương tình cài đặt ở trên cần thay đổi thế nào để sắp xếp một dãy ....

• Câu hỏi tự kiểm tra trang 45 Chuyên đề Tin học 11: Trong các câu sau đây, câu nào đúng khi mô tả trình tự các bước cơ bản của phương pháp chia để trị? ....

Xem thêm lời giải bài tập Chuyên đề học tập Tin học 11 Cánh diều hay, ngắn gọn khác:

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

• Chuyên đề Tin học 11 Bài 1: Kĩ thuật duyệt

• Chuyên đề Tin học 11 Bài 2: Kĩ thuật quay lui

• Chuyên đề Tin học 11 Bài 3: Thực hành kĩ thuật quay lui

• Chuyên đề Tin học 11 Bài 4: Thực hành tổng hợp kĩ thuật duyệt

Săn SALE shopee Tết:

• Mỹ phẩm SACE LADY giảm tới 200k
• SRM Simple tặng tẩy trang 50k
• Combo Dầu Gội, Dầu Xả TRESEMME 80k

---