一道组合数学题求大神讲
  • 浏览:645 评论:10 人

  • 这题等价于求一个正整数n如何分解为m个正整数。这我高中的时候考虑过,很难找到通项公式。我当年写过这题的程序,可以用三维动态规划的方式解决,也就是找到一个递推式,非常难。




    代码写完了,用C写的,想了我老半天。
    以下是源程序(n,m<50):
    #include <stdio.h>
    int main()
    {
    long n,m,i,j,k,l,f[50][50][50],s;
    printf("n=");
    scanf("%d",&n);
    printf("m=");
    scanf("%d",&m);
    for (i=0;i<=n;i++)
    for (j=0;j<=m;j++)
    for (k=0;k<=n;k++)
    f[j][k]=0;
    f[1][1][1]=1;
    for (i=2;i<=n;i++)
    {
    f[1]=1;
    for (j=2;j<=m;j++)
    for (k=1;k<=i-1;k++)
    for (l=1;l<=k;l++)
    if (i-k>=l)
    f[j][i-k]=f[j][i-k]+f[k][j-1][l];
    }
    s=0;
    for (i=1;i<=n;i++)
    s=s+f[n][m];
    printf("%ld\n",s);
    return 0;
    }
    主要代码部分比较难,不知能否理解。




    我的理解 f[n][m][k] 表示n个球放在m个箱子里 其中装最多球的那个箱子装了k个球,那么f[n][m][k] = sum(f[n-k][m-1][j]) 其中 1<=j<=k 初始条件是f[1][1][1]=1 然后dp一遍