Câu hỏi:
03/07/2023 176
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. Ví dụ: Em hãy 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ị.
Gợi ý: 7 3 8 2->3 7 2 8 ->2 3 7 8
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. Ví dụ: Em hãy 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ị.
Gợi ý: 7 3 8 2->3 7 2 8 ->2 3 7 8
Quảng cáo
Trả lờ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
Hot: Học hè online Toán, Văn, Anh...lớp 1-12 tại Vietjack với hơn 1 triệu bài tập có đáp án. Học ngay
- Trọng tâm Hóa học 11 dùng cho cả 3 bộ sách Kết nối, Cánh diều, Chân trời sáng tạo VietJack - Sách 2025 ( 58.000₫ )
- Sách - Sổ tay kiến thức trọng tâm Vật lí 11 VietJack - Sách 2025 theo chương trình mới cho 2k8 ( 45.000₫ )
- Sách lớp 11 - Trọng tâm Toán, Lý, Hóa, Sử, Địa lớp 11 3 bộ sách KNTT, CTST, CD VietJack ( 52.000₫ )
- Sách lớp 10 - Combo Trọng tâm Toán, Văn, Anh và Lí, Hóa, Sinh cho cả 3 bộ KNTT, CD, CTST VietJack ( 75.000₫ )
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Lời giải
Giai đoạn I: Ở 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
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 (Hoa, Lâm, Mai).
Lượt 2: Chia mỗi đây trong hai dây trên thành hai dãy nhỏ. lần hượt lá: (Thi), (An) (Hoa) và (Lâm, Mai).
Lượt 3: Chia dãy (Lâm, Mai) thành hai đây mỗi dãy có đúng một bạn: (Lâm), (Mai)
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
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.