用Python 3写一行代码生成斐波那契数列？

Question

我知道写代码的时候用合适的函数结构是没问题的，但我想知道用最“Pythonic”的方式，怎么能用一行代码找到第n个斐波那契数。

我写了这个代码，但我觉得这不是最好的方法：

>>> fib = lambda n:reduce(lambda x, y: (x[0]+x[1], x[0]), [(1,1)]*(n-2))[0]
>>> fib(8)
13

那有什么更好更简单的方法吗？

Answer 1

我最近学到了用矩阵乘法来生成斐波那契数，这个方法挺有意思的。你先准备一个基础矩阵：

[1, 1]
[1, 0]

然后把这个矩阵自己乘N次，就能得到：

[F(N+1), F(N)]
[F(N), F(N-1)]

今天早上，我在洗澡的时候，看到蒸汽在墙上画画，突然想到其实可以通过从第二个矩阵开始，先把它自己乘N/2次，这样就能把运行时间缩短一半。然后再用N来从第一行或第一列中选一个索引。

经过一番琢磨，我把这个过程简化成了一行代码：

import numpy

def mm_fib(n):
    return (numpy.matrix([[2,1],[1,1]])**(n//2))[0,(n+1)%2]

>>> [mm_fib(i) for i in range(20)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]

Answer 2

一个很少见的技巧是，lambda函数可以自我调用，也就是递归调用自己：

fib = lambda n: n if n < 2 else fib(n-1) + fib(n-2)

顺便说一下，这种用法不常见是因为它比较让人困惑，而且在这种情况下效率也不高。写成多行代码会更好：

def fibs():
    a = 0
    b = 1
    while True:
        yield a
        a, b = b, a + b

Answer 3

fib = lambda n:reduce(lambda x,n:[x[1],x[0]+x[1]], range(n),[0,1])[0]

（这个过程保持了一个元组，它把 [a,b] 映射到 [b,a+b]，最开始的值是 [0,1]，然后重复这个过程 N 次，最后取第一个元组的元素）

>>> fib(1000)
43466557686937456435688527675040625802564660517371780402481729089536555417949051
89040387984007925516929592259308032263477520968962323987332247116164299644090653
3187938298969649928516003704476137795166849228875L

（注意，在这个编号中，fib(0) = 0，fib(1) = 1，fib(2) = 1，fib(3) = 2，等等。）

（另外要注意：reduce 是 Python 2.7 中的一个内置函数，但在 Python 3 中没有；在 Python 3 中你需要执行 from functools import reduce。）