Cho một dãy số bất kì A[0], A[1]..., A[n – 1]. Một tổng con được định nghĩa

Mai Hương Ngày: 20-11-2023 Lớp 11

218

Với giải Vận dụng 2 trang 47 Chuyên đề Tin học 11 Kết nối tri thức chi tiết trong Bài 10: Thực hành giải toán bằng kĩ thuật chia để trị giúp học sinh dễ dàng xem và so sánh lời giải, từ đó biết cách làm bài tập Chuyên đề Tin học 11. Mời các bạn đón xem:

Cho một dãy số bất kì A[0], A[1]..., A[n – 1]. Một tổng con được định nghĩa

Vận dụng 2 trang 47 Chuyên đề Tin học 11: Cho một dãy số bất kì A[0], A[1]..., A[n – 1]. Một tổng con được định nghĩa là tổng của một dãy con liên tục dạng . Bài toán yêu cầu tìm và chỉ ra một tổng con và dãy con tương ứng có giá trị lớn nhất. Yêu cầu sử dụng kĩ thuật chia để trị.

Lời giải:

Em có thể áp dụng kỹ thuật chia để trị như sau:

1. Chia dãy số ban đầu thành hai dãy con bằng cách chia nó ở giữa.

2. Giải quyết hai dãy con bằng cách đệ quy áp dụng cùng thuật toán.

3. Tìm tổng con lớn nhất chứa phần tử ở giữa của dãy số ban đầu. Ta thực hiện điều này bằng cách tính tổng của phần tử đó cùng các phần tử liền trước và liền sau nó, rồi lưu lại tổng lớn nhất tìm được.

4. Tìm tổng con lớn nhất nằm hoàn toàn trong một trong hai dãy con đã giải quyết ở bước 5. Ta thực hiện điều này bằng cách đệ quy áp dụng lại thuật toán trên hai dãy con đó.

6. Tìm tổng con lớn nhất giữa phần tử ở giữa dãy con trái và phần tử ở giữa dãy con phải. Ta thực hiện điều này bằng cách tính tổng của phần tử giữa dãy con trái và phần tử giữa dãy con phải, rồi lưu lại tổng lớn nhất tìm được.

Cho một dãy số bất kì A[0], A[1]..., A[n – 1]