Câu hỏi
Cho n chuỗi, tìm cách cộng các chuỗi này lại theo một thứ tự nào đó sao cho ít tốn bộ nhớ nhất.
Ví dụ: Cho chuỗi A=abc, B=wxyz, C=g, và xét hai cách cộng chuỗi sau:
- Cộng A và B trước, sau đó cộng với C. A + B sẽ tốn 3 + 4 = 7. Sau đó cộng thêm C sẽ tốn 7 + 1 = 8. Tổng cộng tốn 7 + 8 = 15.
- Cộng A và C trước, sau đó cộng với B. A + C tốn 3 + 1 = 4. Sau đó cộng thêm B sẽ tốn 4 + 4 = 8. Tổng cộng tốn 4 + 8 = 12.
Cách cộng chuỗi thứ 2 đỡ tốn bộ nhớ hơn cách thứ 1, và cũng là cách tốn ít bộ nhớ nhất.
Phân tích
Việc cộng n chuỗi với nhau luôn luôn tốn n-1 phép cộng chuỗi, và tạo ra chuỗi cuối cùng với độ lớn không đổi. Do đó, lý do tốn bộ nhớ không phải là vì kết quả cuối cùng, mà là do các mảng nhớ tạm ta phải sử dụng để chứa kết quả của các phép cộng chuỗi này.
Xét ba chuỗi bất kỳ với độ lớn x <= y <= z. Ta cần thực hiện 2 phép cộng chuỗi, và độ lớn của chuỗi cuối cùng sẽ là tổng của x + y + z không đổi. Độ lớn của chuỗi tạm sẽ là tổng này trừ đi độ lớn của chuỗi gốc trong phép cộng chuỗi thứ 2. Dễ thấy rằng nếu ta để dành chuỗi có độ lớn z để cộng cuối cùng, thì độ lớn của chuỗi tạm sẽ là nhỏ nhất, x + y.
Do đó, ta sẽ để dành chuỗi có chiều dài lớn nhất cho các phép cộng sau cùng, chuỗi có độ dài lớn thứ hai cho phép cộng kế cuối... Vì vậy, cách giải bài toán này chỉ đơn giản là sắp xếp các chuỗi đã cho theo thứ tự tăng dần về độ lớn chuỗi.
Phần cài đặt xin được để dành làm một thử thách nhỏ cho bạn đọc. Diễn đàn là nơi phù hợp để trao đổi thêm về những vấn đề tương tự.