当前位置:首页 » Project Euler » 详细页

Combinatoric selections 题号:53 难度: 5 中英对照

There are exactly ten ways of selecting three from five, 12345:

123, 124, 125, 134, 135, 145, 234, 235, 245, and 345

In combinatorics, we use the notation, 5C3 = 10.

In general,

nCr =
n!
r!(n−r)!
,where rn, n! = n×(n−1)×...×3×2×1, and 0! = 1.

It is not until n = 23, that a value exceeds one-million: 23C10 = 1144066.

How many, not necessarily distinct, values of nCr, for 1 ≤ n ≤ 100, are greater than one-million?

Solution

计算过程的数值超过了long类型的范围,需要使用BigInteger类实现求解。 使用暴力法求解很容易,要求 $~C_n^r,1 \leq n \leq 100~$中所有大于1000000的情况,只需要对$~n,r~$进行两层循环即可。

Code


import java.math.BigInteger;

public final class p053 {

    public static void main(String[] args) {
        long start = System.nanoTime();
        long result = run();
        long end = System.nanoTime();
        System.out.println(result);
        System.out.println((end - start) / 1000000 + "ms");
    }

    public static long run() {
        int result = 0;
        BigInteger limit = BigInteger.TEN.pow(6);
        int nlimit = 100;
        for (int n = 1; n <= nlimit; n++) {
            for (int r = 0; r <= n; r++) {                
                if ( binomial(n,r).compareTo(limit)>0 ) {
                    result++;
                }
            }
        }
        return result;
    }

    private static BigInteger factorial(int x) {
        BigInteger y = BigInteger.ONE;
        for (int i = 2; i <= x; i++) {
            y = y.multiply(BigInteger.valueOf(i));
        }
        return y;
    }
    
    private static BigInteger binomial(int n, int r){
        return factorial(n).divide(factorial(r).multiply(factorial(n - r)));
    }
}
4075
151ms