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

如何让它更好、更简单？

- utdemir

---

怎么能更好、更简单呢？不要只有一行代码就好了。 - Karl Knechtel

Answer 1

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，依此类推。)

(同时注意：在Python 2.7中，reduce是内置函数，但在Python 3中不是；您需要在Python 3中执行from functools import reduce。)

- Jason S

---

但是我并没有真正理解这个解决方案，x是一个整数，范围在[0,1]+range(n)，对吗（我想我的错误就在这里）？但我们使用的是x [1]，x [0]。怎么做到的？我看不出我们如何维护元组。 - utdemir

reduce 函数的输入函数接受两个参数：累加器和输入。对于可迭代对象中的每个元素（在本例中是 range(n)），reduce 都会调用该函数。在这种情况下，累加器是一个元组 x，初始化为 [0,1]。reduce() 函数中的函数输出一个新的元组 [x[1],x[0]+x[1]]。 - Jason S

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

- Mark Byers

---

1->n，2->1 允许 fib(0) = 0。 - DSM

@Jason S，@DSM：感谢您们的评论。已更新答案。 - Mark Byers

对于生成器，我一直认为它是在Python中表示斐波那契数列最优雅和高效的方式。 - Rafe Kettler

我不知道 lambda 函数可以调用自身，但如果我们可以像使用 self 访问类变量一样使用关键字引用 lambda，而无需将其分配给某个变量，那将是很好的。 - utdemir

应用记忆化模式：fib = lambda n,m={}: m.get(n) or m.setdefault(n, n if n < 2 else fib(n - 1) + fib(n - 2)) - John La Rooy

Answer 3

最近我学到了使用矩阵乘法生成斐波那契数列，感觉很酷。你需要一个基础矩阵：

[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]

- Chris Doggett

---

@winmwx：Numpy数组支持2D索引（[i，j]），因此对于普通列表，它将类似于a [0] [(1,0) [n％2]]。基本上是获取矩阵的顶行（[F（N + 1），F（N）]），然后使用（1,0）[n％2]根据N是偶数还是奇数选择其中之一。因此，如果N是偶数，则取第二个（F（N）），如果是奇数，则取第一个（F（N + 1））。现在我再看一遍，我本可以让它使用[0，（n + 1）％2]。这是因为我们从第二个矩阵（[[2,1]，[1,1]]）开始，所以会有一个偏差。 - Chris Doggett

Answer 4

这是一个使用整数算术的斐波那契数列的封闭表达式，非常高效。

fib = lambda n:pow(2<<n,n+1,(4<<2*n)-(2<<n)-1)%(2<<n)

>> fib(1000)
4346655768693745643568852767504062580256466051737178
0402481729089536555417949051890403879840079255169295
9225930803226347752096896232398733224711616429964409
06533187938298969649928516003704476137795166849228875L

它在O(log n)的算术运算中计算结果，每个操作都作用于O(n)位的整数。考虑到结果（第n个斐波那契数）是O(n)位，该方法相当合理。

它基于http://fare.tunes.org/files/fun/fibonacci.lisp中的genefib4，而该文件又基于我不那么高效的闭式整数表达式（请参见：http://paulhankin.github.io/Fibonacci/）。

- Paul Hankin

Answer 5

如果我们认为“最Pythonic的方式”是优雅而有效的，那么：

def fib(nr):
    return int(((1 + math.sqrt(5)) / 2) ** nr / math.sqrt(5) + 0.5)

wins hands down. 为什么要使用低效的算法（即使你开始使用记忆化，我们也可以忘记这个一行代码的解决方案），当你可以通过用黄金比例近似结果在O(1)内完美地解决问题呢？虽然实际上我肯定会用以下形式编写：

def fib(nr):
    ratio = (1 + math.sqrt(5)) / 2
    return int(ratio ** nr / math.sqrt(5) + 0.5)

更高效，更易理解。

- Voo

---

我也考虑了显式的斐波那契公式，但是对于较大的n存在精度问题。 - Jason S

对于小的n值，它存在精度问题；fib(71) 的结果是错误的。如果我们只需要对前几个项正确，那么使用def fib(n): return [0, 1, 1, 2, 3, ..][n]即可更加简单。[已更新代码中round到int的更改问题] - DSM

谢谢，其实我的主要目的是探索Python的能力，而不是快速计算 :)。+1 - utdemir

