Ở đây chúng ta sẽ thấy một chương trình có thể kiểm tra xem một số có thể được chia thành nhiều hơn một đoạn với tổng bằng nhau hay không. Giả sử một số giống như 74325, thì số này có thể được phân đoạn thành ba phần (7), (4, 3), (2, 5), tất cả đều có cùng giá trị um.
Chúng tôi phải làm theo các bước sau để giải quyết vấn đề này.
- Lấy số dưới dạng chuỗi
- sử dụng một mảng để giữ tổng tiền tố của mảng
- Hiện đang chuyển từ phần tử thứ hai sang phần tử cuối cùng và phân đoạn đầu tiên sẽ là 0 đến i-1, có tổng sẽ được đặt ở prefix_sum [i - 1]
- Sử dụng một biến khác chuyển từ 1 đến n, sau đó tiếp tục cộng tổng.
- Nếu giá trị tổng giống với prefix_sum [i - 1] ở bất kỳ giai đoạn nào, thì phân đoạn có tổng bằng giá trị đầu tiên.
- Khởi tạo lại giá trị tổng của phân đoạn bằng 0, sau đó tiếp tục di chuyển con trỏ.
- Nếu ở bất kỳ giai đoạn nào, tổng phân đoạn lớn hơn prefix_sum [i - 1] thì ngắt vòng lặp
- Nếu chúng tôi đến điểm đến cuối cùng và nếu tổng phân đoạn cuối cùng bằng với tổng phân đoạn đầu tiên, thì nó có thể được chia thành các phân đoạn có tổng bằng nhau.
Ví dụ
#include <iostream>
using namespace std;
bool canBeSegmented(string str) {
int n = str.length();
int prefix_sum[n];
prefix_sum[0] = str[0] - '0';
for (int i = 1; i < n; i++) {
prefix_sum[i] = prefix_sum[i - 1] + (str[i] - '0');
}
for (int i = 1; i <= n - 1; i++) {
int sum = prefix_sum[i - 1];
int prev_sum = 0;
int it = i;
bool flag = false;
while (it < n) {
prev_sum += str[it] - '0';
if (prev_sum == sum) {
prev_sum = 0;
flag = true;
} else if (prev_sum > sum) {
break;
}
it++;
}
if (prev_sum == 0 && it == n && flag) {
return true;
}
}
return false;
}
int main() {
string s = "74325";
if (canBeSegmented(s))
cout << "Yes, This can be segmented into more than two segments";
else
cout << "No, This can not be segmented into more than two segments";
} Đầu ra
Yes, This can be segmented into more than two segments