Câu hỏi:
03/07/2023 171
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:
Giải bởi Vietjack
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
Sách thầy cô Vietjack biên soạn:
- Trọng tâm Sử, Địa, GD KTPL 11 cho cả 3 bộ Kết nối, Chân trời, Cánh diều VietJack - Sách 2025 ( 38.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₫ )
Bình luận
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.
🔥 Đề thi HOT:
-
Bộ 4 đề thi cuối học kì 2 Tin 11 Kết nối tri thức có đáp án (Đề 2)
-
15 câu Trắc nghiệm Tin học 11 Kết nối tri thức Bài 26 có đáp án
-
Bộ 4 đề thi cuối học kì 2 Tin 11 Kết nối tri thức có đáp án (Đề 1)
-
15 câu Trắc nghiệm Tin học 11 Cánh diều Bài 1: Một số thao tác chỉnh sửa ảnh và hỗ trợ chỉnh sửa ảnh có đáp án
-
15 câu Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25 có đáp án
-
15 câu Trắc nghiệm Tin học 11 Kết nối tri thức Bài 28 có đáp án
-
15 câu Trắc nghiệm Tin học 11 Kết nối tri thức Bài 27 có đáp án
-
15 câu Trắc nghiệm Tin học 11 Cánh diều Bài 2: Tẩy xóa ảnh có đáp án
Hãy Đăng nhập hoặc Tạo tài khoản để gửi bình luận
-
-
Bình luận