Fibonacci数字,在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

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中;您需要from functools import reduce在Python 3中执行.)

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

我最近学会了使用矩阵乘法来生成Fibonacci数,这非常酷.你拿一个基本矩阵:

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

如果我们认为"最恐怖的方式"优雅而有效,那么:

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

赢得胜利.为什么使用低效算法(如果你开始使用memoization我们可以忘记oneliner)当你可以通过用黄金比率逼近结果来解决O(1)中的问题？虽然实际上我显然是用这种形式写的:

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

更高效,更容易理解.

Answer 5

这是一个非递归(匿名)记忆一个班轮

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]

Answer 6

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

运行时间O(n),fib(0)= 0,fib(1)= 1,fib(2)= 1 ...

Answer 7

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

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）位，则该方法非常合理。

它是基于genefib4从http://fare.tunes.org/files/fun/fibonacci.lisp，这又是基于我的一个效率较低的闭合形式的整数表达式（参见：HTTP：//paulhankin.github。 io / Fibonacci /）

Answer 8

我是 Python 新手，但为了学习目的做了一些措施。我收集了一些 fibo 算法并采取了一些措施。

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()

结果通常是一样的。

带有递归和缓存、Fib 整数算法和 Fibfast 算法的 Fiboslow_2 似乎是最好的。也许我的装饰器不是衡量性能的最佳工具，但总体而言，它似乎不错。