斐波那契数列，在 Python 3 中带有一行？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/4935957/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Fibonacci numbers, with an one-liner in Python 3?
提问by utdemir
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.
我知道使用正确的函数结构编写没有任何问题，但是我想知道如何使用一行一行的大多数 Pythonic 方式找到第 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?
怎样才能更好更简单？
采纳答案by Jason S
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 等）
(also note: reduceis a builtin in Python 2.7 but not in Python 3; you'd need to execute from functools import reducein Python 3.)
（另请注意：reduce是 Python 2.7 中的内置函数，但在 Python 3 中不是；您需要from functools import reduce在 Python 3 中执行。）
回答by Mark Byers
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
回答by Voo
If we consider the "most Pythonic way" to be elegant and effective then:
如果我们认为“最 Pythonic 的方式”是优雅和有效的，那么：
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:
赢得胜利。当您可以通过用黄金比例近似结果在 O(1) 中很好地解决问题时，为什么要使用低效算法（如果您开始使用记忆化，我们可以忘记 oneliner）？虽然实际上我显然会以这种形式写它：
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.
更高效，更容易理解。
回答by 6502
This is a non-recursive (anonymous) memoizing one liner
这是一个非递归（匿名）记忆一个班轮
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]
回答by Jason S
Another example, taking the cue from Mark Byers's answer:
另一个例子，从 Mark Byers 的回答中得到提示：
fib = lambda n,a=0,b=1: a if n<=0 else fib(n-1,b,a+b)
回答by dalef
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), fib(0) = 0, fib(1) = 1, fib(2) = 1 ...
回答by Jon Schoning
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).
它不如使用上面的 Reduce 方法优雅，但是，尽管与所要求的略有不同，但如果还需要将序列输出到第 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]
回答by Chris Doggett
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]
回答by MMSs
To solve this problem I got inspired by a similar question here in Stackoverflow 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:
为了解决这个问题，我受到了 Stackoverflow Single Statement Fibonacci 中的一个类似问题的启发，我得到了这个可以输出斐波那契数列列表的单行函数。不过，这是一个 Python 2 脚本，未在 Python 3 上测试：
(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]
回答by bigtan
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.
从 Jason S 那里得到提示，我认为我的版本有更好的理解。
