数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法学研究用 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 次浏览
广告