算法计算二项式系数 [英] Algorithm for Calculating Binomial Coefficient

问题描述

我需要计算组合，而无需运行内存的方式。这是我到目前为止所。

 公共静态长的组合（N久，长K）// NCK
{
    返回（divideFactorials（阶乘（n）时，（（阶乘（k）的*阶乘（（正 -  K））））））;
}

公共静态长因子（N久）
{
    长期的结果;
    如果（N＆LT; = 1）返回1;
    结果=因子（N  -  1）* N;
    返回结果;
}

公共静态长divideFactorials（长分子，分母长）
{
    返回阶乘（Math.Abs​​（（分子 - 分母）））;
}
 

我已标记它作为C＃，但解决的办法最好应该是独立的语言。

解决方案

 公共静态长的组合（N久，长K）
    {
        双总和= 0;
        为（长I = 0; I＆LT; k;我++）
        {
            总和+ = Math.log10（N-1）;
            sum- = Math.log10第（i + 1）;
        }
        返程（长）Math.pow（10，总和）;
    }
 

I need a way of calculating combinations without running out of memory. Here's what i have so far.

public static long combination(long n, long k) // nCk
{
    return (divideFactorials(factorial(n), ((factorial(k) * factorial((n - k))))));
}

public static long factorial(long n)
{
    long result;
    if (n <= 1) return 1;
    result = factorial(n - 1) * n;
    return result;
}

public static long divideFactorials(long numerator, long denominator)
{
    return factorial(Math.Abs((numerator - denominator)));
}

I have tagged it as C#, but the solution should ideally be language independent.

解决方案

public static long combination(long n, long k)
    {
        double sum=0;
        for(long i=0;i<k;i++)
        {
            sum+=Math.log10(n-i);
            sum-=Math.log10(i+1);
        }
        return (long)Math.pow(10, sum);
    }

这篇关于算法计算二项式系数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！