?

計算組合數最大的困難在于數據的溢出，對于大于150的整數n求階乘很容易超出double類型的范圍，那么當C(n,m)中的n=200時，直接用組合公式計算基本就無望了。另外一個難點就是效率。

??? 對于第一個數據溢出的問題，可以這樣解決。因為組合數公式為：

??? C(n,m) = n!/(m!(n-m)!)

為了避免直接計算n的階乘，對公式兩邊取對數，于是得到：

??? ln(C(n,m)) = ln(n!)-ln(m!)-ln((n-m)!)

進一步化簡得到：

???

這樣我們就把連乘轉換為了連加，因為ln(n)總是很小的，所以上式很難出現數據溢出。

??? 為了解決第二個效率的問題，我們對上式再做一步化簡。上式已經把連乘法變成了求和的線性運算，也就是說，上式已經極大地簡化了計算的復雜度，但是還可以進一步優化。從上式中，我們很容易看出右邊的3項必然存在重復的部分。現在我們把右邊第一項拆成兩部分：

???

這樣，上式右邊第一項就可以被抵消掉，于是得到：

???

上式直接減少了2m次對數計算及求和運算。但是這個公式還可以優化。對于上面公式里的求和，當m<n/2時，n-m是一個很大的數，但是當m>n/2時，n-m就會小很多。我們知道：

??? C(n,m) = C(n,n-m)

那么通過這個公式，我們可以把小于n/2的m變為大于n/2的n-m再進行計算，結果是一樣的，但是卻能減少計算量。

??? 當計算出ln(C(n,m))后，只需要取自然對數，就可以得到組合數：

??? C(n,m) = exp(ln(C(n,m)))

這樣就完成了組合數的計算。

??? 用這種方法計算組合數，如果只計算ln(C(n,m))的話，n可以取到整型數據的極限值65535，

??? ln(C(65535,32767)) = 45419.6

而計算時間只需要0.01ms。當然，如果要取對數得到最終的組合數的話，n的取值就不能達到這么大了。但是這種算法仍然可以保證n取到1000以上，而不是開頭說的150這個極限值。例如:

??? C(1000,500) = 2.70288e+299

計算時間仍然小于0.01ms。

??? 采用我這種算法，不僅n的取值范圍大，而且計算速度高，不像用遞歸算法實現這個問題的時候，很容易陷入遞歸層次太深而導致計算時間太長。

??? 算法代碼實現如下：

double lnchoose(int n, int m)
{

if (m > n)

{

return 0;

}
if (m < n/2.0)
{
m = n-m;
}

double s1 = 0;
for (int i=m+1; i<=n; i++)
{
s1 += log((double)i);
}

double s2 = 0;
int ub = n-m;
for (int i=2; i<=ub; i++)
{
s2 += log((double)i);
}

return s1-s2;
}

double choose(int n, int m)
{

if (m > n)

{

return 0;

}
return exp(lnchoose(n, m));
}

摘自：http://blog.sina.com.cn/s/blog_4298002e0100eko0.html

有一個用歐幾里得擴展算法計算的大數取模計算方法，比較實用

#include<cstdio>
?#include<memory>
?using namespace std;
?const int mod=10007;
?int a[mod];
?void init()
?{
?int i;
???? a[0]=1;
?for(i=1;i<mod;i++)
??? a[i]=(a[i-1]*i)%mod;
?}
?int gcd(int a,int b){
?if(b==0) return a;
?return gcd(b,a%b);
?}
void e_gcd(int a,int b,int &x,int &y) //擴展歐幾里得定理：解ax+by==1。
?{
???? if(!b)
???? {
???????? x=1;
???????? y=0;
???? }
???? else
???? {
???????? e_gcd(b,a%b,x,y);
???????? int l=x;
???????? x=y;
???????? y=l-a/b*y;
???? }
?}
int choose(int n,int m)??
?{
???? if(m>n)
??? return 0;
?else if(n==m)
??? return 1;
?int nn=a[n],mm=(a[m]*a[n-m])%mod;
?int d=gcd(nn,mm);
?nn/=d;
?mm/=d;
???? int x,y;
???? e_gcd(mm,mod,x,y);
?x=(x+mod)%mod;
???? return (x*nn)%mod;
?}
?int main( )
?{
?int t;
?scanf("%d",&t);
?init();
?while(t--)
?{
??? int e[100],f[100];
??? int i=0,j,m,n;
??? memset(e,0,sizeof(e));
??? memset(f,0,sizeof(f));
??? scanf("%d %d",&n,&m);
??? while(n>0)
??? {
???? e[i++]=n%mod;
???? n=n/mod;
??? }
??? int len=i;
??? i=0;
??? while(m>0)
??? {
??????????? f[i++]=m%mod;
????? m=m/mod;
??? }
??? int re=1;
???????? for(i=0;i<len;i++)
??? {
??????????? re=(re*choose(e[i],f[i]))%mod;
??? }
??? printf("%d\n",re%mod);
?}
?return 0;
?}

/********************************************/

轉載于:https://www.cnblogs.com/liushang0419/archive/2011/09/30/2196457.html

總結

以上是生活随笔為你收集整理的高效的组合数计算方法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。