组合词“N”在java数学中选择R?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (22)

在Java库中是否有一个内置方法,可以为任何N,R计算‘N选择R’?

提问于
用户回答回答于

公式

N choose K即使没有计算因子,计算其实也很容易。

我们知道公式为(N choose K)

    N!
 --------
 (N-K)!K!

因此,公式为(N choose K+1)

       N!                N!                   N!               N!      (N-K)
---------------- = --------------- = -------------------- = -------- x -----
(N-(K+1))!(K+1)!   (N-K-1)! (K+1)!   (N-K)!/(N-K) K!(K+1)   (N-K)!K!   (K+1)

那是:

(N choose K+1) = (N choose K) * (N-K)/(K+1)

我们也知道那(N choose 0)是:

 N!
---- = 1
N!0!

所以这给了我们一个简单的起点,并且使用上面的公式,我们可以找到(N choose K)任何K > 0K乘法和K除法的。

易帕斯卡的三角形

综合上述内容,我们可以很容易地生成帕斯卡三角形,如下所示:

    for (int n = 0; n < 10; n++) {
        int nCk = 1;
        for (int k = 0; k <= n; k++) {
            System.out.print(nCk + " ");
            nCk = nCk * (n-k) / (k+1);
        }
        System.out.println();
    }

这输出:

1 
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1 
1 5 10 10 5 1 
1 6 15 20 15 6 1 
1 7 21 35 35 21 7 1 
1 8 28 56 70 56 28 8 1 
1 9 36 84 126 126 84 36 9 1 

BigInteger

应用公式BigInteger很简单:

static BigInteger binomial(final int N, final int K) {
    BigInteger ret = BigInteger.ONE;
    for (int k = 0; k < K; k++) {
        ret = ret.multiply(BigInteger.valueOf(N-k))
                 .divide(BigInteger.valueOf(k+1));
    }
    return ret;
}

//...
System.out.println(binomial(133, 71));
// prints "555687036928510235891585199545206017600"

扫码关注云+社区