好吧，那是短视的 - 只测试了前60个值，并假设如果在那里工作，我们不会遇到更大值的精度问题。嗯，那就太糟糕了。是的，改变了公式，因为我认为它应该可以在没有显式舍入的情况下正常工作。 - Voo

你为什么认为记忆化会排除一个一行代码的解决方案？ - 6502

顺便说一句，如果这确实是常数时间，我们将有很多NP难问题需要减少。如果我没记错，pow的时间复杂度为$O(\log(n))$。 - Sean Allred

Answer 6

这是一个非递归的（匿名）记忆化一行代码

fib = lambda x,y=[1,1]:([(y.append(y[-1]+y[-2]),y[-1])[1] for i in range(1+x-len(y))],y[x])[1]

- 6502

Answer 7

fib = lambda n, x=0, y=1 : x if not n else fib(n-1, y, x+y)

运行时间为O(n)，斐波那契数列的前两个数字分别是0和1，从第三个数字开始，每个数字都是前两个数字之和...

- dalef

Answer 8

我是Python的新手，但为了学习目的采取了一些措施。我收集了一些斐波那契算法并进行了一些措施。

from datetime import datetime
import matplotlib.pyplot as plt
from functools import wraps
from functools import reduce
from functools import lru_cache
import numpy


def time_it(f):

    @wraps(f)
    def wrapper(*args, **kwargs):
        start_time = datetime.now()

        f(*args, **kwargs)

        end_time = datetime.now()
        elapsed = end_time - start_time
        elapsed = elapsed.microseconds

        return elapsed
    return wrapper


@time_it
def fibslow(n):
    if n <= 1:
        return n

    else:
        return fibslow(n-1) + fibslow(n-2)


@time_it
@lru_cache(maxsize=10)
def fibslow_2(n):
    if n <= 1:
        return n

    else:
        return fibslow_2(n-1) + fibslow_2(n-2)


@time_it
def fibfast(n):
    if n <= 1:
        return n

    a, b = 0, 1

    for i in range(1, n+1):
        a, b = b, a + b

    return a


@time_it
def fib_reduce(n):
    return reduce(lambda x, n: [x[1], x[0]+x[1]], range(n), [0, 1])[0]


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


@time_it
def fib_ia(n):
    return pow(2 << n, n+1, (4 << 2 * n) - (2 << n)-1) % (2 << n)


if __name__ == '__main__':

    X = range(1, 200)
#    fibslow_times = [fibslow(i) for i in X]
    fibslow_2_times = [fibslow_2(i) for i in X]
    fibfast_times = [fibfast(i) for i in X]
    fib_reduce_times = [fib_reduce(i) for i in X]
    fib_mm_times = [mm_fib(i) for i in X]
    fib_ia_times = [fib_ia(i) for i in X]

#    print(fibslow_times)
#    print(fibfast_times)
#    print(fib_reduce_times)

    plt.figure()
#    plt.plot(X, fibslow_times, label='Slow Fib')
    plt.plot(X, fibslow_2_times, label='Slow Fib w cache')
    plt.plot(X, fibfast_times, label='Fast Fib')
    plt.plot(X, fib_reduce_times, label='Reduce Fib')
    plt.plot(X, fib_mm_times, label='Numpy Fib')
    plt.plot(X, fib_ia_times, label='Fib ia')
    plt.xlabel('n')
    plt.ylabel('time (microseconds)')
    plt.legend()
    plt.show()

结果通常是相同的。 使用递归和缓存的Fiboslow_2，Fib整数算法和Fibfast算法似乎是最好的。也许我的装饰器不是衡量性能的最佳方法，但对于概述来说，它看起来很好。

- tkircsi

Answer 9

我想看看是否可以创建整个序列，而不仅仅是最终值。

以下代码将生成长度为100的列表。它排除了前导的[0, 1]，并且适用于Python2和Python3。没有其他额外的行！

(lambda i, x=[0,1]: [(x.append(x[y+1]+x[y]), x[y+1]+x[y])[1] for y in range(i)])(100)

输出

[1,
 2,
 3,
 ...
 218922995834555169026,
 354224848179261915075,
 573147844013817084101]

- Alec

Answer 10

还有一个例子，参考Mark Byers的答案：

fib = lambda n,a=0,b=1: a if n<=0 else fib(n-1,b,a+b)

- Jason S

---

尽管在n=999时似乎存在递归深度问题。Python没有尾递归吗？ - Jason S

不，它没有尾递归消除。 - user395760