python 中的第 N 个斐波那契数列

Question

def fibonaci(i,memo):
    if i == 0 or i == 1:
       return i

    if memo[i]==-1:
       memo[i] = fibonaci(i-1,memo) + fibonaci(i-2,memo)

    return memo[i]

def fibo(n):
    a = []
    return fibonaci(n,a)

print(fibo(2))

我是一名Java程序员，正在学习python。该算法使用递归 + 记忆计算第 n 个斐波那契数。我不明白为什么运行 python 中的程序时会看到此错误“IndexError：列表索引超出范围”。有人可以帮忙吗？非常感谢！

Answer 1

我对你的代码做了一些改动以获得第 n 个斐波那契数。（可能还有其他方法）

def fibonaci(i,memo):
    if i == 0 or i == 1:
       return i

    if memo[i] == -1:
       memo[i] = fibonaci(i-1,memo) + fibonaci(i-2,memo)

    return memo[i]

def fibo(n):
    a = [-1] * n
    return fibonaci(n-1,a)

print(fibo(5))
print(fibo(10))
print(fibo(13))
print(fibo(57))

输出为：-

3
34
144
225851433717

Answer 2

美好的一天，欢迎来到 Python:-)

正如您问题的评论中所建议的，memo[i]==-1 不可能是真的。

我理解你想测试类似“如果斐波那契 (i) 的值尚未被记忆”之类的东西，但是 Python 告诉你索引不存在的方式肯定不是通过返回一些魔法值（如 -1），而是通过引发异常。

在您最喜欢的搜索引擎上查找“EAFP”（请求宽恕比请求许可更容易）可能会告诉您为什么异常不应被理解为错误，在 python。

此外，记忆化最好由字典而不是列表来实现（因为字典允许将值映射到任何可能的键，而不必映射到下一个整数索引值）。

在不对您的程序结构做太多改动的情况下，我建议如下：

def fibonaci(i,memo):
    if i == 0 or i == 1:
        return i

    try:
        memo[i]
    except KeyError:
        memo[i] = fibonaci(i-1,memo) + fibonaci(i-2,memo)

    return memo[i]

def fibo(n):
    a = {} 
    return fibonaci(n,a)

print(fibo(2))

Answer 3

您看到错误是因为您使用 a = [] 创建了一个空列表，然后您尝试查看它。您需要创建一个足够长的列表，以便从零索引到 n-1。

也就是说，在 Python 中进行记忆的一种简单方法是使用 functools 中的 cache 函数。此代码为您做记忆：

from functools import cache


@cache
def fib(n):
    if n <= 1:
        return n
    else:
        return fib(n - 1) + fib(n - 2)


for n in range(10):
    print(f"{fib(n) = }")

在运行时间里效率不高，但在程序员时间里它是。

python 中的第 N 个斐波那契数列

Nth Fibonacci in python

python

dynamic-programming