斐波那契数列，在Python 3中有一行代码吗?

I know there is nothing wrong with writing with proper function structure, but I would like to know how can I find nth fibonacci number with most Pythonic way with a one-line.

我知道，用适当的函数结构来写作并没有什么错，但是我想知道如何用一条一行的python方法来找到第n个斐波那契数。

I wrote that code, but It didn't seem to me best way:

我写了这段代码，但我觉得这并不是最好的方法:

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

How could it be better and simplier?

怎样才能变得更好、更简单呢?

18 个解决方案

#1

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

(this maintains a tuple mapped from [a,b] to [b,a+b], initialized to [0,1], iterated N times, then takes the first tuple element)

(这维护一个从[a,b]映射到[b,a+b]的元组，初始化为[0,1]，迭代N次，然后取第一个元组元素)

>>> fib(1000)
43466557686937456435688527675040625802564660517371780402481729089536555417949051
89040387984007925516929592259308032263477520968962323987332247116164299644090653
3187938298969649928516003704476137795166849228875L

(note that in this numbering, fib(0) = 0, fib(1) = 1, fib(2) = 1, fib(3) = 2, etc.)

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

#2

A rarely seen trick is that a lambda function can refer to itself recursively:

一个罕见的技巧是，lambda函数可以递归地引用它自己:

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

By the way, it's rarely seen because it's confusing, and in this case it is also inefficient. It's much better to write it on multiple lines:

顺便说一下，它很少见，因为它很容易混淆，在这种情况下，它也是低效的。把它写在多行上要好得多:

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

#3

If we consider the "most Pythonic way" to be elegant and effective then:

如果我们认为“最python的方式”是优雅和有效的:

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

wins hands down. Why use a inefficient algorithm (and if you start using memoization we can forget about the oneliner) when you can solve the problem just fine in O(1) by approximation the result with the golden ratio? Though in reality I'd obviously write it in this form:

轻松获胜。为什么使用效率低的算法(如果你开始使用memoization，我们可以忘记oneliner)当你可以通过近似于黄金比例的结果来解决O(1)中的问题?虽然在现实中，我显然会把它写成这种形式:

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

More efficient and much easier to understand.

更有效率，更容易理解。

#4

I recently learned about using matrix multiplication to generate Fibonacci numbers, which was pretty cool. You take a base matrix:

我最近学习了使用矩阵乘法来生成斐波那契数列，这很酷。你取一个基底矩阵:

[1, 1]
[1, 0]

and multiply it by itself N times to get:

再乘以N次得到:

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

This morning, doodling in the steam on the shower wall, I realized that you could cut the running time in half by starting with the second matrix, and multiplying it by itself N/2 times, then using N to pick an index from the first row/column.

今天早上，在淋浴墙上的水蒸汽中，我意识到你可以从第二个矩阵开始，将运行时间减少一半，然后再乘以N/2次，然后使用N从第一行/列中选择一个索引。

With a little squeezing, I got it down to one line:

用一点挤压，我把它变成了一行:

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]

#5

This is a non-recursive (anonymous) memoizing one liner

这是一个非递归(匿名)的memoizing一行。

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]

#6

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

run time O(n), fib(0) = 0, fib(1) = 1, fib(2) = 1 ...

运行时O(n),心房纤颤(0)= 0,fib(1)= 1,fib(2)= 1…

#7

Another example, taking the cue from Mark Byers's answer:

另一个例子，从马克·拜耳的回答中得到提示:

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

#8

This is a closed expression for the Fibonacci series that uses integer arithmetic, and is quite efficient.

这是使用整数算法的斐波那契级数的一个封闭表达式，而且非常有效。

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

>> fib(1000)
4346655768693745643568852767504062580256466051737178
0402481729089536555417949051890403879840079255169295
9225930803226347752096896232398733224711616429964409
06533187938298969649928516003704476137795166849228875L

It computes the result in O(log n) arithmetic operations, each acting on integers with O(n) bits. Given that the result (the nth Fibonacci number) is O(n) bits, the method is quite reasonable.

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

It's based on genefib4 from http://fare.tunes.org/files/fun/fibonacci.lisp , which in turn was based on an a less efficient closed-form integer expression of mine (see: http://paulhankin.github.io/Fibonacci/)

它的基础是http://fare.tunes.org/files/fun/acci.lisp，而这是基于一个不那么高效的闭型整数表达式(参见:http://paulhankin.github.io/acci/)。

#9

Here's an implementation that doesn't use recursion, and only memoizes the last two values instead of the whole sequence history.

这里有一个不使用递归的实现，并且只记录最后两个值而不是整个序列历史。

nthfib() below is the direct solution to the original problem (as long as imports are allowed)

nthfib()下面是原始问题的直接解决方案(只要允许进口)

It's less elegant than using the Reduce methods above, but, although slightly different that what was asked for, it gains the ability to to be used more efficiently as an infinite generator if one needs to output the sequence up to the nth number as well (re-writing slightly as fibgen() below).

它比使用上面的方法减少不太优雅,但是,虽然略有不同,要求是什么,但它获得的能力更有效地使用作为一个无限发电机如果需要输出序列的n个数以及(重写略fibgen下面())。

