OSSEZTEC 阅读(230) 评论(0)

In mathematics, any of the positive integers that occurs as a coefficient in the binomial theorem is a binomial coefficient. Commonly, a binomial coefficient is indexed by a pair of integers n ≥ k ≥ 0 and is written {\displaystyle {\tbinom {n}{k}}.} {\displaystyle {\tbinom {n}{k}}.} It is the coefficient of the xk term in the polynomial expansion of the binomial power (1 + x)n, and it is given by the formula.

英文描述

英文描述请参考下面的图。

中文描述

根据给定的公式计算二项式的值。

在这里有一个说明需要注意的是,如果结果超过 1,000,000,000 你的程序应该返回 -1。

如果结果没有定义的话,那么你的程序应该也要返回 -1。

思路和点评

在这里的计算,公式比较简单,就是计算 N,K N-K 的阶乘,在阶乘中,你可以使用递归进行计算。

但是需要注意的是对这个数字的阶乘计算量,程序是很容易溢出的,如果从出题者的意图来看就是要考察大数值的计算和计算中的溢出。

如果你使用的是 Java 的话,你应该使用类 BigDecimal,进行计算。如果你可以使用 Apache Common Math 的话,你就直接使用 CombinatoricsUtils.factorialDouble 进行计算。在计算中允许的最大参数值为 170,超过这个值以后就超过程序能够计算的最大值了。

如果你希望直接计算二项式系数的话,你可以使用 CombinatoricsUtils.binomialCoefficientDouble(40, 20) 直接进行计算。

源代码

源代码和有关代码的更新请访问 GitHub:

外链网址已屏蔽

测试类请参考:

外链网址已屏蔽

代码思路请参考:

/**
 * 外链网址已屏蔽
 * 
 * Binomial Coefficient
 */
@Test
public void testBinomialCoefficient() {
  int n = 40;
  int k = 20;

  BigDecimal bc = factorial(n).divide(factorial(k).multiply(factorial(n - k)));
  // pareTo(new BigDecimal(1000000000))
  logger.debug("{}", bc);
  logger.debug("Check for Compare To - [{}]", pareTo(new BigDecimal(1000000000)));
  logger.debug("Value - [{}]", bc);

  logger.debug("Apache CombinatoricsUtils Factorial - [{}]", CombinatoricsUtils.factorialDouble(20));
  logger.debug("Apache CombinatoricsUtils Binomial Coefficient - [{}]", CombinatoricsUtils.binomialCoefficientDouble(40, 20));

}

/**
 * for factorial
 * 
 * @param x
 * @return
 */
private static BigDecimal factorial(int x) {
  if (x == 1 || x == 0) {
    return BigDecimal.valueOf(1);
  } else {
    return BigDecimal.valueOf(x).multiply(factorial(x - 1));
  }
}

 

测试结果

上面程序的测试结果如下:

2018/12/29 19:35:10 DEBUG [com.ossez.codebank.interview.tests.WayfairTest] - 137846528820
2018/12/29 19:35:10 DEBUG [com.ossez.codebank.interview.tests.WayfairTest] - Check for Compare To - [1]
2018/12/29 19:35:10 DEBUG [com.ossez.codebank.interview.tests.WayfairTest] - Value - [137846528820]
2018/12/29 19:35:10 DEBUG [com.ossez.codebank.interview.tests.WayfairTest] - Apache CombinatoricsUtils Factorial - [2.43290200817664E18]
2018/12/29 19:35:10 DEBUG [com.ossez.codebank.interview.tests.WayfairTest] - Apache CombinatoricsUtils Binomial Coefficient - [1.3784652882E11]