检查在C ++中是否可以将大数分为相等总和的两个或多个段
在这里，我们将看到一个程序，该程序可以检查一个数字是否可以分为多个相等相等的段。假设一个数字为74325，则可以将其分为三部分(7)，（4、3），（2、5），所有部分的um值相同。
我们必须按照以下步骤解决此问题。
以数字为字符串
使用数组保存数组的前缀和
现在从第二个元素遍历到最后一个元素，并且第一段将从0到i-1，其总和将位于prefix_sum[i-1]
使用另一个从1遍历到n遍历的变量，然后继续将总和相加。
如果在任何阶段，总和值都与prefix_sum[i–1]相同，则该段的总和等于第一个。
将段总和值重新初始化为0，然后继续移动指针。
如果在任何阶段分段总和大于prefix_sum[i–1]，则中断循环
如果我们到达最后一个目的地，并且如果最后一个分段总和与第一个分段总和相同，则可以将其划分为相等总和的分段。
示例
#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";
}输出结果
Yes, This can be segmented into more than two segments