Binomial Coefficient（二項式系數）

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：

https://github.com/cwiki-us/codebank-algorithm/blob/master/src/test/java/com/ossez/codebank/interview/tests/WayfairTest.java

測試類請參考：

代碼思路請參考：

/**
	 * https://www.cwiki.us/display/ITCLASSIFICATION/Binomial+Coefficient
	 * 
	 * Binomial Coefficient
	 */
	@Test
	public void testBinomialCoefficient() {
		int n = 40;
		int k = 20;

		BigDecimal bc = factorial(n).divide(factorial(k).multiply(factorial(n - k)));
		// a.compareTo(new BigDecimal(1000000000))
		logger.debug("{}", bc);
		logger.debug("Check for Compare To - [{}]", bc.compareTo(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]