将n个相同的球放入m个相同的盒子,没有空盒,求方法数。
这题等价于求一个正整数n如何分解为m个正整数。这我高中的时候考虑过,很难找到通项公式。我当年写过这题的程序,可以用三维动态规划的方式解决,也就是找到一个递推式,非常难。
zgh0202
2012/12/21 7:02:33
代码写完了,用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一遍