分治与递归-整数划分

基本整数划分

基本整数划分问题是将一个正整数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);
}