我自己正在学习 JAVA,我现在正在学习记忆。但我有点迷失方向......
有没有人有一些关于如何通过使用递归和使用记忆来加速算法来计算 Java 组合的示例代码?
就像计算 C5,3 = 5*4*3/3*2*1 = 10 的方法一样?但使用递归?
我自己正在学习 JAVA,我现在正在学习记忆。但我有点迷失方向......
有没有人有一些关于如何通过使用递归和使用记忆来加速算法来计算 Java 组合的示例代码?
就像计算 C5,3 = 5*4*3/3*2*1 = 10 的方法一样?但使用递归?
让我们用一个例子来做20 选择 5
由于 20 choose 5
定义为20! / ( 5! * (20-5)! )
我们可以memoization
用来存储这些阶乘计算,这样我们就不必在递归下不断地重新计算它们。
所以:
//STORING FACTORIAL COMPUTATIONS
private Map<Integer,Long> factorialMap = new HashMap<Integer,Long>();
public Long getFactorial(int number) {
//CHECK IF I ALREADY COMPUTED THIS FACTORIAL
Long val = factorialMap.get(number);
if(val != null) {
//GOT IT!
return val;
} else {
//NEED TO COMPUTE!
val = getFactorialRecursive(number);
//STORING IT TO SAVE COMPUTATION FOR LATER
factorialMap.put(number, val);
return val;
}
}
//RECURSIVE FUNCTION TO COMPUTE FACTORIAL
public Long getFactorialRecursive(int number) {
if(number < 2) {
return 1L;
} else {
return number * getFactorialRecursive(number-1);
}
}
//ACTUAL CALL TO "20 choose 5"
public Long combination(int fromVal, int chooseVal) {
return getFactorial(fromVal)/(getFactorial(chooseVal)*getFactorial(fromVal-chooseVal));
}
您可以在combinatoricslib
此处免费使用该库: