用 C++ 检查一个大数是否可以分成两个或多个和相等的段

在这里，我们将看到一个程序，它可以检查一个数字是否可以分成多个和相等的段。假设一个数字是 74325，那么它可以分成三个部分：(7)，(4, 3)，(2, 5)，它们都具有相同的和。

我们必须遵循以下步骤来解决这个问题。

  • 将数字作为字符串
  • 使用数组保存数组的前缀和
  • 现在从第二个元素遍历到最后一个元素，第一个段将是 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

更新于：2019年10月22日

96 次浏览

启动您的职业生涯

通过完成课程获得认证

开始
广告