检查在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