Python 中的斐波那契记忆

Question

我编写了这段代码来计算第 n 个斐波那契数，它可以工作（计算出正确的数字）但失败了，因为 table 没有得到更新。有人知道为什么吗？

# memoization
n = 12
table = np.ones(n+1)*-1
def fib3(n):
    if table[n]==-1:
        if n<=2:
            table[n] = 1
        else:
            table[n] = fib3(n-1)+fib3(n-2)
    #return table ##This was part of my original solution but I removed it because it wasn't working
fib3(12)

这是我得到的错误，我认为是由未更新 table 引起的（因为 table[n] 总是 = -1）：

TypeError: unsupported operand type(s) for +: 'NoneType' and 'NoneType'

Answer 1

您没有明确返回任何内容，因此您的 fib3 函数自动 returns None。因此，您的行 table[n] = fib3(n-1) + fib3(n-2) 的计算结果为 table[n] = None + None 并且没有为 None.

定义的 + 运算符

Answer 2

您错过了返回 fib3 函数的值

import numpy as np

# memoization
n = 12
table = np.ones(n+1)*-1
def fib3(n):
    if table[n]==-1:
        if n<=2: 
            table[n] = 1
        else:
            table[n] = fib3(n-1)+fib3(n-2)
    return table[n]
fib3(12)

144

Python 中的斐波那契记忆

Fibonacci Memoization in Python

python

fibonacci

memoization