Bài toán: Tìm các vị trí i (nếu có) chia dãy số thành 2 phần có tổng bằng nhau. Nếu không có ghi ra -1. Ví dụ: n = 6; 1 3 4 2 7 3 → i = 4 (giải thích: 1+3+4+2=7+3)
Để tìm các vị trí i mà chia dãy số thành hai phần có tổng bằng nhau, ta có thể sử dụng thuật toán tương đối đơn giản. Dưới đây là một cách tiếp cận để giải bài toán này:
- Tính tổng của toàn bộ dãy số và lưu vào biến sum.
- Khởi tạo biến left_sum ban đầu bằng 0.
- Duyệt qua từng phần tử trong dãy số bắt đầu từ vị trí đầu tiên.
- Tại mỗi vị trí, cộng giá trị của phần tử đó vào left_sum.
- So sánh left_sum với tổng sum/2. Nếu left_sum bằng tổng sum/2, thì vị trí hiện tại chia dãy số thành hai phần có tổng bằng nhau.
- Nếu left_sum vượt quá tổng sum/2, dừng vòng lặp vì không có cách chia dãy số thỏa mãn yêu cầu.
- Nếu tại bước trên, không tìm thấy vị trí i nào thỏa mãn yêu cầu, ghi ra -1.
Dưới đây là một đoạn mã Python thực hiện thuật toán trên:
def find_equal_sum_partition(n, arr):
total_sum = sum(arr)
left_sum = 0
for i in range(n):
left_sum += arr[i]
if left_sum == total_sum / 2:
return i + 1
if left_sum > total_sum / 2:
return -1
return -1
# Ví dụ
n = 6
arr = [1, 3, 4, 2, 7, 3]
result = find_equal_sum_partition(n, arr)
print(result)
Một thuật toán khác để giải bài toán chia dãy số thành hai phần có tổng bằng nhau là thuật toán “cân bằng” (balance algorithm). Ý tưởng chính của thuật toán này là sử dụng một biến tổng cục bộ (local sum) để duyệt qua dãy số, và kiểm tra tại mỗi vị trí xem có tồn tại một vị trí i trước đó sao cho tổng từ đầu đến vị trí i bằng với tổng từ vị trí i+1 đến vị trí x.
Dưới đây là cách triển khai thuật toán “cân bằng” trong Python:
def find_equal_sum_partition(n, arr):
total_sum = sum(arr)
local_sum = 0
for i in range(n - 1):
local_sum += arr[i]
if local_sum == total_sum - local_sum:
return i + 1
return -1
# Ví dụ
n = 6
arr = [1, 3, 4, 2, 7, 3]
result = find_equal_sum_partition(n, arr)
print(result)