Nội dung bài viết

    Xem thêm

    Áp dụng trực tiếp thuật toán sắp xếp trộn ở trên để mô tả chi tiết phương pháp chia để trị

    Trả lời Thực hành 1 trang 47 Chuyên đề Tin học 11 sách Cánh diều hay nhất, chi tiết sẽ giúp học sinh dễ dàng làm bài tập Tin học 11.

    1 374 18/07/2023
    Trang trước
    Chia sẻ
    Trang sau  

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

    Thực hành 1 trang 47 Chuyên đề Tin học 11: Áp dụng trực tiếp thuật toán sắp xếp trộn ở trên để mô tả chi tiết phương pháp chia để trị giải bài toán đếm số lượng nghịch thế ở trên.

    Lời giải:

    Khi chia mảng A thành hai mảng con T và P, số lượng nghịch thế từ những cặp phần tử mà một phần tử thuộc mảng T và một phần tử thuộc mảng P sẽ không thay đổi nếu ta sắp xếp các phần tử trong từng mảng T và P tăng dần. Nhận xét này giúp cho chúng ta có thể áp dụng trực tiếp các bước của thuật toán sắp xếp trộn ở trên như sau:

    1. Chia: Sử dụng thuật toán chia của hàm Merge_sort(A).

    2. Trị: Gọi đệ quy hàm Merge_sort(T)và Merge_sort(P) để giải từng bài toán con, đồng thời cập nhật kết quả đếm số lượng nghịch thế từng bài toán con vào một biến đếm.

    3. Kết hợp: Sử dụng thuật toán trộn của hàm Merge(A), đồng thời cập nhật số lượng nghịch thế từ những cặp phần tử mà một phần tử thuộc mảng T và một phần tử thuộc mảng P, các phần tử trong hai mảng này đều đã được sắp xếp tăng dần.

    Gợi ý: Trong hàm Merge(A), mỗi khi xảy ra điều kiện T[i]>P[j], nghĩa là các phần tử từ T[i+1] đến phần tử cuối cùng của mảng T đều lớn hơn P[j], số lượng nghịch thế cần được cập nhật thêm là len (T) −i, với len (T) là số lượng phần tử của mảng T.

    Em hãy mô tả chi tiết kết quả từng bước trong các hướng dẫn 1, 2, 3 trên cho một trường hợp mảng số cụ thể, ví dụ thực hành trên mảng gồm 7 số có các giá trị lần lượt là 9, 44, 7, 2, 8, 17, 31.

    Xem thêm giải bài tập Chuyên đề Tin học 11 Cánh diều hay, chi tiết khác:

    Thực hành 1 trang 47 Chuyên đề Tin học 11: Áp dụng trực tiếp thuật toán sắp xếp trộn ở trên để mô tả chi tiết phương pháp chia để trị giải bài toán đếm số lượng nghịch thế ở trên.

    Thực hành 2 trang 47 Chuyên đề Tin học 11: Viết chương trình nhập vào một số nguyên dương n và n giá trị A0,A1,…,An-1 

    Thực hành 3 trang 48 Chuyên đề Tin học 11: Viết chương trình thực hiện thuật toán đơn giản bằng vòng lặp để đếm số lượng

    Vận dụng trang 48 Chuyên đề Tin học 11: Cho một mảng A gồm n phần tử A0, A1,...An-1, hai phân tử bất kì có thể bằng nhau.

    Xem thêm giải bài tập Chuyên đề Tin học 11 Cánh diều hay, chi tiết khác:

    Bài 4: Thực hành tổng hợp thiết kế thuật toán đệ quy

    Bài 1: Ý tưởng chia để trị

    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

    Bài 4: Kĩ thuật chia để trị trong thuật toán sắp xếp trộn

    Tham khảo các loạt bài Tin học 11 khác:

    Bài viết cùng lớp mới nhất

    Xem thêm
    1 374 18/07/2023
    Trang trước
    Chia sẻ
    Trang sau  

    Xem thêm các chương trình khác: