轉(zhuǎn)載請(qǐng)注明出處:http://www.klion.0fees.net/?p=47

今天無意中再群里看到有人在討論計(jì)算組合數(shù)的一種方法
感覺還有點(diǎn)用就記錄下來了  稍稍的證明了下  證明不是很嚴(yán)密,看官湊合著看吧
c(n,m) = n!/(m!*(n-m)!)
如果n和m比較大時(shí) 可能會(huì)導(dǎo)致中間超過數(shù)據(jù)范圍,不過我們可以直接用遞推也就是
c(n,m) = c(n-1,m)+c(n-1,m-1)
不過下面我們要用另外一種方法來計(jì)算這個(gè)組合
把分子和分母約掉之后就變成了
(n*(n-1)*……*(n-m+1))/m!
這樣上面和下面都是m個(gè)元素,我們可能會(huì)想到乘1個(gè)除1個(gè),這樣來避免越界,可是這樣會(huì)剛好整除嗎？不會(huì)出現(xiàn)小數(shù)使得最后的答案變錯(cuò)嗎？其實(shí)只要我們按照一定的順序來乘和除的話,是不會(huì)產(chǎn)生小數(shù)的,也就是說會(huì)一直整除的.下面給出我的簡單證明,如有錯(cuò)誤,還請(qǐng)指出(這個(gè)公式是借的這位博主的)
首先我們把上面那個(gè)分?jǐn)?shù)寫成這樣的
(n*(n-1)*……*(n-m+1))/(m*(m-1)*……*1)
這樣的話就相當(dāng)于n–>m  (n-1)—>(m-1) …… (n-m+1)—>1
下面先給出主要程序吧
f = 1;//最后答案
for(i = 1;i <= m;i++)
  f = f*(i+(n-m))/i;
現(xiàn)在主要的是要說明每次乘以(i+(n-m))然后再除以i不會(huì)產(chǎn)生小數(shù),我是這么想的,說先i是1,肯定不會(huì)有小數(shù),然后i=2,但是分母已經(jīng)乘過兩個(gè)數(shù)了,肯定有一個(gè)奇數(shù),一個(gè)偶數(shù),也不會(huì)產(chǎn)生小數(shù),同理3的時(shí)候也不會(huì),但是4的時(shí)候可能會(huì)這樣想,前面某個(gè)數(shù)k整除4,那已經(jīng)別2除掉了一個(gè)2,這樣會(huì)不會(huì)產(chǎn)生小數(shù)呢?結(jié)果是不會(huì)的,因?yàn)?個(gè)相當(dāng)于2個(gè)2,或者1個(gè)4,我們可以把除2的那個(gè)選擇到這4個(gè)當(dāng)中不能出4的那一個(gè)數(shù)上,這樣的話,就剩下了一個(gè)能整除4的了,然后其他的就和這里一樣了。