programar - Programa de Python para encontrar series de Fibonacci. Más camino Ptónico

sucesion de fibonacci ejercicios

Question

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

Me encanta este programa que escribí para resolver el Proyecto Euler Q2. Estoy recién codificando en Python y me regocijo cada vez que lo hago ¡La manera Pythonic! ¿Puedes sugerir una mejor manera Pythonic para hacer esto?

Proyecto Euler Q2 . Encuentre la suma 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)

Answer 1

El uso de generadores es una forma pitonica de generar largas secuencias 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))

Answer 2

Haría los siguientes cambios:

• Usar 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 suma de los pares a posterior

Aparte de eso, es razonablemente pitónico.

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

Answer 3

Por un lado, sugiero resumir los términos a medida que los calcula en lugar de almacenarlos en una matriz y sumar la matriz después, ya que no es necesario hacer nada con los términos individuales que no sean sumarlos. (Eso es solo un buen sentido computacional en cualquier idioma)

Answer 4

Primero haría fibo () como generador:

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

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

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

Answer 5

En Python 3 al menos si le das un generador a la función sum , lo evaluará perezosamente para que no haya necesidad de reinventar la rueda.

Esto es lo que @Constantin hizo 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.

Answer 6

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

Answer 7

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

Answer 8

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

1. Cada número de Fibonacci puede calcularse directamente como piso (pow (phi, n) + 0.5) (Ver Computación por Rounding en http://en.wikipedia.org/wiki/Fibonacci_number ). Por el contrario, el índice del mayor número de Fibonacci menor que i está dado por piso (log (i * sqrt (5)) / log (phi))
2. La suma de los primeros N números de Fibonacci es el N + 2º número de Fibonacci menos 1 (Ver 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 suma de los números pares de Fibonacci es la mitad de la suma de los números impares de Fibonacci hasta el mismo punto en la secuencia.

El punto 4 se puede ver a partir de 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) )

Así que convierta nuestro valor máximo de 4000000 calcule el índice del número de Fibonacci más alto menos que él.

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

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

n = (n/3)*3;

La suma de todos los números de Fibonacci hasta este punto si es dada por

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

La suma 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) (o O (log (N)) si incluye el costo de pow / log), y funciona en dobles ... por lo que podemos calcular la suma para valores muy grandes.

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

Answer 9

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

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_