C++将一个正整数分解成若干个正整数相加

可以使用递归的方法来实现将一个正整数分解成若干个正整数相加的功能。具体实现如下：

#include <iostream>
using namespace std;

void decompose(int n, int max_num, string s) {
    if (n == 0) {
        cout << s << endl;
        return;
    }
    for (int i = 1; i <= max_num && i <= n; i++) {
        decompose(n - i, i, s + to_string(i) + " ");
    }
}

int main() {
    int n;
    cout << "请输入一个正整数：";
    cin >> n;
    decompose(n, n, "");
    return 0;
}

输入一个正整数后，程序会输出所有将该正整数分解成若干个正整数相加的方案。

例如，输入 5，程序会输出：

1 1 1 1 1 
2 1 1 1 
2 2 1 
3 1 1 
3 2 
4 1 
5 

相关问题

整数分解（将一个正整数分解成若干个正整数之和） c加加

整数分解，也叫因式分解，是指将一个给定的正整数表示为其他较小正整数相加的形式。在C++编程中，可以使用循环和条件判断来实现这个过程。例如，对于一个数n，我们可以从最小的质数2开始尝试除法，如果n能被2整除，就一直除到n不再是偶数，然后继续尝试下一个质数，直到n变成1或者找到所有因子为止。

这是一个简单的C++函数示例，用于分解一个整数：

#include <iostream>
#include <vector>

std::vector<int> primeFactors(int n) {
    std::vector<int> factors;
    while (n % 2 == 0) {
        factors.push_back(2);
        n = n / 2;
    }
    for (int i = 3; i * i <= n; i += 2) { // 只检查奇数质数
        while (n % i == 0) {
            factors.push_back(i);
            n = n / i;
        }
    }
    if (n > 2) {
        factors.push_back(n); // 如果n是大于2的质数，直接添加
    }
    return factors;
}

int main() {
    int num;
    std::cout << "Enter a positive integer: ";
    std::cin >> num;
    std::vector<int> factorList = primeFactors(num);
    std::cout << "Prime factors of " << num << " are: ";
    for (const auto& factor : factorList) {
        std::cout << factor << " ";
    }
    return 0;
}

7-37 整数分解为若干项之和 分数 20 作者 DS课程组 单位 浙江大学 将一个正整数N分解成几个正整数相加，可以有多种分解方法，例如7=6+1，7=5+2，7=5+1+1，…。编程求出正整数N的...

题目描述

将一个正整数 N 分解成若干个正整数之和，输出所有的分解方式。

输入格式

一个正整数 N。

输出格式

每行输出一种分解方式，每种分解方式按照从大到小的顺序输出。

样例输入

7

样例输出

7
6 1
5 2
5 1 1
4 3
4 2 1
4 1 1 1
3 2 2
3 2 1 1
3 1 1 1 1
2 2 2 1
2 2 1 1 1
2 1 1 1 1 1
1 1 1 1 1 1 1

算法1

(回溯算法) $O(n!)$

首先我们可以发现，所有的分解方式的第一个数都不会小于 $\lfloor \frac{N}{2} \rfloor$，因为如果第一个数小于 $\lfloor \frac{N}{2} \rfloor$，那么第二个数至少为 $\lfloor \frac{N}{2} \rfloor$，那么第一个数和第二个数的和就已经大于等于 N 了，不符合要求。

接着，我们可以借助回溯算法来求解。具体方法是，首先设当前的数字为 N，从 $\lfloor \frac{N}{2} \rfloor$ 开始依次枚举第一个数 num，然后递归处理剩下的数字 $N-num$，直到 N 为 0，表示已经找到了一种分解方法。注意，我们为了避免重复，下一次递归的起始数字应该为上一次递归的数字，即从 num 开始枚举。

时间复杂度

最坏情况下，如果 N 为质数，那么分解方式的数量为 $(2^{N-1}-1)$，时间复杂度为 $O((2^{N-1}-1) \times N)$。但实际上，分解方式的数量不会超过 $2^N$，因此时间复杂度可以近似看作 $O(2^N \times N)$。

C++ 代码

class Solution {
public:
void dfs(int n, int start, vector<int>& path, vector<vector<int>>& res) {
if (n == 0) {
res.push_back(path);
return;
}
for (int i = start; i <= n; i++) {
path.push_back(i);
dfs(n - i, i, path, res);
path.pop_back();
}
}

vector<vector<int>> getFactors(int n) {
vector<vector<int>> res;
vector<int> path;
dfs(n, 2, path, res);
return res;
}
};

算法2

(暴力枚举) $O(n^2)$

我们可以将分解出来的数字存储在数组中，每次从数组的最后一位开始减去 1，直到当前的数字为 0，表示找到了一种分解方式。不断枚举数字的过程可以通过两层循环实现。

时间复杂度

最坏情况下，如果 N 为质数，那么分解方式的数量为 $(2^{N-1}-1)$，时间复杂度为 $O((2^{N-1}-1) \times N^2)$。但实际上，分解方式的数量不会超过 $2^N$，因此时间复杂度可以近似看作 $O(2^N \times N^2)$。

C++ 代码

class Solution {
public:
vector<vector<int>> getFactors(int n) {
vector<vector<int>> res;
vector<int> path(n, 1);
while (path[0] <= n / 2) {
int sum = accumulate(path.begin(), path.end(), 0);
if (sum == n) res.push_back(path);

int i = n - 1;
while (i >= 0 && path[i] == 1) i--;
if (i < 0) break;

int j = i;
while (j >= 0 && path[j] == path[i]) j--;
path[j]++;
for (int k = j + 1; k <= i; k++) path[k] = path[j];
}
return res;
}
};