我正在使用以下递归函数计算任意大小的二项式系数
private static final BigDecimal ZERO = new BigDecimal("0");
private static final BigDecimal ONE = new BigDecimal("1");
private static BigDecimal binomial(BigDecimal n, BigDecimal k) {
if(n.equals(k) || k.equals(ZERO))
return ONE;
else if(k.compareTo(ZERO) < 0)
return ZERO;
else
return binomial(n.subtract(ONE), k).add(binomial(n.subtract(ONE), k.subtract(ONE)));
}
对于大数字，它变得非常慢。是否有任何简单和/或明显的优化？不确定 BigDecimals 减慢了多少，但是为大量数字创建自定义类似乎需要做很多工作。
你可以在保持递归的同时做得相当好（BigInteger虽然算术很不愉快）：
public class Binomials {
private HashMap<Pair<BigInteger, BigInteger>, BigInteger> map = new HashMap();
public BigInteger binomial(int n, int k) {
return binomial(new Pair(valueOf(n), valueOf(k)));
}
public BigInteger binomial(Pair<BigInteger, BigInteger> x) {
if(x.getValue().equals(ZERO) || x.getKey().equals(x.getValue())) {
return ONE;
}
return map.computeIfAbsent(x, nk -> binomial(doP1(nk)).add(binomial(doP2(nk))));
}
private Pair<BigInteger, BigInteger> doP1(Pair<BigInteger, BigInteger> nk) {
return new Pair(nk.getKey().subtract(ONE), nk.getValue());
}
private Pair<BigInteger, BigInteger> doP2(Pair<BigInteger, BigInteger> nk) {
return new Pair(nk.getKey().subtract(ONE), nk.getValue().subtract(ONE));
}
public static void main(String[] args) {
System.out.println(new Binomials().binomial(8, 4)); // 70
}
}
事实上，所有这些Pair和BigInteger恶作剧都足够嘈杂，以至于掩盖了正在发生的事情，所以在 Kotlin 中使用相同的方法：
fun BigInteger.plus(other: BigInteger): BigInteger = this.add(other)
fun BigInteger.minus(other: BigInteger): BigInteger = this.subtract(other)
object Binomial {
val map = mutableMapOf<Pair<BigInteger, BigInteger>, BigInteger>()
fun binomial(n: Int, k: Int): BigInteger =
binomial(Pair(n.toBigInteger(), k.toBigInteger()))
fun binomial(x: Pair<BigInteger, BigInteger>): BigInteger {
val (n, k) = x
if (k == ZERO || n == k) {
return ONE
}
return map.getOrPut(x) { binomial(Pair(n - ONE, k)) + binomial(Pair(n - ONE, k - ONE)) }
}
}
fun main() {
println(binomial(8, 4)) // 70
}
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句