看了weipeng1217坛友的整数划分问题帖子，我去网上看了下，有一个ACM题和他类似，不过还详细些我写下来供大家思考。我的建议是大家先做，别去网上抄代码。各抒己码，一起比较。


整数划分问题整数划分是一个经典的问题。希望这道题会对你的组合数学的解题能力有所帮助。

Input

每组输入是两个整数n和k。(1 <= n <= 50, 1 <= k <= n)

Output

对于每组输入，请输出六行。

第一行： 将n划分成若干正整数之和的划分数。
第二行： 将n划分成k个正整数之和的划分数。
第三行： 将n划分成最大数不超过k的划分数。
第四行： 将n划分成若干奇正整数之和的划分数。
第五行： 将n划分成若干不同整数之和的划分数。
第六行： 打印一个空行。

Sample Input
5 2

Sample Output
7
2
3
3
3


Hint:
1、将5划分成若干正整数之和的划分为： 5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1
2、将5划分成2个正整数之和的划分为： 3+2, 4+1
3、将5划分成最大数不超过2的划分为： 1+1+1+1+1, 1+1+1+2, 1+2+2
4、将5划分成若干奇正整数之和的划分为： 5, 1+1+3, 1+1+1+1+1
5、将5划分成若干不同整数之和的划分为： 5, 1+4, 2+3

第一个和第三个都可以用下面方法解决  n为要划分的数 m为可以使用的最大数
f1(n,m) = f1(n-m,m) + f1(n,m-1)  
边界1 ：f1(1,m) = f1(n,1) = f(0,m) = 1   边界2 ：f(n,m) = f(n,n)当m大于n时

剩下的三个都是第一个的特例   刚刚运行了下f1(50,50)结果是204226中划分方法   
先暂时在这个空间中过滤吧  不过估计会超时  我去试下

648631  1402 2012-01-14 16:16:57 Accepted 0.60 s 728 K C++ 1517 B laoyang103

数据果然很小  不会超时  哈尔滨工业大学的OJ http://acm.hit.

#include <stdio.h>
#include <string.h>
int answer[7];
bool foot[50];

int q(int n,int m)
{
    if((n<1)||(m<1) )return 0;
    if(n==1||m==1) return 1;
    if(n<m) return q(n,n);
    if(n==m)return q(n,m-1)+1;
    return q(n,m-1)+q(n-m,m);
}

void dfs2(int n,int k,int depth,int front)
{
    if(depth > k)return ;
    if(0 == n)
    {
        if(depth == k)answer[2]++;
        return ;
    }
    int i;
    for(i = n;i;i--)
    {
        if(i<=front)
        {
            int temp = front;
            front = i;       
            dfs2(n-i,k,depth+1,front);
            front = temp;
        }
    }
}


void dfs4(int n,int k,int front)
{
    if(0 == n)
    {
        answer[4]++;
        return ;
    }
    int i;
    for(i = n;i;i--)
    {
        if((i & 0x01) && i<=front)
        {
            int temp = front;
            front = i;       
            dfs4(n-i,k,front);
            front = temp;
        }
    }
}

void dfs5(int n,int k,int front)
{
    if(0 == n)
    {
        answer[5]++;
        return ;
    }

    int i;
    for(i = n;i;i--)
    {
        if(!foot[i] && i<=front)
        {
            foot[i] = true;
            int temp = front;
            front = i;       
            dfs5(n-i,k,front);
            front = temp;
            foot[i] = false;
        }
    }

}

int main()
{
    int n,k;
    while(EOF != scanf("%d%d",&n,&k))
    {
        memset(answer,0,sizeof(answer));
        memset(foot,0,sizeof(foot));
        dfs2(n,k,0,100);
        dfs4(n,k,100);
        dfs5(n,k,100);

        printf("%d\n",q(n,n));
        printf("%d\n",answer[2]);
        printf("%d\n",q(n,k));
        printf("%d\n",answer[4]);
        printf("%d\n\n",answer[5]);
       
    }
    return 0;
}
        

我也去看看， 能不能 码出来  是否能在第一页那

648656 1402 2012-01-14 19:13:07 Accepted 0.11 s 728 K C++ 1105 B beyondyfang
代码没经任何优化即AC。题的内容不错，但样例比较水。下面就是提交的代码。
不优化的原因是为了更清晰地阐明算法，有兴趣的看明白这些递归关系后，可以改写成动态归划法，速度将显著地提高。

#include<stdio.h>

int f1(int);
int f2(int, int);
int f3(int, int);
int f4(int);
int f4_t(int, int);
int f5(int);

int f1(int n)
{
    return f3(n, n);
}

int f2(int n, int m)
{
    int i, c;
    if(m < 1 || n < m) return 0;
    if(m == 1 || n == m) return 1;
    for(n -= m, c = i = 0; i <= m; c += f2(n, i++));
    return c;
}

int f3(int n, int m)
{
    if(n < 1 || m < 1) return 0;
    if(n == 1 || m == 1) return 1;
    if(n < m) return f3(n, n);
    if(n == m) return f3(n, m - 1) + 1;
    return f3(n, m - 1) + f3(n - m, m);
}

int f4(int n)
{
    return f4_t(n, n + (n & 1) - 1);
}

int f4_t(int n, int m)
{
    if(n < 1 || m < 1) return 0;
    if(n == 1 || m == 1) return 1;
    if(n < m) return f4_t(n, n + (n & 1) - 1);
    if(n == m) return 1 + f4_t(n, n - 2);
    return f4_t(n, m - 2) + f4_t(n - m, m);
}

int f5(int n)
{
    return f4(n);
}

int main()
{
    int n, k;
    while(scanf("%d %d", &n, &k) != EOF)
        printf("%d\n%d\n%d\n%d\n%d\n\n", f1(n), f2(n, k), f3(n, k), f4(n), f5(n));
    return 0;
}

[ 本帖最后由 beyondyf 于 2012-1-14 19:28 编辑 ]

两位版主写的很好（用的是递归法），还有其他的方法，大家可以继续思考。

哈哈，柳暗花明，我那边帖子结了，这里有了。。。
研究下大侠们的代码去。。

谢谢分享

杨大哥的代码果然比我优化的好多了 学习了

原来那个奇数的递归只要保证传进来的参数m是奇数就可以了  后面的m和m-2当然也是奇数

但是想问下为啥第五个和第四个是一样的  求解释

本来我单独做了第五函数，不过在测试中发现所有的测试值都与第四函数的相同，于是删去了原来的第五函数，改用第四函数，结果也AC。
这只是个发现，我也在考虑其中的关系，不过这两天太忙，在置办年货