from itertools import imap, islice, repeat

nthfib = lambda n: next(islice((lambda x=[0, 1]: imap((lambda x: (lambda setx=x.__setitem__, x0_temp=x[0]: (x[1], setx(0, x[1]), setx(1, x0_temp+x[1]))[0])()), repeat(x)))(), n-1, None))    

>>> nthfib(1000)
43466557686937456435688527675040625802564660517371780402481729089536555417949051
89040387984007925516929592259308032263477520968962323987332247116164299644090653
3187938298969649928516003704476137795166849228875L

from itertools import imap, islice, repeat

fibgen = lambda:(lambda x=[0,1]: imap((lambda x: (lambda setx=x.__setitem__, x0_temp=x[0]: (x[1], setx(0, x[1]), setx(1, x0_temp+x[1]))[0])()), repeat(x)))()

>>> list(islice(fibgen(),12))
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144]

#10

To solve this problem I got inspired by a similar question here in * Single Statement Fibonacci, and I got this single line function that can output a list of fibonacci sequence. Though, this is a Python 2 script, not tested on Python 3:

为了解决这个问题，我在*单语句Fibonacci中得到了一个类似的问题，我得到了这个单行函数，它可以输出斐波那契序列的列表。不过，这是一个Python 2脚本，没有在python3上测试过:

(lambda n, fib=[0,1]: fib[:n]+[fib.append(fib[-1] + fib[-2]) or fib[-1] for i in range(n-len(fib))])(10)

assign this lambda function to a variable to reuse it:

将这个lambda函数分配给一个变量来重用它:

fib = (lambda n, fib=[0,1]: fib[:n]+[fib.append(fib[-1] + fib[-2]) or fib[-1] for i in range(n-len(fib))])
fib(10)

output is a list of fibonacci sequence:

输出是斐波那契序列的列表:

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

#11

def fib(n):
    x =[0,1]
    for i in range(n):
        x=[x[1],x[0]+x[1]]
    return x[0]

take the cue from Jason S, i think my version have a better understanding.

从杰森的角度来看，我认为我的版本有更好的理解。

#12

I don't know if this is the most pythonic method but this is the best i could come up with:->

我不知道这是不是最python的方法，但这是我能想到的最好的方法:->。

Fibonacci = lambda x,y=[1,1]:[1]*x if (x<2) else ([y.append(y[q-1] + y[q-2]) for q in range(2,x)],y)[1]

The above code doesn't use recursion, just a list to store the values.

上面的代码不使用递归，只是一个存储值的列表。

#13

My 2 cents

我2美分

# One Liner
def nthfibonacci(n):
    return long(((((1+5**.5)/2)**n)-(((1-5**.5)/2)**n))/5**.5)

OR

或

# Steps
def nthfibonacci(nth):
    sq5 = 5**.5
    phi1 = (1+sq5)/2
    phi2 = -1 * (phi1 -1)
    n1 = phi1**(nth+1)
    n2 = phi2**(nth+1)
    return long((n1 - n2)/sq5)

#14

Why not use a list comprehension?

为什么不使用列表理解呢?

from math import sqrt, floor
[floor(((1+sqrt(5))**n-(1-sqrt(5))**n)/(2**n*sqrt(5))) for n in range(100)]

Without math imports, but less pretty:

没有数学的输入，但更不漂亮:

[int(((1+(5**0.5))**n-(1-(5**0.5))**n)/(2**n*(5**0.5))) for n in range(100)]

#15

Similar:

类似的:

    def fibonacci(n):
      f=[1]+[0]
      for i in range(n):
        f=[sum(f)] + f[:-1]
      print f[1]

#16

A simple Fibonacci number generator using recursion

使用递归的一个简单的Fibonacci数字生成器。

fib = lambda x: 1-x if x < 2 else  fib(x-1)+fib(x-2)
print fib(100)

This takes forever to calculate fib(100) in my computer.

在我的电脑里计算fib(100)是需要花费很多时间的。

There is also closed form of Fibonacci numbers.

斐波那契数列还有一种封闭形式。

fib = lambda n: int(1/sqrt(5)*((1+sqrt(5))**n-(1-sqrt(5))**n)/2**n)
print fib(50)

This works nearly up to 72 numbers due to precision problem.

由于精度问题，这几乎可以达到72个数字。

#17

Lambda with logical operators

λ与逻辑运算符

fibonacci_oneline = lambda n = 10, out = []: [ out.append(i) or i if i <= 1 else out.append(out[-1] + out[-2]) or out[-1] for i in range(n)]

#18

here is how i do it ,however the function returns None for the list comprehension line part to allow me to insert a loop inside .. so basically what it does is appending new elements of the fib seq inside of a list which is over two elements

下面是我的操作方法，但是这个函数没有返回列表理解行部分，允许我在里面插入一个循环。基本上它所做的就是在一个列表中添加fib seq的新元素，它包含两个元素。

>>f=lambda list,x :print('The list must be of 2 or more') if len(list)<2 else [list.append(list[-1]+list[-2]) for i in range(x)]
>>a=[1,2]
>>f(a,7)