山寨机中的战斗机！	程序优化工程师到底对IT界有没有贡献

简单问题，接分请进。

楼主fire314159（水源是学生，穷鬼，闷骚型男人的聚集地，请对号入座）2005-05-05 12:20:19 在 C/C++ / C语言提问

m个球，放到n个盘子里面。每个盘子可以放一个，多个或者不放。
问题---
1，当m>=n，且n个盘子各不相同。
2，当m<n, 且n个盘子各不相同。
3, 当m>=n，且n个盘子都相同。
4，当m<n, 且n个盘子都相同。

这四种情况下，各有多少种分法？

要求，不要跟我用回溯法穷举出答案。要求是用数学的方法得到答案。问题点数：60、回复次数：25Top

1 楼du51（郁郁思扬）回复于 2005-05-05 12:29:26 得分 3

那m个球一样吗?Top

2 楼fire314159（水源是学生，穷鬼，闷骚型男人的聚集地，请对号入座）回复于 2005-05-05 12:35:19 得分 0

m个球相同Top

3 楼zhousqy（标准C匪徒)(甩拉，甩拉）回复于 2005-05-05 12:51:59 得分 3

markTop

4 楼liujingfu123（Oh_My_GoD）回复于 2005-05-05 13:49:52 得分 2

问题太简单，我来接分的Top

5 楼dongpy（51-->ARM）回复于 2005-05-05 13:59:30 得分 3

pow(n,m)Top

6 楼Non_miracle（CSDN小七）回复于 2005-05-05 14:16:24 得分 3

我觉的每个问题的算法应该是相同的
可以这样想..将第1个盘子里不放球
第二个盘子放一个,M=M-1
第三个盘子放2个 M=M-2
用M>=0KO控制while循环
共样的另外三个问题都这么考虑
用IF控制问题!
楼主要是没想好.说话我晚上来写程序
Top

7 楼ltc_mouse（野地芳菲）回复于 2005-05-05 15:50:42 得分 3

1、2题我觉得等价于求解方程 x(1)+x(2)+...+x(n) = m 的非负整数解的个数

3、4题则是把m拆分成不多于n个整数和形式的方法数的问题，离散数学中有详细描述
例如：m=5, n=3，则有：5=5；5=4+1；5=3+2；5=3+1+1；5=2+2+1；5种拆分方法Top

8 楼useresu（俗人)(灌水是我无言的抗议）回复于 2005-05-05 15:59:15 得分 3

mark

jfTop

9 楼lzwei3842（赐缘）回复于 2005-05-05 16:09:26 得分 3

长见识Top

10 楼flying_dancing（小混混-_-）回复于 2005-05-05 16:13:29 得分 3

1>.2>一样 n^m/m!...呵呵数学忘光了...
JF
mark
Top

11 楼qingyuan18（zealot_tang）回复于 2005-05-05 16:54:54 得分 3

第一个盘子放k1个的放法是C(k1,m)，第二个盘子放k2个的放法是C（k2，m）.......
这样总共的放法是C（K1，M） + C（k2,m) +C(k3,m) +........
k1+k2+k3+........kn = m

查查概率书，公式化简，应该可以算出来的。Top

12 楼mostideal（三甲）回复于 2005-05-05 17:36:07 得分 3

不知道怎么做了。。。学习。。Top

13 楼fire314159（水源是学生，穷鬼，闷骚型男人的聚集地，请对号入座）回复于 2005-05-05 22:16:55 得分 0

那些诸如写pow(n,m)的仁兄请认真看题。真的这样我还来这问吗？
这里一个盘子既可以装全部球，又可以一个都不装，没有要求每种分法每个盘子都有球，也就是说m个相同的球是随便喜欢放哪就放哪。给出一个测试数据，3，4情况下，m=7,n=3，有8种分法。Top

14 楼fire314159（水源是学生，穷鬼，闷骚型男人的聚集地，请对号入座）回复于 2005-05-05 22:21:25 得分 0

