計(jì)算組合數(shù)

編寫函數(shù)，參數(shù)是兩個(gè)非負(fù)整數(shù)n和m，返回組合數(shù)

其中m<=n<=25。例如，n=25,m=12時(shí)的答案為5200300。

代碼及算法分析

程序4-1 組合數(shù)（有問(wèn)題）

#include <stdio.h> long long factorial(int n) {long long m=1;//不要忘記初始化，不然的出來(lái)的結(jié)果驚人。for(int i=1;i<=n;i++){m*=i;}return m; } int main () {int n,m;scanf("%d %d",&n,&m);printf("%lld",factorial(n)/(factorial(m)*factorial(n-m)));return 0; }

這個(gè)代碼的問(wèn)題顯而易見(jiàn)，階乘容易溢出，所以不可取。
所以，套用劉汝佳老師的一句話：”即使最終答案在所選擇的數(shù)據(jù)類型范圍之內(nèi)，計(jì)算的中間結(jié)果仍然可能溢出“。

汝佳老師也給出了相應(yīng)的解決方案，雖然不能完全避免中間結(jié)果溢出，但是對(duì)于題目給出的范圍已經(jīng)可以保證得到正確的結(jié)果了。
先來(lái)分析一下組合數(shù)的公式：
n!
————
m!(n-m)!
展開之后：
n *(n-1) *(n-2)……3 *2 *1
—————————————————————————————（1）
m *(m-1) *(m-2)……3 *2 *1 *(n-m) *(n-m-1) *(n-m-2)…… *3 *2 *1
因?yàn)閚>=m，所以m在1~n之間，這樣可以把n!除以m!約分：
n *(n-1) *(n-2)……(m+2) *(m+1)
————————————————（2）
(n-m) *(n-m-1) *(n-m-2)…… *3 *2 *1

然后汝佳老師給了一道思考題：為什么當(dāng)m<n-m時(shí)要把m變成n-m？
移項(xiàng)之后得到：m<n/2，先列一個(gè)數(shù)軸：
|————————————————————>
0 1 2 3 ……m……n/2……M……(n-1) n
為了不把變換后的m與變換前的m弄混，把變化后的m記為M。因?yàn)榻M合數(shù)的公式，分子是大于分母的，所以分子的乘積比較大，容易溢出，要想優(yōu)化，就得讓分子乘積變小。
M=n-m帶入組合式公式之后就是：
n!
————————————————（3）
M!(n-M)!=(n-m)!(n-(n-m))!=(n-m)!m!
所以式子并沒(méi)有變化，同樣可以進(jìn)行約分得到（2）式的變式：
n *(n-1) *(n-2)……(M+2) *(M+1)
————————————————（4）
(n-M) *(n-M-1) *(n-M-2)…… *3 *2 *1
相當(dāng)于將數(shù)軸
|————————————————————>
0 1 2 3 ……m ……n/2……M ……(n-1) n
標(biāo)出的部分直接干掉了。

由于M是大于m的，所以分子的乘積縮小，溢出問(wèn)題得到緩解，注意，是緩解不是解決，如果n和m的值很大的話還是會(huì)溢出。
分析之后就可以把程序4-1升級(jí)為程序4-2了：

#include <stdio.h> long long c(int n,int m) {if(m<n-m){m=n-m;}long long ans=1;for(int i=m+1;i<=n;i++){ans*=i;}for(int i=1;i<=n-m;i++){ans/=i;}return ans; } int main () {int n,m;scanf("%d %d",&n,&m);printf("%lld",c(n,m));return 0; }

汝佳老師提示

“對(duì)復(fù)雜的表達(dá)式進(jìn)行化簡(jiǎn)有時(shí)不僅能減少計(jì)算量，還能減少甚至避免中間結(jié)果的溢出。”

總結(jié)

以上是生活随笔為你收集整理的《算法竞赛入门经典》计算组合数问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。