转载请注明出处:http://www.klion.0fees.net/?p=47

今天无意中再群里看到有人在讨论计算组合数的一种方法
感觉还有点用就记录下来了  稍稍的证明了下  证明不是很严密,看官凑合着看吧
c(n,m) = n!/(m!*(n-m)!)
如果n和m比较大时 可能会导致中间超过数据范围,不过我们可以直接用递推也就是
c(n,m) = c(n-1,m)+c(n-1,m-1)
不过下面我们要用另外一种方法来计算这个组合
把分子和分母约掉之后就变成了
(n*(n-1)*……*(n-m+1))/m!
这样上面和下面都是m个元素,我们可能会想到乘1个除1个,这样来避免越界,可是这样会刚好整除吗？不会出现小数使得最后的答案变错吗？其实只要我们按照一定的顺序来乘和除的话,是不会产生小数的,也就是说会一直整除的.下面给出我的简单证明,如有错误,还请指出(这个公式是借的这位博主的)
首先我们把上面那个分数写成这样的
(n*(n-1)*……*(n-m+1))/(m*(m-1)*……*1)
这样的话就相当于n–>m  (n-1)—>(m-1) …… (n-m+1)—>1
下面先给出主要程序吧
f = 1;//最后答案
for(i = 1;i <= m;i++)
  f = f*(i+(n-m))/i;
现在主要的是要说明每次乘以(i+(n-m))然后再除以i不会产生小数,我是这么想的,说先i是1,肯定不会有小数,然后i=2,但是分母已经乘过两个数了,肯定有一个奇数,一个偶数,也不会产生小数,同理3的时候也不会,但是4的时候可能会这样想,前面某个数k整除4,那已经别2除掉了一个2,这样会不会产生小数呢?结果是不会的,因为4个相当于2个2,或者1个4,我们可以把除2的那个选择到这4个当中不能出4的那一个数上,这样的话,就剩下了一个能整除4的了,然后其他的就和这里一样了。