自然数无序拆分
时间限制: 1 Sec 内存限制: 128 MB
题目描述
美羊羊给喜羊羊和沸羊羊出了一道难题，说谁能先做出来，我就奖励给他我自己做的一样礼物。沸羊羊这下可乐了，于是马上答应立刻做出来，喜羊羊见状，当然也不甘示弱，向沸羊羊发起了挑战。
可是这道题目有一些难度，喜羊羊做了一会儿，见沸羊羊也十分头疼，于是就来请教你。
题目是这样的：
把自然数Ｎ（N<＝100）分解为若干个自然数之和，求出有几种情况。
如N＝5时，有7种情况
5=1+1+1+1+1
5=1+1+1+2
5=1+1+3
5=1+2+2
5=1+4
5=2+3
5=5
怎么样？你要加油帮助喜羊羊哦！
输入
一个自然数N(N<＝100）
输出
无序拆分的种数。
样例输入
复制样例数据
5
样例输出
7
1.递归，超级慢
/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>
typedef long long LL;
using namespace std;
int n;
int dp(int x, int y){ //x表示被分的数，y表示分的值
if(x == 1 || y == 1){//如果x=1，怎么分都是1种，y=1时2只有{1,1,1,...}这一种
return 1;
}else if(x == y){ // 表示被分的数与分的数相同，有两种情况，按分的数分，就{x}一种，第二种就是分比y小的数
return 1 + dp(x, x - 1);
}else if(x < y){// 如果被分的数小于分的数，那种类和分的数同被分的数种数相同
return dp(x, x);
}else if(x > y){//如果被分数大于分的数，那么也有两种情况，第一种情况，就是包含分的数y，并且有可能有多个，所以分的数y不变
return dp(x - y, y) + dp(x, y - 1); //第二种情况就是不包含分的数y，那么从分的数为（y-1）开始分
}
}
int main()
{
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
scanf("%d", &n);
int ans = dp(n, n);
printf("%d\n", ans);
return 0;
}
/**/
2.dp
/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>
typedef long long LL;
using namespace std;
int n;
int dp[105][105];
int main()
{
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
scanf("%d", &n);
for (int i = 1; i <= n; i++){
for (int j = 1; j <= i; j++){
if(i == 1 || j == 1) dp[i][j] = 1;// 这个和递归的情况是一样的
else if(i == j) dp[i][j] = 1 + dp[i][j - 1];// 这个情况也同递归的一样
else if(i - j < j) dp[i][j] = dp[i - j][i - j] + dp[i][j - 1];
//1.j为分的数，i为被分数，如果分完一次j还存在比j大的数，那么应该从那个数(i-j)开始分，而不是j
//2.如果不包含分的数j，那么从(j-1)开始分
else dp[i][j] = dp[i - j][j] + dp[i][j - 1];
//1.如果分完一次不存在比j大的数，那么还从j开始再分
//2.分的数不为j，就从j-1开始分
}
}
printf("%d\n", dp[n][n]);
return 0;
}
/**/ 3.母函数
f(x)=(1+x^1+x^2+x^3....+x^n)*(1+x^2+x^4+...)*.....(1+x^n);
上面的就是母函数。。。应该就是这样
然后首先数为n的被分数，可以由1，2，3，4，......，n组成，就是不知道选1几个，选2几个。。。
这时候我们可以看一下母函数，设选的数字为i，选的次数为k，那么x的指数可以表示为x^(i*k)；
就像f(x)中(1+x^1+x^2+x^3....+x^n)表示1不选，1选一次，1选2次....; (1+x^2+x^4+...)表示2不选，2选1次，选2次。。。
那么我们要求的分解n的种数就是x^n前的系数（很容易想）。
怎么求x^n的系数呢，多项式相乘解决。
/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>
typedef long long LL;
using namespace std;
int n;
int num1[105], num2[105];
int main()
{
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
scanf("%d", &n);
for (int i = 0; i <= n; i++) num1[i] = 1;//开始第一个多项式的系数都为1，指数为i
for (int i = 2; i <= n; i++){//i表示选的数
for (int j = 0; j <= n; j++){//j表示第几项
for (int k = 0; k + j <= n; k += i){//k为x的指数，就是选一次i，2次i。。。
num2[j + k] += num1[j];//用另一个数组存储指数为j+k的x的系数，是与前一个多项式相乘
}
}
memcpy(num1, num2, sizeof(num2));
memset(num2, 0, sizeof(num2));
}
printf("%d\n", num1[n]);
return 0;
}
/**/
京公网安备 11010502036488号