带回忆录的Fibonacci和
带回忆录的Fibonacci和
提问于 2015-07-02 08:03:56
问题：
使用递归方法，在不重复计算的情况下找到一个Fibonacci和。
def sum_fibonacci(n):
"""Compute the nth Fibonacci number.
>>> sum_fibonacci(35)
9227465
>>> sum_fibonacci(10)
55
>>> sum_fibonacci(0)
0
>>> sum_fibonacci(1)
1
>>> sum_fibonacci(5)
5
"""
"""Your code here"""解决方案：
fibcache = {}
def sum_fibonacci(n):
"""Compute the nth Fibonacci number.
>>> sum_fibonacci(35)
9227465
>>> sum_fibonacci(10)
55
>>> sum_fibonacci(0)
0
>>> sum_fibonacci(1)
1
>>> sum_fibonacci(5)
5
"""
if n == 0:
fibcache[n] = 0
return fibcache[n]
elif n == 1:
fibcache[n] = 1
return fibcache[n]
else:
sum_left = 0
sum_right = 0
if n-2 in fibcache.keys():
sum_left += fibcache[n-2]
else:
sum_left += sum_fibonacci(n-2)
fibcache[n-2] = sum_left
if n-1 in fibcache.keys():
sum_right += fibcache[n-1]
else:
sum_right += sum_fibonacci(n-1)
fibcache[n-1] = sum_right
return sum_left + sum_right该程序在树递归中使用字典数据模型。
它能更易读吗？它能避免全局缓存fibcache更新吗？因为nonlocal比全球更好。
注意:我现在知道数据模型-- class 'tuple'、class 'list'和class 'dict'。
回答 4
Code Review用户
发布于 2015-07-02 08:14:14
我认为缓存在每个函数上都应该是一样的，
cached_f(args):
if args not in cache:
cache[args] = f(args)
return cache[args]所以斐波纳契变成：
cache = {}
def fib(n):
if n not in cache.keys():
cache[n] = _fib(n)
return cache[n]
def _fib(n):
if n < 2:
return n
else:
return fib(n-1) + fib(n-2)我不知道为什么缓存不应该是全局的(除了名称空间污染之外)，您可能会以结果的复制而结束，还会丢失缓存的结果，从而使您再次计算想要避免计算的内容。
此外，您可以使用基本情况初始化缓存，并在编写递归时跳过缓存，但这并不是很清楚。
Code Review用户
发布于 2015-07-02 13:58:31
如果您不喜欢全局变量(实际上不应该！)，可以通过将它作为函数的一个属性来创建一个静态变量：
def fib(n):
if n in fib.cache:
return fib.cache[n]
ret = fib(n-2) + fib(n-1)
fib.cache[n] = ret
return ret
fib.cache = {0: 1, 1: 1}注释是Python中函数装饰器的海报孩子之一，所以另一种方法应该是：
class Memoize(object):
def __init__(self, func):
self.func = func
self.cache = {}
def __call__(self, *args):
if args in self.cache:
return self.cache[args]
ret = self.func(*args)
self.cache[args] = ret
return ret
@Memoize
def fib(n):
if n < 2:
return 1
return fib(n-2) + fib(n-1)Code Review用户
发布于 2018-05-16 06:05:14
不需要全局变量或两个函数声明：
def fib(a, cache={0:1,1:1}):
if a in cache: return cache[a]
res = fib(a-1, cache) + fib(a-2, cache)
cache[a] = res
return res 缓存应该初始化为0:0，1:1您的解决方案将返回+1的答案。
页面原文内容由Code Review提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://codereview.stackexchange.com/questions/95554
复制相关文章
相似问题
腾讯云开发者
