蓝桥杯算法提高 自然数拆分 C++实现
·
资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
HJQ同学发现了一道数学题，要求n拆分成若干自然数和的方案
输入格式
输入n
输出格式
输出n拆分成若干自然数和的方案，每个方案一行
数据规模和约定
n <= 10
注意：自然数是包括零的，但是这里我们不把0算进去
#include<iostream>
using namespace std;
int N;
int visit[10000] = { 1 };
void display(int x) {
for (int i = 1; i < x; i++) {
cout << visit[i] << "+";
}
cout << visit[x] << endl;
}
void dfs(int n,int x) {
for (int i = visit[x - 1]; i <= n; i++) { //从1开始拆分，一直到n
if (i < N) { //不能拆分为N=N；
visit[x] = i; //-当前拆分的数i
n -= i; //减去已拆分的数，继续拆分
if (n == 0) //拆分结束，输出
display(x);
else
dfs(n, x + 1);
n += i; //回溯，加上已拆分的数
}
}
}
int main() {
cin >> N;
dfs(N,1);
return 0;
}
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
1
0- 0
已为社区贡献1条内容
所有评论(0)