自然数无序拆分(三种方法)

自然数无序拆分

时间限制: 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;
}
/**/