ACM 训练日志记录 · 思考 · 成长 提交 / 修改记录
廖夏 / 题目列表训练档案
导出

P2404 自然数的拆分问题

来源:洛谷 ★ 1000

搜索仍在学习待复习
本题活力0.22按难度、完成结果与训练证据估算

算法如山行则将至

题目描述

自然数的拆分问题

题目描述

任何一个大于 $1$ 的自然数 $n$,总可以拆分成若干个小于 $n$ 的自然数之和。现在给你一个自然数 $n$,要求你求出 $n$ 的拆分成一些数字的和。每个拆分后的序列中的数字从小到大排序。然后你需要输出这些序列,其中字典序小的序列需要优先输出。

输入格式

输入:待拆分的自然数 $n$。

输出格式

输出:若干数的加法式子。

说明/提示

数据保证,$2\leq n\le 8$。

样例 1

输入:

7

输出:

1+1+1+1+1+1+1
1+1+1+1+1+2
1+1+1+1+3
1+1+1+2+2
1+1+1+4
1+1+2+3
1+1+5
1+2+2+2
1+2+4
1+3+3
1+6
2+2+3
2+5
3+4

代码

#include<iostream>
#include<algorithm>
using namespace std;
int n;
int a[100] = {1};
void print(int t){
	for (int i = 1; i < t; i++) cout << a[i] << "+";
	cout << a[t] << endl;
}
void dfs(int x, int t){
	for (int i = a[t - 1]; i < x; i++){
		if (i >= n) continue;
		a[t] = i;
		dfs(x-i, t+1);
	}
	a[t] = x;
	if (x >= a[t-1] && x < n) print(t);
}
int main(){
	cin >> n;
	dfs(n, 1);
	return 0;
}

// 下面的GPT提示的偏现代思路

#include<iostream>
#include<vector>
using namespace std;
vector<int> a; // 外置状态存储
int n;
void print(){
	for (int i = 0; i < a.size()-1; i++) 
		cout << a[i] << "+";
	cout << a[a.size()-1] << endl;
}
void dfs(int remain, int low){ // 携带的状态信息:影响下一步决策的信息

	if (!remain && a.size() >= 2) {print(); return;}  // 终止条件
	for (int i = low; i <= remain; i++){ // 尝试每种可能
		a.push_back(i);
		dfs(remain - i, i);
		a.pop_back();
	}
}
int main(){
	cin >> n;
	dfs(n, 1);
	return 0;
}