基本整数划分问题是将一个正整数n拆成一组数连加并等于n的形式，且这组数中的最大加数不大于m。
即n=n1+n2+n3+……（其中，n1>=n2>=n3>=n4……）
对于这种问题，可以建立一下递归关系：
（1）q（n,1）=1,n>=1;
当最大加数m不大于1时，任何正整数n只有一种划分，即n=1+1+1+1+1……
（2）q(n,m)=q(n,n),m>=n;
因为，显然最大加数不能大于n……，囧
（3）q(n,n)=q(n,n-1)+1;
正整数n的划分由n=n和m<=n-1的划分组成
(即如果划分中最大加数是n，则这种划分为n=n，剩下的划分最大加数为n-1)
（4）q(n,m)=q(n,m-1)+q(n-m,m);
同上，正整数n的划分由m=m和m<=m-1的划分组成(即如果划分中最大加数是m，
则这种划分为n-m（将划分中的一个必然存在的m减去）的最大加数为m的划分，
剩下的为最大加数为m-1的划分)
由此可设计递归函数如下（C++）
#include <stdio.h>
int numdipart(int n,int m)
//求对于正整数n，其最大加数不大于m的划分个数,算法效
//率低（递归），当n超过80时，
//运算时间超过一秒，对于m==n的问题建议打表
{
if(n<1 || m<1) return 0;
if(n==1 || m==1) return 1;
if(n<m) return numdipart(n,n);
if(n==m) return numdipart(n,m-1)+1;
return numdipart(n,m-1)+numdipart(n-m,m);
}
由于递归算法效率很低，同时由于整数划分的整数级增长速度，故对于一般问题，完全可以通过DP打表来解决，程序如下：
Long long dap[1001][1001];
//注意为long long类型，注意输出，之所以用long long
//类型是因为当n大于300时，dap[n][n]便超出了int的范围
void dpdipart()
{
int i,j;
for(i=1;i<1001;++i)
for(j=1;j<1001;++j)
{
if(i<1 || j<1) dap[i][j]=0;
else if(i==1 || j==1) dap[i][j]=1;
else if(i<j) dap[i][j]=dap[i][i];
else if(i==j) dap[i][j]=dap[i][j-1]+1;
else dap[i][j]=dap[i][j-1]+dap[i-j][j];
}
}
如15可以划分成4种连续整数相加的形式：
15
7 8
4 5 6
1 2 3 4 5
首先考虑一般的形式，设n为被划分的正整数，x为划分后最小的整数，如果n有一种划分，那么
结果就是x,如果有两种划分，就是x和x x + 1， 如果有m种划分，就是 x 、x x + 1 、 x x + 1 x + 2 、... 、x x + 1 x + 2 ... x + m - 1
将每一个结果相加得到一个公式(i * x + i * (i - 1) / 2) = n，i为当前划分后相加的正整数个数。
满足条件的划分就是使x为正整数的所有情况。
如上例，当i = 1时，即划分成一个正整数时，x = 15， 当i = 2时， x = 7。
当i = 3时，x = 4， 当i = 4时，9/4，不是正整数，因此，15不可能划分成4个正整数相加。
当i = 5时，x = 1。
这里还有一个问题，这个i的最大值是多少？不过有一点可以肯定，它一定比n小。我们可以做一个假设，
假设n可以拆成最小值为1的划分，如上例中的1 2 3 4 5。这是n的最大数目的划分。如果不满足这个假设，那么 i 一定比这个划分中的正整数个数小。因此可以得到这样一个公式i * (i + 1) / 2 <= n，即当i满足这个公式时n才可能被划分。
综上所诉，可得程序如下：
int split(int n)
//此程序用m记录划分种数并返回m值，并且在函数体内输出了各种划分
//种类，n在int范围内皆可处理，处理时间小于1秒
{
int i, j, m = 0, x, t;
for(i = 1;(i*(i+1)/2)<=n; i++)
{
t = n - i*(i-1)/2;
x = t / i;
if(x <= 0) break;
if(t % i == 0)
{
printf("%d ", x);
for(j = 1; j < i; j++)
printf("%d ", x + j);
printf("\n");
m++;
}
}
return m;
}
递归搜索每一个可能的因子，当搜索到底部（为1时），因子分解方式加1，此时也可进行输出
void solve(int n)
{
int i;
if(n==1) sum++;
else
for(i=2;i<=n;++i)
if(n%i==0)
solve(n/i);
}