组合数算法 - 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));
}      

转载地址：点击打开链接