Fibonacci数的迭代算法

Question

我对Fibonacci数的迭代算法很感兴趣,所以我在wiki上找到了公式...它看起来很直接,所以我在Python中尝试了...它没有问题编译和公式看起来正确...不是确定为什么它给出了错误的输出......我没有实现它吗？

def fib (n): 
    if( n == 0):
        return 0
    else:
        x = 0
        y = 1
        for i in range(1,n):
            z = (x + y)
            x = y
            y = z
            return y

for i in range(10):
    print (fib(i))

产量

0
无
1
1
1
1
1
1

Answer 1

问题是return y你的功能在你的循环中.所以在第一次迭代之后,它将已经停止并返回第一个值:1.除非n是0,在这种情况下函数返回0自身,如果n是1,当for循环不会迭代一次,并且没有return正在执行(因此None返回值).

要解决此问题,只需移动return y循环外部即可.

替代实施

按照KebertX的例子,这是我个人用Python制作的解决方案.当然,如果您要处理许多Fibonacci值,您甚至可能希望将这两个解决方案组合在一起并为数字创建缓存.

def f(n):
    a, b = 0, 1
    for i in range(0, n):
        a, b = b, a + b
    return a

Answer 2

您在循环中返回一个值，因此函数在 y 的值变得大于 1 之前退出。

如果我可以建议更短，更pythonful的东西：

def fibs(n):                                                                                                 
    fibs = [0, 1, 1]                                                                                           
    for f in range(2, n):                                                                                      
        fibs.append(fibs[-1] + fibs[-2])                                                                         
    return fibs[n]

这将与您的算法做完全相同的事情，但它不会创建三个临时变量，而是将它们添加到列表中，并按索引返回第 n 个斐波那契数。