首页 > 代码库 > 自然数和分解
自然数和分解
codevs——2549 自然数和分解
时间限制: 1 s
空间限制: 32000 KB
题目等级 : 白银 Silver
题目描述 Description
把自然数Ｎ分解为若干个自然数之和，输出方案数。
输入描述 Input Description
N,（1≤n≤50）
输出描述 Output Description
方案数
样例输入 Sample Input
5
样例输出 Sample Output
7
数据范围及提示 Data Size & Hint
5 可分为
1 1 1 1 1
1 1 1 2
1 1 3
1 2 2
1 4
2 3
5
代码：
#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>#include<algorithm>#define N 1000using namespace std;int n,ans;void dfs(int x,int y){ if(x==0)//这个时候说明我们已经凑到了n { ans++;//方案数加一 return ; } for(int i=y;i<=n;i++) if(x-i>=0) dfs(x-i,i);//x-i为当前减完后数的大小 i为当前要减的数的大小 }int main(){ scanf("%d",&n); dfs(n,1); printf("%d",ans); return 0;}
据说这个题好像能用dp做，蒟蒻这里就不写了，相信厉害的你会做这道题！
青春就是用拼搏交换了不起！
自然数和分解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。