回复人： Non_miracle(CSDN小七）
我觉的每个问题的算法应该是相同的
可以这样想..将第1个盘子里不放球
第二个盘子放一个,M=M-1
第三个盘子放2个 M=M-2
用M>=0KO控制while循环
共样的另外三个问题都这么考虑
用IF控制问题!
楼主要是没想好.说话我晚上来写程序

-------------------
1，2情况和3，4情况应该是不同的，1，2是排列，3，4是组合Top

15 楼xingjibing（星际冰）回复于 2005-05-05 23:14:56 得分 3

前两种情况，每个球有n种放法，即n的m次方；如果m＝n，则总放法再－m＋1；
后两种容以后再想，呵呵Top

16 楼du51（郁郁思扬）回复于 2005-05-06 00:49:39 得分 5

第一题我想了一上午.不会.可能太笨了.呵呵.
算是抛砖引玉吧把我的结果写一下.(肯定不对)
----------------------------------------
E(i=n/i=0)表示i从0到n的连加.
C(i/n)表示从n中选i的组合数
P(i/n)表示从n中选i的排列数.

E(i=n/i=1)C(i-1/m-1)P(i/n)
---------------------------------------
另外,我只做了第一题.后面的没看.因为第一个都不会.汗!!!!!!!!
用程序可能会简单点.因为电脑可检验.可递归.可循环.用数学公式表达.不是那么容易.当然了,可能是我数学基础不好吧.呵呵.Top

17 楼du51（郁郁思扬）回复于 2005-05-06 01:24:45 得分 3

刚才看一下,后两个,似乎是
1+E(i=n/i=2)[floor]C(i-1/m-1)/i
似乎也不对.晕了.呵呵.
Top

18 楼ltc_mouse（野地芳菲）回复于 2005-05-06 16:56:30 得分 3

第3种情况，按下列的递归方法考虑试试看：
F(m,n,k)表示把m个无差别的球放入n个无差别的盘子，盘子中球的最大数量为k，分情况如下：
(1) n*k-m < 0，此时，不可能将m个球放入n个盘子(每个盘子球数不超过k)，F(m,n,k)=0
(2) n=1 或者 m=0, 则 F(m,n,k)=1
(3) 不满足(1),(2),则 F(m,n,k) = sum{ i=1, i<=min(m,k) | F(m-i, n-1, i) }

问题所求即是F(m,n,m)（适合4），目前不知道怎样转化成一般的数学表达式...
例如,m=5,n=2，则
F(5,2,5) = F(4,1,1)+F(3,1,2)+F(2,1,3)+F(1,1,4)+F(0,1,5)
= 0 + 0 + 1 + 1 + 1 = 3Top

19 楼qhfu（改个名字）回复于 2005-05-06 17:57:26 得分 2

up，骗分来的， ^_^Top

20 楼llf_hust（）回复于 2005-05-06 18:03:36 得分 2

upTop

21 楼fire314159（水源是学生，穷鬼，闷骚型男人的聚集地，请对号入座）回复于 2005-05-09 09:06:40 得分 0

谢谢各位踊跃发言，接分也欢迎。可惜没有一个人写出数学表达式。我现在给出第一，二种情况的表达式，各位可以再思考，想想看,如果真的遇到这样的问题，别人仅仅算那条公式就oK了。我们还在那里努力的回溯，递归。差别就在这了，看来这数学素养还真的需要阿。

NO1，2 situation :
C m,n+m-1.也就是说n+m-1取m个的组合。公式可能经过化简。

有人给出或解释一条公式就结贴。Top

22 楼fire314159（水源是学生，穷鬼，闷骚型男人的聚集地，请对号入座）回复于 2005-05-09 09:18:35 得分 0

如果用程序实现，我已经完成了第三，四种情况，用同一个程序就行了。回溯法，由于盘子相同，所以任意互换两个盘子的位置都可以，所以只要把每个盘子的球数按递增或者递减排放的所有情况计算出来就可以了。这两种情况是北大acm题的NO.1664. 程序已提交通过。现在请大家讨论如何数学方法来思考这个问题。因为我知道有人的确是这样干的。Top

23 楼inlin（）回复于 2005-05-09 10:10:11 得分 3

只要用概率的插空法来做就行了
自己想想先
不懂发信息给我Top

24 楼inlin（）回复于 2005-05-09 10:10:43 得分 2

这是纯正的概率问题Top

25 楼ltc_mouse（野地芳菲）回复于 2005-05-11 08:43:47 得分 5

NO1，2 situation :
C m,n+m-1.也就是说n+m-1取m个的组合。公式可能经过化简。

这个正是方程组 x1+x2+x3+...+xn = m 的非负整数解的个数。思路如下（一般的组合数学书都有）：
采用“挡板法”。求非负整数解，相当于在 m个1中间插入n-1个0，这n-1个0将m个1分成了n部分，第i部分中的1的个数，就是xi对应的值。换个角度，上述一共有 m + (n-1) 个元素（0或1），只要确定m个1的位置或者n-1个0的位置，就得到方程组的一个解。
于是解的个数为： C m,m+(n-1) 或者 C n-1, m+(n-1)Top