这是给定的斐波那契数列:
1,1,2,3,5,8,13,21
这意味着 n = 8。这是我的斐波那契代码:
def fib(n, count= 0):
if n == 0:
return 0
elif n == 1:
return 1
return fib(n-1) + fib(n-2)
如何创建一个函数来计算上述序列中每个元素的计算次数？例如在计算 fib(5) 时，fib(0) 被调用了 3 次，fib(1) 被调用了 5 次，fib(2) 被调用了 3 次等等...
我尝试使用全局计数器，但我意识到每个 n 值都应该有一个计数器(如果我错了请纠正我)。任何帮助将不胜感激。
请您参考如下方法:
要计算您使用给定的 n 调用该函数的次数，您可以创建一个 Counter 并递增它:
from collections import Counter
c = Counter()
def fib(n):
c[n] += 1
if n == 0:
return 0
elif n == 1:
return 1
return fib(n-1) + fib(n-2)
fib(8)
print(c)
# Counter({1: 21, 2: 13, 0: 13, 3: 8, 4: 5, 5: 3, 6: 2, 8: 1, 7: 1})
这也是查看内存此功能效果的好方法。例如，这里是使用 lru_cache 的计数:
from collections import Counter
from functools import lru_cache
c = Counter()
@lru_cache()
def fib(n):
c[n] += 1
if n == 0:
return 0
elif n == 1:
return 1
return fib(n-1) + fib(n-2)
fib(8)
print(c)
#Counter({8: 1, 7: 1, 6: 1, 5: 1, 4: 1, 3: 1, 2: 1, 1: 1, 0: 1})
