Progtwig de Python para encontrar series de fibonacci. Manera más pythonica

Hay otro hilo para discutir la serie Fibo en Python. Esto es para ajustar el código en más pythonic. Cómo escribir la secuencia de Fibonacci en Python

Estoy enamorado de este progtwig que escribí para resolver el Proyecto Euler Q2. Estoy codificando recientemente en Python y me alegro cada vez que lo hago de la manera Pythonic. ¿Puedes sugerir una mejor forma pythonica para hacer esto?

Proyecto Euler Q2 . Encuentre la sum de todos los términos pares en la secuencia de Fibonacci que no excedan los cuatro millones.

fib=[] def fibo(a=-1,b=1,upto=4000000): if a+b>=upto: return else: a,b=b,a+b fib.append(b) fibo(a,b) fibo() even=[i for i in fib if not i%2] print sum(even) 

Primero haría fibo () como generador:

 def fibo(a=-1,b=1,upto=4000000): while a+b 

Luego también seleccionaría la uniformidad como un generador en lugar de una lista de comprensión.

 print sum(i for i in fibo() if not i%2) 

El uso de generadores es una forma de Pythonic para generar secuencias largas mientras se preserva la memoria:

 def fibonacci(): a, b = 0, 1 while True: yield a a, b = b, a + b import itertools upto_4000000 = itertools.takewhile(lambda x: x <= 4000000, fibonacci()) print(sum(x for x in upto_4000000 if x % 2 == 0)) 

Por un lado, sugeriría resumir los términos a medida que los calcule en lugar de almacenarlos en una matriz y luego sumr la matriz, ya que no necesita hacer nada con los términos individuales más que sumrlos. (Eso es solo un buen sentido computacional en cualquier idioma)

Yo haría los siguientes cambios:

  • Usa iteración en lugar de recursión
  • Simplemente mantenga un total acumulado en lugar de mantener una lista de todos los números de Fibonacci y luego encuentre la sum de los pares un posterior.

Aparte de eso, es razonablemente pythonico.

 def even_fib_sum(limit): a,b,sum = 0,1,0 while a <= limit: if a%2 == 0: sum += a a,b = b,a+b return sum print(even_fib_sum(4000000)) 

Usaría el generador de fibonacci como en la respuesta de @constantin ‘ pero las expresiones del generador podrían ser reemplazadas por un simple for bucle:

 def fibonacci(a=0, b=1): while True: yield a a, b = b, a + b sum_ = 0 for f in fibonacci(): if f > 4000000: break if f % 2 == 0: sum_ += f print sum_ 

Aquí hay un método directo alternativo. Se basa en algunas propiedades:

  1. Cada número de Fibonacci se puede calcular directamente como piso (potencia (phi, n) + 0.5) (Ver Cálculo por redondeo en http://en.wikipedia.org/wiki/Fibonacci_number ). Por el contrario, el índice del mayor número de Fibonacci menor que i viene dado por floor (log (i * sqrt (5)) / log (phi))
  2. La sum de los primeros N números de Fibonacci es el N + 2º número de fibonacci menos 1 (vea la Segunda Identidad en la misma página de wikipedia)
  3. Los números pares de Fibonacci son cada tercer número. (Mira la secuencia mod 2 y el resultado es trivial)
  4. La sum de los números de Fibonacci pares es la mitad de la sum de los números de Fibonacci impares hasta el mismo punto en la secuencia.

El punto 4 se puede ver desde esto:

 Sum of first 3N fibonacci numbers =(F(1) + F(2))+ F(3) +(F(4) + F(5))+ F(6) + ... +(F(3N-2) + F(3N-1))+ F(3N) = F(3) + F(3) + F(6) + F(6) + ... + F(3N) + F(3N) = 2( F(3) + F(6) + ... + F(3N) ) = 2 ( Sum of odd fibonacci numbers up to F(3N) ) 

Entonces, convierta nuestro valor máximo de 4000000 calcule el índice del número de Fibonacci más alto menos que este.

 int n = floor(log(4000000*sqrt(5))/log(phi)); // ( = 33) 

33 es divisible por 3, por lo que es un número de Fibonacci par, si no fuera así tendríamos que ajustar n de esta manera.

 n = (n/3)*3; 

La sum de todos los números de Fibonacci hasta este punto si está dada por

 sum = floor( pow( phi, n+2 ) + 0.5 ) - 1; // ( = 9227464 ) 

La sum de todos los números pares es la mitad de esto:

 sum_even = sum/2; // ( = 4613732 ) 

Lo bueno de esto es que es un algoritmo O (1) (u O (log (N)) si incluye el costo de poder / log), y funciona en dobles … así que podemos calcular la sum para valores muy grandes.

NOTA: edité y moví esta respuesta desde un duplicado cerrado de esta pregunta. Fibonacci bajo 4 millones

En Python 3, al menos, si asigna un generador a la función de sum , lo evaluará perezosamente, por lo que no es necesario reinventar la rueda.

Esto es lo que hizo @Constantin y es correcto.

Probado comparando el uso de memoria de usar generadores:

sum(range(9999999))

comparado con no hacerlo

sum(list(range(9999999)))

El que tiene el generador tampoco causa excepciones de memoria con números más altos.

 print ("Fibonacci Series\n") a = input ("Enter a nth Term: ") b = 0 x = 0 y = 1 print x,("\n"), y while b <=a-2: b = b+1 z = x + y print z x = y y = z 
 def main(): a = 1 b = 2 num = 2 while b < 4000000: a, b = b, a+b num += b if b % 2 == 0 else 0 print num if __name__ == '__main__': main()