2117: 数的划分
Time Limit:
1 Sec
Memory Limit:
128 MB
Submit:
69
Solved:
28
[
Submit
][
Status
][
Web Board
]
Description
一个正整数可以划分为多个正整数的和，比如n=3时：
3；1＋2；1＋1＋1；
共有三种划分方法。
给出一个正整数，问有多少种划分方法。
Input
一个正整数n，n<=100
Output
一个正整数，表示划分方案数
Sample Input
3
Sample Output
3
f[n][m]=f[n-1][m-1]+f[n-j][m];//f[n][m]表示将大小为n的数划分为m个；
两种情况：a、m个数中至少有一个1;b、m个数中没有一个1，就可以先从n中取出m个1均分给m个数，使m个数至少为1，再将剩余的n-m均分个m个数,若不够分，则f[n-j][m]=0;
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int f[105][105];
int main()
{
int n;
while(~scanf("%d",&n))
{
memset(f,0,sizeof(f));
int i;
int j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(i==j)f[i][j]=1;
else if(j==1)f[i][j]=1;
else if(i>j)
{
f[i][j]=f[i-1][j-1]+f[i-j][j];//f[n][m]表示将大小为n的数划分为m个；两种情况：a:m个数中至少有一个1;b:m个数中没有一，就可以先将i均分给j个数，使j个数至少为1，再将剩余的i-j均分个j个数
}
}
}
int sum=0;
for(i=1;i<=n;i++)
sum+=f[n][i];
printf("%d\n",sum);
}
return 0;
}
版权声明：本文为qq_37378303原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。