Giải chuyên đề tin học 11 định hướng Khoa học máy tính cánh diều

CHUYÊN ĐỀ 1. THỰC HÀNH THIẾT KẾ THUẬT TOÁN THEO KĨ THUẬT ĐỆ QUY

Giải chuyên đề Tin học khoa học máy tính 11 cánh diều bài 1 Khái niệm đệ quy và ví dụ
Giải chuyên đề Tin học khoa học máy tính 11 cánh diều bài 2 Thuật toán đệ quy
Giải chuyên đề Tin học khoa học máy tính 11 cánh diều bài 3 Thực hành thiết kế thuật toán đệ quy
Giải chuyên đề Tin học khoa học máy tính 11 cánh diều bài 4 Thực hành tổng hợp thiết kế thuật toán đệ quy

CHUYÊN ĐỀ 2. THỰC HÀNH THIẾT KẾ THUẬT TOÁN THEO KĨ THUẬT CHIA ĐỂ TRỊ

Giải chuyên đề Tin học khoa học máy tính 11 cánh diều bài 1 Ý tưởng chia để trị
Giải chuyên đề Tin học khoa học máy tính 11 cánh diều bài 2 Kĩ thuật đệ quy trong chia để trị
Giải chuyên đề Tin học khoa học máy tính 11 cánh diều bài 3 Thực hành ứng dụng thuật toán tìm kiếm nhị phân bằng đệ quy
Giải chuyên đề Tin học khoa học máy tính 11 cánh diều bài 4 Kĩ thuật chia để trị trong thuật toán sắp xếp trộn
Giải chuyên đề Tin học khoa học máy tính 11 cánh diều bài 5 Thực hành tổng hợp ứng dụng chia để trị

CHUYÊN ĐỀ 3. THỰC HÀNH THIẾT KẾ THUẬT TOÁN THEO KĨ THUẬT DUYỆT

Giải chuyên đề Tin học khoa học máy tính 11 cánh diều bài 1 Kỹ thuật duyệt
Giải chuyên đề Tin học khoa học máy tính 11 cánh diều bài 2 Kỹ thuật quay lui
Giải chuyên đề Tin học khoa học máy tính 11 cánh diều bài 3 Thực hành kĩ thuật quay lui
Giải chuyên đề Tin học khoa học máy tính 11 cánh diều bài 4 Thực hành tổng hợp kĩ thuật duyệt
Giải chuyên đề Tin học khoa học máy tính 11 cánh diều bài 5 Thực hành kỹ thuật quy lui giải bài toán xếp hậu
Giải chuyên đề Tin học khoa học máy tính 11 cánh diều bài 6 Dự án Xây dựng chương trình sử dụng kĩ thuật duyệt

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,....

Vận dụng

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.


Gợ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;
}

Xem toàn bộ: Giải chuyên đề Tin học khoa học máy tính 11 cánh diều bài 4 Kĩ thuật chia để trị trong thuật toán sắp xếp trộn

Giải những bài tập khác

Bình luận

Giải bài tập những môn khác

Giải sgk lớp 11 KNTT

Giải sgk lớp 11 CTST

 

Giải sgk lớp 11 cánh diều

 

Giải SBT lớp 11 kết nối tri thức

Giải SBT lớp 11 chân trời sáng tạo

Giải SBT lớp 11 cánh diều

Giải chuyên đề học tập lớp 11 kết nối tri thức

Giải chuyên đề toán 11 kết nối tri thức
Giải chuyên đề ngữ văn 11 kết nối tri thức
Giải chuyên đề vật lí 11 kết nối tri thức
Giải chuyên đề hóa học 11 kết nối tri thức
Giải chuyên đề sinh học 11 kết nối tri thức

Giải chuyên đề kinh tế pháp luật 11 kết nối tri thức
Giải chuyên đề lịch sử 11 kết nối tri thức
Giải chuyên đề địa lí 11 kết nối tri thức
Giải chuyên đề mĩ thuật 11 kết nối tri thức
Giải chuyên đề âm nhạc 11 kết nối tri thức
Giải chuyên đề công nghệ chăn nuôi 11 kết nối tri thức

Giải chuyên đề công nghệ cơ khí 11 kết nối tri thức
Giải chuyên đề tin học 11 định hướng Khoa học máy tính kết nối tri thức
Giải chuyên đề tin học 11 định hướng Tin học ứng dụng kết nối tri thức
Giải chuyên đề quốc phòng an ninh 11 kết nối tri thức
Giải chuyên đề hoạt động trải nghiệm hướng nghiệp 11 kết nối tri thức

Giải chuyên đề học tập lớp 11 chân trời sáng tạo

Giải chuyên đề học tập lớp 11 cánh diều

 

Trắc nghiệm 11 Kết nối tri thức

Trắc nghiệm 11 Chân trời sáng tạo

Trắc nghiệm 11 Cánh diều

Bộ đề thi, đề kiểm tra lớp 11 kết nối tri thức

Đề thi Toán 11 Kết nối tri thức
Đề thi ngữ văn 11 Kết nối tri thức
Đề thi vật lí 11 Kết nối tri thức
Đề thi sinh học 11 Kết nối tri thức
Đề thi hóa học 11 Kết nối tri thức
Đề thi lịch sử 11 Kết nối tri thức
Đề thi địa lí 11 Kết nối tri thức
Đề thi kinh tế pháp luật 11 Kết nối tri thức
Đề thi công nghệ cơ khí 11 Kết nối tri thức
Đề thi công nghệ chăn nuôi 11 Kết nối tri thức
Đề thi tin học ứng dụng 11 Kết nối tri thức
Đề thi khoa học máy tính 11 Kết nối tri thức

Bộ đề thi, đề kiểm tra lớp 11 chân trời sáng tạo

 

Bộ đề thi, đề kiểm tra lớp 11 cánh diều

Đề thi Toán 11 Cánh diều
Đề thi ngữ văn 11 Cánh diều
Đề thi vật lí 11 Cánh diều
Đề thi sinh học 11 Cánh diều
Đề thi hóa học 11 Cánh diều
Đề thi lịch sử 11 Cánh diều
Đề thi địa lí 11 Cánh diều
Đề thi kinh tế pháp luật 11 Cánh diều
Đề thi công nghệ cơ khí 11 Cánh diều
Đề thi công nghệ chăn nuôi 11 Cánh diều
Đề thi tin học ứng dụng 11 Cánh diều
Đề thi khoa học máy tính 11 Cánh diều

Giáo án lớp 11