代码拉取完成,页面将自动刷新
using System;
using System.Numerics;
namespace Algorithms.Numeric;
/// <summary>
/// The binomial coefficients are the positive integers
/// that occur as coefficients in the binomial theorem.
/// </summary>
public static class BinomialCoefficient
{
/// <summary>
/// Calculates Binomial coefficients for given input.
/// </summary>
/// <param name="num">First number.</param>
/// <param name="k">Second number.</param>
/// <returns>Binimial Coefficients.</returns>
public static BigInteger Calculate(BigInteger num, BigInteger k)
{
if (num < k || k < 0)
{
throw new ArgumentException("num ≥ k ≥ 0");
}
// Tricks to gain performance:
// 1. Because (num over k) equals (num over (num-k)), we can save multiplications and divisions
// by replacing k with the minimum of k and (num - k).
k = BigInteger.Min(k, num - k);
// 2. We can simplify the computation of (num! / (k! * (num - k)!)) to ((num * (num - 1) * ... * (num - k + 1) / (k!))
// and thus save some multiplications and divisions.
var numerator = BigInteger.One;
for (var val = num - k + 1; val <= num; val++)
{
numerator *= val;
}
// 3. Typically multiplication is a lot faster than division, therefore compute the value of k! first (i.e. k - 1 multiplications)
// and then divide the numerator by the denominator (i.e. 1 division); instead of performing k - 1 divisions (1 for each factor in k!).
var denominator = BigInteger.One;
for (var val = k; val > BigInteger.One; val--)
{
denominator *= val;
}
return numerator / denominator;
}
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。