組合數算法 - Slege

組合數算法

組合數的定義：C(n,m)=n!/( (n-m)!*m! )

計算組合數主要頭疼的是溢出，long long 類型的數字算C(82,41)已經不行了。。。

一、普通算法

    由于溢出問題嚴重，是以算出三個階乘再做除法的話，中間結果會溢出。

    首先做個小優化，利用 C(n,m) = C(n,n-m) ，如果m超過n的一半就讓 m = n-m。

    這樣處理之後，m一定是小于等于n-m的

    對于：1，2，3，…，m，m+1，…，n-m，…，n

    公式中 n! , (n-m)!, m!肯定有重疊的部分，是以把n!和(n-m)!中重疊部分消去，直接算(n-m+1)*(n-m+2)*…*n / m!（紅色部分的連乘）就好，這樣時間複雜度是O( m )，已經和n沒有關系了，而且就算要計算 C(10000,3)也可以，因為中間結果最大是1000*999*998。

    還有個小優化，為了防止溢出，一邊計算 (n-m+1)*(n-m+2)*…*n ，一邊除掉1,2,3,...,m中能除的數（下面的算法是按順序除的）

#include"stdio.h"
__int64 cnm(__int64 n,__int64 m)
{
	__int64 sum;
	__int64 k,i;
	k=sum=1;	
	for(i=n-m+1;i<=n;i++)
	{
		sum*=i;
		while(k<=m&&sum%k==0)
		{
			sum/=k;
			k++;
		}
	}
	return sum;
}
int main()
{
	__int64 ans;
	__int64 n,m;
	scanf("%I64d%I64d",&n,&m);
	ans=cnm(n,m);
	printf("%I64d\n",ans);
	return 0;
}
      

二、對數算法

    為了避免直接計算n的階乘，對公式兩邊取對數，于是得到：ln(C(n,m)) = ln(n!) - ln(m!) - ln( (n-m)! )

    對數有性質：ln(x*y) = ln(x) + ln(y)，是以轉化成:

    同理消去重疊的部分，就變成了

    是以這個算法時間複雜度仍然是 O( m )，雖然浮點計算比整數計算要慢，但解決了整數計算的溢出問題。

double cnm_lg(int n,int m)
{
    int i;
    double s1=0.0,s2=0.0;
    for(i=1;i<=m;i++)
        s1 += log(i);
    for(i=n-m+1;i<=n;i++)
        s2 += log(i);
    return s2-s1;
}

double cnm_double(int n,int m)
{
    if(m > n/2)
        m = n-m;
    return exp(cnm_lg(n,m));
}      

轉載位址：點選打開連結