给定fibonacci递归函数的记忆算法
给定fibonacci递归函数的记忆算法
提问于 2019-11-06 14:45:14
对于学校作业，我们必须创建一个记忆中的fibonacci函数，该函数重用计算fibonacci的递归实现。
什么是一个好的方法来设计我们的记忆函数，使它利用一个已经存在的函数？这是我到目前为止的实现：
基类：
public int computeFibonacci(int position) {
assertPosition(position);
if (position < 2) {
return 1;
}
return computeFibonacci(position - 1) + computeFibonacci(position - 2);
}继承类：
public int computeFibonacci(int position) {
assertPosition(position);
if (position < 2) {
return 1;
}
if (this.memoizedList.containsKey(position)) {
return this.memoizedList.get(position);
}
int result = super.computeFibonacci(position - 1) + super.computeFibonacci(position - 2);
this.memoizedList.put(position, result);
return result;
}回答 2
Stack Overflow用户
发布于 2019-11-06 19:18:09
在基类中重用递归实现会让人感到困惑。如果调用递归实现，它将递归计算fib(n) = fib(n-1) + fib(n-2) = ...，这与memo函数冲突。Memo函数尝试为计算结果节省时间。备注：
public int computeFibonacci(int position) {
assertPosition(position);
if (position < 2) {
return 1;
}
if (this.memoizedList.containsKey(position)) {
return this.memoizedList.get(position);
}
int result = computeFibonacci(position - 1) + computeFibonacci(position - 2);
this.memoizedList.put(position, result);
return result;
}例如，您尝试打印fibonacci中的前1000个元素，memo函数将节省计算的时间。
Stack Overflow用户
发布于 2019-11-06 14:51:21
您的子类版本没有充分利用缓存值。例如，如果您调用computeFibonacci(5)，而memoizedList不包含该键，那么您将调用super.computeFibonacci(4)和super.computeFibonacci(3)，即使它们已经被缓存。相反，您应该调用super.computeFibonacci(5)。
public int computeFibonacci(int position) {
assertPosition(position);
if (position < 2) {
return 1;
}
if (this.memoizedList.containsKey(position)) {
return this.memoizedList.get(position);
} else {
int result = super.computeFibonacci(position);
this.memoizedList.put(position, result);
return result;
}
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/58724472
复制相关文章
相似问题
腾讯云开发者
