Números de Fibonacci, con una línea en Python 3?

Question

Sé que no hay nada de malo en escribir con la estructura de función adecuada, pero me gustaría saber cómo puedo encontrar el n. ° número de fibonacci con la forma más pitonica con una línea.

escribí ese código, pero no me parece mejor manera:

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

como no podía ser mejor y más simple?

Answer 1

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

(Esto mantiene una tupla asignada desde [a, b] a [b, a + b], inicializa a [0,1], iterado N veces, y luego se lleva el primer elemento de tupla)

>>> fib(1000) 
43466557686937456435688527675040625802564660517371780402481729089536555417949051 
89040387984007925516929592259308032263477520968962323987332247116164299644090653 
3187938298969649928516003704476137795166849228875L 

(nótese que en esta numeración, fib (0) = 0, fib (1) = 1, fib (2) = 1, fib (3) = 2, etc.)

Answer 2

Un truco que rara vez se ve es una función lambda puede referirse a sí mismo de forma recursiva:

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

Por cierto, es poco frecuente porque es confuso, y en este caso también es ineficiente. Es mucho mejor que escribirlo en varias líneas:

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

Answer 3

Si tenemos en cuenta la "forma más Pythonic" es elegante y eficaz a continuación:

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

gana sin esfuerzo. ¿Por qué usar un algoritmo ineficiente (y si comienzas a utilizar la memoria podemos olvidarnos del delineador) cuando puedes resolver el problema muy bien en O (1) por aproximación el resultado con la proporción áurea? Aunque en realidad obviamente lo escribiría de esta forma:

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

Más eficiente y mucho más fácil de entender.

Answer 4

este no es un -recursivo (anónimo) memorizar un trazador de líneas

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 5

Otro ejemplo, tomando el ejemplo de respuesta de Mark Byers:

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

Answer 6

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

tiempo de ejecución O (n), fib (0) = 0, fib (1) = 1, fib (2) = 1 ...

Answer 7

Aquí hay una implementación que no usa recursividad, y solo memoriza los dos últimos valores en lugar de todo el historial de la secuencia.

nthfib() a continuación es la solución directa al problema original (siempre y cuando se permiten las importaciones)

es menos elegante que el uso de los métodos reducen el anterior, pero, aunque ligeramente diferente que lo que se solicitó, se gana la habilidad de ser usado de manera más eficiente como un generador infinito si también se necesita generar la secuencia hasta el enésimo número (reescribiendo ligeramente como fibgen() a continuación).

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] 

Answer 8

Recientemente he aprendido acerca del uso de la multiplicación de matrices para generar números de Fibonacci, que era bastante guay. Se toma una matriz de base:

[1, 1] 
[1, 0] 

y se multiplica por sí mismo n veces para obtener:

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

Esta mañana, hacer garabatos en el vapor en la pared de la ducha, me di cuenta de que se podía cortar el funcionamiento tiempo a la mitad comenzando con la segunda matriz, y multiplicándola por sí misma N/2 veces, luego usando N para elegir un índice de la primera fila/columna.

Con un poco de compresión, lo tengo a una línea:

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 9

Para resolver este problema me inspiré en una pregunta similar aquí en Stackoverflow Single Statement Fibonacci, y me dieron esta función sola línea que se puede dar salida una lista de secuencia de fibonacci. Sin embargo, esto es una secuencia de comandos Python 2, no probado en 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) 

asignar esta función lambda a una variable de reutilizar que:

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) 

salida es una lista de la secuencia de Fibonacci:

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

Answer 10

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

tomar el ejemplo de Jason S, creo que mi versión tiene un mejor entendimiento.

Answer 11

similares:

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

Answer 12

No sé si este es el método más Pythonic pero esto es lo mejor que podía llegar a: ->

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] 

El código anterior doesn' t usa recursión, solo una lista para almacenar los valores.

Answer 13

Mis 2 centavos

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

O

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

Answer 14

Un generador de números Fibonacci sencilla utilizando la recursividad

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

Esto tarda una eternidad para calcular fib(100) en mi ordenador.

También hay closed form de números de Fibonacci.

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

Esto funciona casi hasta 72 números debido a un problema de precisión.

Answer 15

Lambda con los operadores lógicos

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

Answer 16

aquí es cómo lo hago, sin embargo, la función devuelve Ninguno para la parte de línea de lista por comprensión que me permita insertar un bucle en el interior .. así que básicamente lo que hace es añadiendo nuevos elementos de la SEC fib dentro de una lista que es más de dos elementos

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

Answer 17

Esta es una expresión cerrado para la serie de Fibonacci que utiliza aritmética de enteros, y es bastante eficiente.

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

>> fib(1000) 
4346655768693745643568852767504062580256466051737178 
0402481729089536555417949051890403879840079255169295 
9225930803226347752096896232398733224711616429964409 
06533187938298969649928516003704476137795166849228875L 

que calcula el resultado en O (log n) operaciones aritméticas, actuando cada uno en números enteros con O bits (N). Dado que el resultado (el enésimo número de Fibonacci) es O (n) bits, el método es bastante razonable.

Se basa en genefib4 de http://fare.tunes.org/files/fun/fibonacci.lisp, que a su vez se basa en un número entero una expresión de forma cerrada menos eficiente de la mina (ver: http://paulhankin.github.io/Fibonacci/)

Answer 18

Por qué no utilizar una lista por comprensión?

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

Sin importaciones de matemáticas, pero menos bonita:

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