0

假设我们有以下算法：

    int com(int a, int b)
    {
        if (b==0 || a==b)
        {

            return(1);
        }
        else 
        {
            return(com(a-1,b) + com(a-1,b-1));
        }
    }

是否有方法可以在不使用递归的情况下更快地计算此结果？我正在尝试优化速度，但这个解决方案太慢了。

4

2 回答 2

3

通常的公式是

com(a,b) = a!/(b!(a-b)!)

在哪里！是 n*(n-1)*...*3*2*1。为了更快的计算，您当然可以消除相互抵消的因素，因此您只剩下：

com(a,b) = a*(a-1)*...*(a-b)/(1*2*..*(a-b))

但是对于严肃的数值计算，你应该使用 log-gamma 函数lgamma而不是滚动你自己的阶乘函数：

com(a,b) = exp(lgamma(a+1)-(lgamma(a-b+1)+lgamma(b+1)))
于 2013-02-24T23:31:51.357 回答
1

很多，尤其是乘法公式：http ://en.wikipedia.org/wiki/Binomial_coefficient

于 2013-02-24T23:29:36.843 回答