Programma Python per trovare serie di fibonacci. Più modo Pythonic

Question

C'è un altro thread per discutere le serie di Fibo in Python. Questo è quello di modificare il codice in più pythonic. How to write the Fibonacci Sequence in Python

Sono innamorato di questo programma che ho scritto per risolvere Project Euler Q2. Sto codificando di recente in Python e mi rallegro ogni volta che lo faccio. Il modo Pythonic! Puoi suggerire un modo Pythonic migliore per farlo?

Project Euler Q2. Trova la somma di tutti i termini con valore pari nella sequenza di Fibonacci che non superano i quattro milioni.

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

Prima farei fibo() come generatore:

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

Poi' d anche selezionare per uniformità come un generatore piuttosto che una lista di comprensione.

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

Answer 2

Per prima cosa, vorrei suggerire riassumendo i termini come li si calcola, piuttosto che la loro memorizzazione in un array e sommando l'array in seguito, dal momento che non c'è bisogno di fare nulla con i singoli termini diversi aggiungendoli. (Questo è solo buon senso computazionale in qualsiasi lingua)

Answer 3

vorrei fare le seguenti modifiche:

• Uso iterazione invece di ricorsione
• Basta tenere un totale parziale invece di mantenere un elenco di tutti i numeri di Fibonacci e poi trovare la somma delle anche quelle un posteriore

oltre a questo, è ragionevolmente Pythonic.

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 4

Utilizzando generatori è un modo Pythonic per generare sequenze lunghe preservando 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 5

userei il generatore di Fibonacci come in @constantin' answer ma espressioni generatore potrebbe essere sostituito da una pianura for ciclo:

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_ 

Answer 6

Ecco un metodo diretto alternativo Esso si basa su alcune proprietà:

1. Ogni numero di Fibonacci può essere calcolato direttamente come floor (pow (phi, n) + 0.5) (Vedere Calcolo arrotondando http://en.wikipedia.org/wiki/Fibonacci_number). Viceversa l'indice del più grande numero di Fibonacci minore di I è dato da floor (log (i * sqrt (5))/log (phi))
2. La somma dei primi numeri N Fibonacci è il numero N + 2 ° di fibonacci meno 1 (Vedi Seconda identità sulla stessa pagina di Wikipedia)
3. I numeri pari di Fibonacci sono ogni terzo. (Guarda la sequenza mod 2 e il risultato è banale)
4. La somma dei numeri pari di Fibonacci è la metà della somma dei numeri dispari di Fibonacci fino allo stesso punto della sequenza.

punto 4 può essere visto da questo:

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

Quindi convertire il nostro valore massimo di 4000000 calcolare l'indice del più alto numero di Fibonacci meno di esso.

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

33 è divisibile per 3, quindi è un numero pari di Fibonacci, se non fosse stato avremmo bisogno di regolare n come questo.

n = (n/3)*3; 

La somma di tutti i numeri di Fibonacci fino a questo punto, se data dal

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

La somma di tutti i numeri è la metà di questo:

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

cosa bella di questo è che è un algoritmo O (1) (o O (log (N)) se si include il costo di pow/log) e funziona su doppio .. quindi possiamo calcolare la somma per valori molto grandi.

NOTA: ho modificato e spostato questa risposta da un duplicato chiuso di questa domanda. Fibonacci under 4 millions

Answer 7

In Python 3 almeno se si fornisce un generatore alla funzione sum, lo valuterà pigramente, quindi non è necessario reinventare la ruota.

Questo è ciò che @Constantin ha fatto ed è corretto.

verificata confrontando l'utilizzo della memoria utilizzando generatori:

sum(range(9999999))

rispetto non farlo:

sum(list(range(9999999)))

Quello con il generatore non causa eccezioni di memoria con maggiore numeri entrambi.

Answer 8

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 9

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