题目描述 一个整数n(n<=100)可以有多种划分,使其分划的一列正整数之和为 n。例如: 输入 一个正整数n 输出 可拆分成的所有不重复等式,一行一个等式,有一定顺序; 最后再输出一行,total=个数 样例输入 6 样例输出 6=1+5 6=1+1+4 6=1+1+1+3 6=1+1+1+1+2 6=1+1+1+1+1+1 6=1+1+2+2 6=1+2+3 6=2+4 6=2+2+2 6=3+3 total=10 c++代码
时间: 2023-10-30 18:08:21 浏览: 260
整数划分问题 将正整数n表示成一系列正整数之和:n=n1+n2+…+nk,其中n1≥n2≥…≥nk≥1,k≥1。
5星 · 资源好评率100%
下面是一个可以解决这个问题的示例代码:
```cpp
#include <iostream>
#include <vector>
using namespace std;
void partition(int n, int sum, vector<int>& nums, vector<vector<int>>& result) {
if (n == 0) {
if (sum == 0) {
result.push_back(nums);
}
return;
}
for (int i = 1; i <= sum; i++) {
nums.push_back(i);
partition(n - 1, sum - i, nums, result);
nums.pop_back();
}
}
int main() {
int n;
cin >> n;
vector<vector<int>> result;
vector<int> nums;
partition(n, n, nums, result);
for (int i = 0; i < result.size(); i++) {
for (int j = 0; j < result[i].size(); j++) {
cout << result[i][j];
if (j != result[i].size() - 1) {
cout << "+";
}
}
cout << endl;
}
cout << "total=" << result.size() << endl;
return 0;
}
```
这段代码使用递归的方式来生成所有可能的划分。函数 `partition` 接受三个参数:`n` 表示剩余要分划的数的个数,`sum` 表示当前剩余要分划的数之和,`nums` 存储当前划分的数字序列,`result` 存储所有划分的结果。
在 `partition` 函数中,首先判断如果 `n` 为 0,则判断 `sum` 是否为 0,如果是,则表示找到了一个划分,将 `nums` 存入 `result` 中。然后使用循环从 1 到 `sum` 遍历可能的划分数,对于每个数,将其加入 `nums` 中,然后递归调用 `partition` 函数继续划分剩下的数。递归结束后,将刚刚加入的数从 `nums` 中弹出,继续尝试下一个划分数。
在主函数中,首先读取输入的整数 `n`。然后创建一个空的二维数组 `result` 和一个空的一维数组 `nums`。调用 `partition` 函数生成所有划分,并将结果存入 `result` 中。最后使用两层循环遍历 `result`,输出每个划分,并在每个数字之间添加 "+" 符号。最后输出划分的总数。
希望这个示例代码能对您有所帮助!如果您有任何其他问题,请随时提问。
阅读全文