java - 使用内存计算二项式 choose(n,r) = n!/(r!(n-r)!)

Question

二项式函数 choose(n,r) = n!/(r!(n-r)!) 如何编写一个程序来计算 10^8 = 1 亿个随机二项式，其中 N 从 1 到 52 随机选择，R 随机选择 0 到 n。

需要使用记忆化或类似方法在 O(1) 时间内计算二项式。

我的代码就是这样。我知道在每次递归中，一个元素可能会计算两次，我不知道如何通过使用内存来提高效率。

public static int choose(int n, int k){
    if(k == 0) return 1;

    return (n * choose(n - 1, k - 1)) / k;
}

Answer 1

首先，对于整数数据类型，您可能会得到太大的数字... Proof .

这个想法是你一步一步来......乘以被除数的后续数字并除以除数的后续数字。

public class Binom {

    private long[][] mapped;

    public Binom(){
        mapped = new long[52][52];
    }

    public long binom(int n, int r) {
        if (r == 0)
            return 1;
        if (r == 1)
            return n;

        if(r > n-r)
            r = n-r;
        long toReturn = 1;
        for (int i = 1, m = n; i <= r; i++, m--){
            toReturn = toReturn*m/i;
        }
        return toReturn;
    }

    public long[][] getMapped() {
        return mapped;
    }
}

我的基准:

public class Benchmark {

    public static void main(String[] args) {
        long start = System.nanoTime();
        Random random = new Random();
        int count = 1;
        Binom binom = new Binom();
        long[][] mapped = binom.getMapped();
        for (int i = 1; i <= 100_000_000; i++) {
            int n = 1 + random.nextInt(52);
            int r = 1 + random.nextInt(n);
            long result = mapped[n-1][r-1];
            if (result != 0) {
                System.out.println(count++ + ". Binomial for n: " + n + " and r: " + r + " equals " + result + ".");
            } else {
                result = binom.binom(n, r);
                mapped[n-1][r-1] = result;
                System.out.println(count++ + ". Binomial for n: " + n + " and r: " + r + " equals " + result + ".");
            }
        }
        System.out.println("The whole lasted " + ((System.nanoTime() - start)/1_000_000_000) + " seconds.");
    }
}

输出结束:

99999995. Binomial for n: 3 and r: 3 equals 1.
99999996. Binomial for n: 19 and r: 17 equals 171.
99999997. Binomial for n: 26 and r: 20 equals 230230.
99999998. Binomial for n: 32 and r: 13 equals 347373600.
99999999. Binomial for n: 20 and r: 14 equals 38760.
100000000. Binomial for n: 3 and r: 3 equals 1.
The whole lasted 342 seconds.

如果不打印它会更快...您只需要计算那些 1378=(52*52/2) 对的二项式系数。