轉載請注明出處: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的了,然后其他的就和這里一樣了。