A27172. 自然数的拆分
填空题
困难
知识点
题目描述
自然数的拆分
题目描述
任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。
当n=7共14种拆分方法：
7=1+1+1+1+1+1+1
7=1+1+1+1+1+2
7=1+1+1+1+3
7=1+1+1+2+2
7=1+1+1+4
7=1+1+2+3
7=1+1+5
7=1+2+2+2
7=1+2+4
7=1+3+3
7=1+6
7=2+2+3
7=2+5
7=3+4
total=14输入
输入n。
输出
按字典序输出具体的方案。
输入样例
7输出样例
7=1+1+1+1+1+1+1
7=1+1+1+1+1+2
7=1+1+1+1+3
7=1+1+1+2+2
7=1+1+1+4
7=1+1+2+3
7=1+1+5
7=1+2+2+2
7=1+2+4
7=1+3+3
7=1+6
7=2+2+3
7=2+5
7=3+4参考答案
#include<bits/stdc++.h>
using namespace std;
int n, a[10001], ai;//数组a记录每次拆分出的数字
void dfs(int m, int st)//还剩下数字m需要拆分，拆分出的数字要大于等于st
{
if(m == 0)
{
cout << n << "=" << a[1];
for(int i = 2; i <= ai; ++i)
cout << '+' << a[i];
cout << endl;
return;
}
for(int i = st; i <= m && i < n; ++i)//不可以拆分出数字n，排除n=n的情况。
{//拆分出一个数字i
a[++ai] = i;
dfs(m - i, i);//这次拆分出数字i，下一次要拆分数字m-i，拆分出的数字最小为i
ai--;//状态还原
}
}
int main()
{
cin >> n;
dfs(n, 1);//从数字n中拆分数字，拆出的最小数字为1
return 0;
}答案解析
//方法二
#include<bits/stdc++.h>
using namespace std;
int n, a[10001], ai;//数组a记录每次拆分出的数字
void dfs(int m, int st)//还剩下数字m需要拆分，拆分出的数字要大于等于st
{
if(m == 0)
{
cout << a[1];
for(int i = 2; i <= ai; ++i)
cout << '+' << a[i];
cout << endl;
return;
}
for(int i = st; i <= m && i < n; ++i)//不可以拆分出数字n，排除n=n的情况。
{//拆分出一个数字i
a[++ai] = i;
dfs(m - i, i);//这次拆分出数字i，下一次要拆分数字m-i，拆分出的数字最小为i
ai--;//状态还原
}
}
int main()
{
cin >> n;
dfs(n, 1);//从数字n中拆分数字，拆出的最小数字为1
return 0;
}
上一题
下一题