python - 如何跟踪每个元素在 Fibonacci 中的计算次数？

Question

这是给定的斐波那契数列:

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 值都应该有一个计数器(如果我错了请纠正我)。任何帮助将不胜感激。

Answer 1

要计算您使用给定的 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})