在 python 斐波那契程序中获取索引错误

Question

我刚刚在Coursera上启动了"算法工具箱"，并正在用python 2.7编写他们的斐波那契程序版本

。

def fibonacci(n):
    F = []
    F[0] = 0
    F[1] = 1
    for i in range(0,n):
        F[i] = F[i-1] + F[i-2]
    return F[n]
fibonacci(3)

但是，我不断收到此错误：

Traceback (most recent call last):
  File "fibonacci.py", line 11, in <module>
    fibonacci(3)
  File "fibonacci.py", line 3, in fibonacci
    F[0] = 0

IndexError: list assignment index out of range

Answer 1

不能通过分配给不存在的索引来在 Python 列表中创建新元素。您的列表为空，因此索引0和1不存在。

请改用list.append()：

def fibonacci(n):
    F = [0, 1]  # a list with two initial elements
    for i in range(2, n + 1):
        F.append(F[i-1] + F[i-2])  # add new value to the list
    return F[n]

请注意，循环从 2 开始，而不是0 ，因为您已经有了 0 和 1 的值。不包括要range()的 stop 参数，因此如果要查找第 n 个斐波那契数，则需要将范围运行到 n + 1 。

现在代码工作了：

>>> def fibonacci(n):
...     F = [0, 1]
...     for i in range(2, n + 1):
...         F.append(F[i-1] + F[i-2])
...     return F[n]
...
>>> fibonacci(10)
55

请注意，您实际上并不需要将所有值存储在列表中;您只需要跟踪最后 2 个值。您可以只使用两个变量，并在每次迭代中交换它们;一个存储

def fibonacci(n):
    prev, curr = 0, 1  # two variables, one set to 0, the other to 1
    for _ in range(n - 1):  # run n - 2 times
        prev, curr = curr, prev + curr
    return curr

请注意，这不会对n进行任何边界测试，因此对于n = 0，结果将不正确（返回 1 而不是 0）。这很容易通过顶部的if n < 1: return 0线来补救。

Answer 2

这是因为当程序达到F[0]时，它会尝试评估F的第 0 个索引中的内容。问题是F最初是一个空列表，因此没有第 0 个索引。您希望使用 F.append(0) 和 F.append(1) 来追加这些元素。

Answer 3

您必须将

值附加到列表中，因为它的大小为 0。当您在下一个索引中添加项目时，Python 列表不会自动增长，您必须指定它，例如使用 append 函数

F = []
F.append(0)
F.append(1)
# [0, 1]
# OR
F = [0, 1]
# [0, 1]

Answer 4

您的代码存在几个问题：

def fibonacci(n):
    F = [] #3
    F[0] = 0
    F[1] = 1
    for i in range(0,n):
        F[i] = F[i-1] + F[i-2] #1
    return F[n] #2

1. 第一次迭代这将是F[0] = F[-1] + F[-2]，这在Python中定义得很好，但不是你想要的。你可能想查看 Python 的索引方案。

2. F[n]指的是第 n+1 个元素，因为 Python 的索引为 0。范围是[下，上），所以它实际上没有i = n在最终迭代中。

3. 正如Martijn在下面评论的那样，第三个问题是你不能简单地索引到一个空列表中。您必须执行连续追加，或者将整个列表分配为 F = [0]*n 。

Answer 5

你需要从 2 而不是 0 开始循环。

def fibonacci(n):
    F = [0,1]
    if n<0:
        return None
    if n<2:
        return F[n]
    for i in range(2,n):
        F[i] = F[i-1] + F[i-2]
    return F[n]
fibonacci(3)