Giáo án điện tử chuyên đề 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ị

XIN CHÀO CÁC EM!

CHÀO MỪNG CÁC EM ĐẾN VỚI

BÀI HỌC NGÀY HÔM NAY!

KHỞI ĐỘNG

Hình 1. Minh họa hệ thống gợi ý trong thương mại điện tử

Các trang web thương mại điện tử ứng dụng trí tuệ nhân tạo thường lưu lại lịch sử thói quen khách hàng khi tương tác với các sản phẩm. Lịch sử tương tác của mỗi khách hàng sẽ được lưu vào một mảng chứa các hành động như: xem, bấm nút “thích” (“like”), mua hàng, theo thứ tự thời gian. Một phương pháp đơn giản và

hiệu quả để gợi ý cho khách hàng là áp dụng bài toán đếm số nghịch thế trong mảng. Chương trình sẽ so sánh mảng của khách hàng đang tương tác trên trang web với mảng của các khách hàng trong lịch sử để đưa ra gợi ý dựa trên số nghịch thế giữa hai mảng.

BÀI 5. THỰC HÀNH

TỔNG HỢP ỨNG DỤNG

CHIA ĐỂ TRỊ

NHIỆM VỤ. TÍNH SỐ NGHỊCH THỂ TRONG MẢNG

Cho một mảng A gồm n phần tử A0, A1,…,An-1 đôi một khác nhau. Hai phần tử Ai, Aj với j < j được gọi là nghịch thế nếu như Ai > Aj. Hãy tính số lượng nghịch thế trong mảng.

Bài toán

YÊU CẦU

Sản phẩm của mỗi nhóm qua bài thực hành này bao gồm:

• Thực hành 1: Mô tả chi tiết thuật toán giải quyết bài toán.
• Thực hành 2: Viết chương trình giải quyết bài toán.
• Thực hành 3: Kết quả thử nghiệm trên các bộ dữ liệu đầu vào mẫu và tự tạo.

Á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 1

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() 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ố 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 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.

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 đôi một khác nhau, đưa ra số lượng nghịch thế của mảng vừa nhập vào.

THỰC HÀNH 2

Hướng dẫn

Sử dụng chương trình thuật toán sắp xếp trộn và thuật toán trong Thực hành 1 để hoàn thiện chương trình.

Hàm Merge_sort(A) gần như giữ nguyên ngoại trừ việc bổ sung các dòng lệnh cộng dồn biến đếm số lượng nghịch thế tính được trong hàm Merge() vào kết quả cuối cùng.

Hàm Merge(A, T, P) được bổ sung thêm biến đếm tính số lượng nghịch thế tạo ra bởi các cặp phần tử mà một phần tử nằm trong mảng con T và phần tử còn lại nằm trong mảng con P.

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 nghịch thế. Tiếp theo, em hãy đếm số bước thực hiện bởi thuật toán này so với thuật toán chia để trị ở trên trong một số ví dụ cụ thể.

THỰC HÀNH 3

1

• Cài đặt thuật toán đơn giản sử dụng hai vòng lặp lồng nhau duyệt qua tất cả các cặp hai phần tử của mảng dãy số để kiểm tra xem từng cặp hai phần tử có phải là nghịch thế hay không.
• Đồng thời thêm các biến đếm đặt trong vòng lặp thứ để tính số bước thực hiện của chương trình.

2

• Bổ sung các biến đếm vào vị trí thích hợp trong hàm đệ quy của chương trình trong bài Thực hành 2 để tính số bước thực hiện của chương trình.

LUYỆN TẬP

Câu 1. Trong hàm Merge(A), mỗi khi xảy ra điều kiện T[i] > P[j] có nghĩa là

A. Các phần tử từ T[i+1] đến phần tử cuối cùng của mảng T đều nhỏ hơn P[j].

B. 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].

C. Các phần tử từ T[i+1] đến phần tử cuối cùng của mảng T đều bằng hơn P[j].

D. Các phần tử từ T[i] đến phần tử cuối cùng của mảng T đều nhỏ hơn P[j].

B. 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].

Câu 2. Thuật toán nào được sử dụng phổ biến để sắp xếp một mảng trong thời gian O(n log n)?

A. Sắp xếp nổi bọt (bubble sort).

B. Sắp xếp chọn (selection sort).

C Sắp xếp chèn (insertion sort).

D. Sắp xếp trộn (merge sort).

D. Sắp xếp trộn (merge sort).

Câu 3. Trong Python, có thể sử dụng hàm nào để thực hiện sắp xếp trộn (merge sort) hoặc kiểm tra số nghịch thế trong một mảng?

A. sorted().

B. sort().

C. merge_sort().

D. inversion_count().

A. sorted().

Câu 4. Trong bài toán tính số nghịch thế, một cặp phần tử (i, j) được coi là nghịch thế nếu điều kiện nào sau đây đúng?

A. i < j và arr[i] > arr[j].

B. i < j và arr[i] < arr[j].

C. i > j và arr[i] > arr[j].

D. i > j và arr[i] < arr[j].

A. i < j và arr[i] > arr[j].

Câu 5. Thuật toán Merge Sort là một thuật toán sắp xếp ổn định. Điều này có nghĩa là gì?

--------------- Còn tiếp ---------------