sucesion - Números de Fibonacci, con una línea en Python 3?
fibonacci series (18)
¿Por qué no usar una lista de 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 importar matemática, pero menos bonita:
[int(((1+(5**0.5))**n-(1-(5**0.5))**n)/(2**n*(5**0.5))) for n in range(100)]
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 Ptónica con una línea.
Escribí ese código, pero no me pareció la mejor manera:
>>> fib=lambda n:reduce(lambda x,y:(x[0]+x[1],x[0]),[(1,1)]*(n-2))[0]
>>> fib(8)
13
¿Cómo podría ser mejor y más simple?
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 que se permitan las importaciones)
Es menos elegante que usar los métodos Reducir anteriores, pero, aunque es ligeramente diferente de lo que se solicitó, gana la capacidad de ser utilizado más eficientemente 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]
Esta es una expresión cerrada para la serie de Fibonacci que usa 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
Calcula el resultado en operaciones aritméticas O (log n), cada una actuando en enteros con O (n) bits. 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 basó en una expresión de enteros de forma cerrada menos eficiente (ver: http://paulhankin.github.io/Fibonacci/ )
Este es un trazador de líneas de memoria no recursivo (anónimo)
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]
Lambda con 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)]
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)
No sé si este es el método más pitónico, pero esto es lo mejor que pude encontrar: ->
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 no usa recursión, solo una lista para almacenar los valores.
Otro ejemplo, siguiendo el ejemplo de la respuesta de Mark Byers:
fib = lambda n,a=0,b=1: a if n<=0 else fib(n-1,b,a+b)
Para resolver este problema, me inspiré en una pregunta similar aquí en Single Statement Fibonacci , y obtuve esta función de línea única que puede generar una lista de secuencia de fibonacci. Sin embargo, este es un script de 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)
asigne esta función lambda a una variable para reutilizarla:
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 secuencia de fibonacci:
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
Recientemente aprendí sobre el uso de la multiplicación de matrices para generar números de Fibonacci, lo cual fue muy bueno. Tomas una matriz base:
def fib(nr):
return int(((1 + math.sqrt(5)) / 2) ** nr / math.sqrt(5) + 0.5)
y multiplicarlo por sí mismo N veces para obtener:
def fib(nr):
ratio = (1 + math.sqrt(5)) / 2
return int(ratio ** nr / math.sqrt(5) + 0.5)
Esta mañana, garabateando en el vapor en la pared de la ducha, me di cuenta de que podías reducir el tiempo de ejecución 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 apretar, lo tengo en una línea:
[1, 1]
[1, 0]
Si consideramos que la "manera más pitonica" es elegante y efectiva, entonces:
[F(N+1), F(N)]
[F(N), F(N-1)]
gana manos abajo. ¿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:
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]
Más eficiente y mucho más fácil de entender.
Similar:
def fibonacci(n):
f=[1]+[0]
for i in range(n):
f=[sum(f)] + f[:-1]
print f[1]
Un simple generador de números de Fibonacci usando recursión
fib = lambda x: 1-x if x < 2 else fib(x-1)+fib(x-2)
print fib(100)
Esto lleva una eternidad calcular el fib(100) en mi computadora.
También hay forma cerrada 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.
Un truco raramente visto es que una función lambda puede referirse a sí misma recursivamente:
fib = lambda n: n if n < 2 else fib(n-1) + fib(n-2)
Por cierto, rara vez se ve porque es confuso, y en este caso también es ineficiente. Es mucho mejor escribirlo en múltiples líneas:
def fibs():
a = 0
b = 1
while True:
yield a
a, b = b, a + b
así es como lo hago, sin embargo la función devuelve Ninguno para la parte de la lista de comprensión de listas para permitirme insertar un bucle dentro ... así que básicamente lo que hace es agregar nuevos elementos del seq de fib dentro de una lista que está sobre 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)
def fib(n):
x =[0,1]
for i in range(n):
x=[x[1],x[0]+x[1]]
return x[0]
siguiendo el ejemplo de Jason S, creo que mi versión tiene una mejor comprensión.
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 ...
fib = lambda n:reduce(lambda x,n:[x[1],x[0]+x[1]], range(n),[0,1])[0]
(esto mantiene una tupla mapeada de [a, b] a [b, a + b], inicializada a [0,1], iterada N veces, luego toma el primer elemento de tupla)
>>> fib(1000)
43466557686937456435688527675040625802564660517371780402481729089536555417949051
89040387984007925516929592259308032263477520968962323987332247116164299644090653
3187938298969649928516003704476137795166849228875L
(tenga en cuenta que en esta numeración, fib (0) = 0, fib (1) = 1, fib (2) = 1, fib (3) = 2, etc.)