广西科技大学论坛综合交流 → 一道组合数学题求大神讲
查看完整版本:一道组合数学题求大神讲
2012/12/20 14:59:21

将n个相同的球放入m个相同的盒子,没有空盒,求方法数。



2012/12/20 17:21:46

……是用隔板法吗?



2012/12/20 18:01:30

暴搜...



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个正整数。这我高中的时候考虑过,很难找到通项公式。我当年写过这题的程序,可以用三维动态规划的方式解决,也就是找到一个递推式,非常难。



2012/12/21 4:46:22

正整数的拆分吧,表示组合没学好。。



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一遍



2012/12/21 11:10:14

n!〔n*(m-n)〕好像是这个以前看过


Powered by ZuoJu X5.0
Processed in 0.09 second(s)