1问题的描述：
把一个正整数n表示为一系列正整数之和：
n=n1+n2+..+nk (其中，n1n2 … nk 1,k 1)
正整数n的这种表示称为正整数n的划分。正整数n的不同划分个数称为正整数n的划分个数，记作P(n).
例如正整数6有如下划分
6
5+1
4+2, 4+1+1
3+3， 3+2+1， 3+1+1+1
2+2+2， 2+2+1+1， 2+1+1+1+1
1+1+1+1+1+1
所以P(n)=11
请输入一个正整数，求P(n).
2问题的分析：
如果｛n1,n2,n3,…nl｝中的最大加数s不超过m，即s=max(n1,n2,n3,…nl) m,则称它属于n的一个m划分。我们记n的m划分的个数为f(n,m),该问题就转化为求n的所有划分个数f(n,n).我们可以建立如下的f(n,m)的递归关系：
1、 f(1,m)=1, m 1
当n=1时，不论m的值为多少（m>0）,只有一种划分即1个1
2、 f(n,1)=1, n 1
当m=1时，不论n的值为多少（n>0），只有一种划分即n个1
3、 f(n,m)=f(n,n), m
4、 f(n,n)=1+f(n,n-1)
5、 f(n,m)=f(n,m-1)+f(n-m,m), n>m>1
整数n的最大加数s不大于m的划分是由s=m的划分和s m-1的划分组成。
n>m时，根据划分中是否包含最大值m，可以分为两种情况：
(a)划分中包含m的情况，即{m, {x1,x2,...xi}}, 其中{x1,x2,... xi} 的和为n-m，因此这情况下为f(n-m,m)（就是把{x1,x2…xi}进行划分，其中最大加数s小于等于m，结果就为f(n-m,m)）
(b)划分中不包含m的情况，则划分中所有值都比m小，即n的(m-1)划分，个数为f(n,m-1)
3公式的递推：
整数n的划分数P(n)=f(n,n)
1 n=1,m=1
f(n,n) n
f(n,m)= 1+f(n,n-1) n=m
f(n,m-1)+f(n-m,m) n>m>1
4代码的编写：
#include<iostream>
#include<string>
using namespace std;
int fun(int n, int m)
{
if(n == 1 || m == 1) return 1;
else if(n < m) return fun(n, n);
else if(n == m) return (1 + fun(n, m - 1));
else return (fun(n, m - 1) + fun(n - m, m));
}
int main(void)
{
int n;
scanf("%d", &n);
printf("%d\n", fun(n, n));
return 0;
}
5 程序的运行
运行的结果与实际计算的结果完全一致。
6 代码的改进及运行的结果
#include<iostream>
#include<string>
using namespace std;
int fun(int n, int m)
{
if(n == 1 || m == 1) return 1;
else if(n < m) return fun(n, n);
else if(n == m) return (1 + fun(n, m - 1));
else return (fun(n, m - 1) + fun(n - m, m));
}
//输出划分结果
void divide(char *s,int a,int b)
{
int i;
static char t[500];//保存上一次的输出结果
char temp[500],str[3]={0};
if(b==0){
if(s[0]==t[0])
printf(",%s",s);
else
printf("%s",s);
strcpy(t,s);
}
for(i=b;i>=1;i--){
if(i>a)
continue;
strcpy(temp,s);
str[0]=‘+‘;
str[1]=i+‘0‘;
strcat(s,str);
divide(s,i,b-i);
strcpy(s,temp);
}
}
int main(void)
{
int i;
int n;
char s[500]={0};
char str[3]={0};
scanf("%d",&n);
printf("划分种数：%d\n",fun(n,n));
for(i=n;i>=1;i--){
if(i==n)
printf("%d",n);
else{
s[0]=0;
str[0]=‘0‘+i;
strcat(s,str);
divide(s,i,n-i);
}
puts("");
}
}
程序运行的结果给出了划分的个数和划分的结果，达到了实验的预期目标。
7 实验总结
先根据问题给出推导式，在分析n>m>1时，有关系式 f(n,m)=f(n,m-1)+f(n-m,m).对于这个关系式当时想大半天，不理解包含m的划分时为啥是f(n-m,m),在上网查阅资料也没能明白时，又仔细琢磨了下，才恍然大悟，原来是很简单的问题。在包含数m的m划分，可写成{m, {x1,x2,...xi}}, 其中{x1,x2,... xi} 的和为n-m，就是求剩余的(n-m)这个数的m划分，故为f(n-m,m).
写完关系式后，编写代码就是很简单的事情了。在求出划分数的基础上又对代码进行了改进，输出了划分的结果，达到了实验的目的。希望我的这篇博客对大家有所帮助。
原文：http://www.cnblogs.com/clp4310/p/5829467.html