斐波那契数的迭代算法

Question

我对斐波那契数列的迭代算法很感兴趣，所以我在维基百科上找到了相关的公式……看起来很简单，所以我在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
None
1
1
1
1
1
1

Answer 1

在计算 fib(0) 时，你返回 0 是因为：

if (n == 0) {
    return 0;
}

在计算 fib(1) 时，你返回 1 是因为：

y = 1
return y

在计算 fib(2) 时，你返回 1 是因为：

y = 1
return y

...以此类推。只要 return y 在你的循环里面，每次函数都会在 for 循环的第一次迭代时就结束。

这里有一个其他用户想到的好解决方案： 如何用 Python 编写斐波那契数列

Answer 2

你在一个循环里返回了一个值，所以函数在y的值还没超过1的时候就结束了。

如果我可以给个更简短、更符合Python风格的建议：

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

这个方法和你的算法完全一样，但它没有创建三个临时变量，而是把它们放进一个列表里，然后通过索引返回第n个斐波那契数。

Answer 3

问题在于你的 return y 写在了函数的循环里面。所以在第一次循环结束后，它就会停止并返回第一个值：1。只有当 n 是 0 的时候，函数才会返回 0，而当 n 是 1 的时候，循环根本不会执行一次，这样就不会有 return 被执行（因此返回的是 None）。

要解决这个问题，只需要把 return y 移到循环外面。

另一种实现方式

根据 KebertX 的例子，这里有一个我个人在 Python 中会做的解决方案。当然，如果你要处理很多斐波那契数值，可能还想把这两种方案结合起来，创建一个缓存来存储这些数字。

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