1、整数划分问题是将一个正整数n拆成一组数连加并等于n的形式，且这组数中的最大加数不大于n。求划分的个数是基本要求：
//sprit()算法的作用求出它的个数，算法思想是：q(n,m)代表的是最大加数是m的划分的个数
/**
1、m==1||n==1 q(n,m)=1;
2、m>n q(n,m)=q(n,n)
3 m==n q(n,m)=q(n,m-1)+1;
4 m<n q(n,m)=q(n,m-1)+q(n-m,m)
**/
int sprit(int n,int m)
{
if(n==1||m==1)
return 1;
if(m>n)
return sprit(n,n);
if(m==n)
return sprit(n,m-1)+1;
if(m<n)
return sprit(n,m-1)+sprit(n-m,m);
return 0;
}
2、如果对时间复杂性要求高时，可以将其转换为非递归的形式，过程很简单
#define N 20
int ans[N][N];
void sprit_1()
{
int i,j;
for(i=1;i<N;i++)
for(j=1;j<=i;j++)
{
if(i==1||j==1)
ans[i][j]=1;
else if(i==j)
ans[i][j]=ans[i][j-1]+1;
else
{
int k=(i-j>=j?j:i-j);
ans[i][j]=ans[i][j-1]+ans[i-j][k];
}
}
}
3、/**将正整数划分成连续的正整数之和
如15可以划分成4种连续整数相加的形式：
15
7 8
4 5 6
1 2 3 4 5
划分思想是：设最小的数为x，划分个数为i，有x*i+i(i-1)/2=n,直接列举i即可
**/
void sprit_2(int n)
{
int i,j,t1,t2,x;
for(i=1;(t1=i*(i-1)/2)<n;i++)
{
t2=n-t1;
if(t2<0)return;
x=t2/i;
if((n-t1)%i==0)
{
for(j=0;j<i;j++)
cout<<x+j<<" ";
cout<<endl;
}
}
}
4、如果想把它的各种拆分也求出来，思想是用数组a保存结果，每次对指针t指向的数据进行拆分即可。
int a[N];
void f(int t)
{
int i,j,m;
for(i=0;i<=t;i++)
cout<<a[i]<<" ";
cout<<endl;
j=t;m=a[j];
for(i=a[j-1];i<=m/2;i++)
{
a[j]=i;a[j+1]=m-i;
f(j+1);
}
}
void sprit_3(int n)
{
for(int i=1;i<=n/2;i++)
{
a[0]=i;a[1]=n-i;
f(1);
}
}