資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告