一道组合数学题求大神讲
- 斯斯LV.连长
- 2012/12/20 14:59:21
将n个相同的球放入m个相同的盒子,没有空盒,求方法数。
- 卡夫卡
- 2012/12/20 17:21:46
……是用隔板法吗?
- 吸烟醉
- 2012/12/20 18:01:30
暴搜...
- jujujuju
- 2012/12/20 20:30:59
因是相同的球 相同的盒子 不可用隔板法
- 澜雨
- 2012/12/20 23:28:11
2种吧....
- 日日日
- 2012/12/21 0:15:07
这个要讨论吧。。取决于n-m?
- 昕旭
- 2012/12/21 2:13:50
这题等价于求一个正整数n如何分解为m个正整数。这我高中的时候考虑过,很难找到通项公式。我当年写过这题的程序,可以用三维动态规划的方式解决,也就是找到一个递推式,非常难。
- wowowo
- 2012/12/21 4:46:22
正整数的拆分吧,表示组合没学好。。
- 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;
}
主要代码部分比较难,不知能否理解。
- 去见他
- 2012/12/21 9:52:32
我的理解 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一遍

广科栏目