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
Gợi ý: 7 3 8 2->3 7 2 8 ->2 3 7 8
Lời giải:
Em chia đôi dãy gồm bốn số {7, 3, 8, 2} làm hai nửa để thực hiện công việc sắp xếp bốn số này theo thứ tự tăng dần của giá trị: 7 3 8 2->3 7 2 8 ->2 3 7 8
1. Ý tưởng thuật toán sắp xếp trộn
Lời giải:
Giai đoạn 1: Ở giai đoạn này. với mỗi lượt, mỗi dãy được chia làm hai dãy nhỏ với mục tiêu sắp xếp tăng dần trên từng dãy nhỏ (Hình 1). Quá trình kết thúc khi mỗi dãy có đúng một bạn:
Lượt 1: Chia thành hai dãy, một dãy 2 bạn (Thi, An) và một dãy 3 bạn (Hoà, Lâm, Mai).
Lượt 2: Chia mỗi dãy trong hai dãy trên thành hai dãy nhỏ, lần hượt là: (Thi), (An) (Hoà) và (Lâm, Mai).
Lượt 3: Chia dãy (Lâm, Mai) thành hai dãy mỗi dãy có đúng một bạn: (Lâm), (Mai).
2. Thuật toán sắp xếp trộn
3. Mô hình tổng quát của phương pháp chia để trị
Lời giải:
Các thuật toán sắp xếp đơn giản như Bubble Sort, Insertion Sort . . . đều không thể xử lý được dữ liệu lớn. Thuật toán sắp xếp trộn lấy ý tưởng từ việc chia để trị để chia nhỏ bài toán thành các bài toán nhỏ hơn, sau đó giải quyết chúng. Từ đó sẽ giúp xử lý dữ liệu lớn một cách tốt hơn, tối ưu về mặt thời gian.
Ý tưởng đưa ra như sau:
Chia danh sách gồm n phần tử chưa được sắp xếp thành n danh sách con, mỗi danh sách chứa một phần tử (danh sách một phần tử được coi là đã sắp xếp).
Liên tục hợp nhất các danh sách con để tạo ra các danh sách con được sắp xếp mớ cho đến khi chỉ còn lại một danh sách. Đây sẽ là danh sách được sắp xếp.
Ví dụ:
void Swap(int &a, int &b){
int temp = a;
a = b;
b = temp;
}
void InterchangeSort(int a[], int n){
for (int i = 0; i < n - 1; i++)
for (int j = i + 1; j < n; j++)
if(a[i] > a[j]) //nếu có nghịch thế thì đổi chỗ
Swap(a[i], a[j]);
}
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;
}
a) Chia nhỏ bài toán: Kết hợp kết quả các bài toán con; Giải từng bài toán con bằng đệ quy.
b) Giải bài toán; Chia nhỏ bài toán; Kết hợp các kết quả bài toán.
c) Chia nhỏ bài toán; Giải từng bài toán con bằng đệ quy; Kết hợp kết quả các bài toán con.
Lời giải:
Trong các câu sau đây, câu sau đúng khi mô tả trình tự các bước cơ bản của phương pháp chia để trị:
c) Chia nhỏ bài toán; Giải từng bài toán con bằng đệ quy; Kết hợp kết quả các bài toán con.
Xem thêm lời giải bài tập Chuyên đề học tập Tin học lớp 11 Cánh diều hay, chi tiết khác:
Bài 2: Kĩ thuật đệ quy trong chia để trị
Bài 3: Thực hành ứng dụng thuật toán tìm kiếm nhị phân bằng đệ quy
