Fibonacci de moins de 4 millions

Question

Possible en double:
Python program to find fibonacci series. More Pythonic way.

Hey, je tentais d'écrire un script qui résume tous les même termes "séquence de Fibonacci" de moins de 4 millions.

Fibonacci1 = 1 
Fibonacci2 = 2 
a = 2 
i = 4 
for i in range(1,4000000): 
Fibonacci1 = Fibonacci1 + Fibonacci2 
if Fibonacci1 % 2 == 0: 
    a = a + Fibonacci1 
Fibonacci2 = Fibonacci1 + Fibonacci2 
if Fibonacci2 % 2 == 0: 
    a = a + Fibonacci2 
print a 
raw_input() 

cela devrait prendre moins d'une minute, mais cela a pris toute la nuit et il n'a pas été résolu!

---

Edit: Désolé les gars, j'ai mal compris le problème. Je pense que cela signifie que je dois résumer tous les termes pairs jusqu'à 4 millions! Mais la solution était de faire la somme de tous les termes pairs jusqu'à 4 millions.

Code de travail (terminé en moins d'une seconde):

Fibonacci1 = 1 
Fibonacci2 = 2 
a = 2 
while a < 4000000: 
Fibonacci1 = Fibonacci1 + Fibonacci2 
if Fibonacci1 % 2 == 0: 
    a = a + Fibonacci1 
Fibonacci2 = Fibonacci1 + Fibonacci2 
if Fibonacci2 % 2 == 0: 
    a = a + Fibonacci2 
print a 
raw_input() 

Answer 1

La condition de la boucle est mauvaise, il devrait être quelque chose comme ceci:

while True: 
    Fibonacci1 = Fibonacci1 + Fibonacci2 
    if Fibonacci1 % 2 == 0: 
     if a + Fibonacci1 > 4000000: 
      break 
     a = a + Fibonacci1 
    Fibonacci2 = Fibonacci1 + Fibonacci2 
    if Fibonacci2 % 2 == 0: 
     if a + Fibonacci2 > 4000000: 
      break 
     a = a + Fibonacci2 

Answer 2

Etes-vous sûr qu'il est i que vous voulez être inférieur à 4 millions?

Answer 3

Actuellement, vous résumez tous les 2 premiers millions même les nombres de Fibonacci.

Mais ce n'est pas la tâche. Vous devez totaliser tous les nombres de Fibonacci inférieurs à 4 millions.

Answer 4

Je ne comprends pas exactement votre algorithme, mais il semble que smerriman a un point, 4000000 numéros de séquence Fibonnacci se développerait sûrement au-dessus de 4M. Je suppose que l'approche la plus rapide serait de générer une séquence jusqu'à 4M, puis d'additionner les paires.

Answer 5

Il y a quelques problèmes avec votre code:

• Vous quatre millions de fois en boucle au lieu de jusqu'à ce qu'une condition est vraie.
• Vous avez du code répété dans le corps de votre boucle.

La plupart des gens lorsqu'ils commencent à apprendre Python n'apprennent que la programmation impérative. Ce n'est pas surprenant car Python est un langage impératif. Mais Python soutient également la programmation fonctionnelle dans une certaine mesure et pour ce genre d'exercice, une approche de programmation fonctionnelle est plus éclairante à mon avis.

d'abord définir un générateur qui génère tous les nombres de Fibonacci:

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

Pour utiliser ce générateur, nous pouvons importer quelques fonctions utiles de itertools.Pour imprimer les premiers numéros utilisent islice:

from itertools import ifilter, islice, takewhile 

for x in islice(fib(), 5): 
    print x 

 
1 
1 
2 
3 
5 

Pour trouver seulement les même chiffres que nous pouvons utiliser ifilter pour produire un nouveau générateur:

def is_even(x): 
    return x % 2 == 0 

evenfibs = ifilter(is_even, fib()) 

for x in islice(evenfibs, 5): 
    print x 

 
2 
8 
34 
144 
610 

Pour récupérer les numéros de la générateur jusqu'à ce qu'un nombre dépasse quatre millions d'utilisation takewhile:

for x in takewhile(lambda x: x < 4000000, evenfibs): 
    print x 

Pour résoudre le problème, vous pouvez utiliser la somme:

sum(list(takewhile(lambda x: x < 4000000, evenfibs))) 

J'espère que cela montre qu'une approche de programmation fonctionnelle est difficile et est une façon plus élégante de résoudre certains types de problèmes.

Answer 6

NOTE: Cela a été fortement modifié pour répondre à la question réelle

Voici un autre (et très rapide, mais non testé, méthode). Elle repose sur quelques propriétés:

1. Chaque numéro de Fibonacci peut être calculé directement étage (pow (phi, n) + 0,5) (Voir Calcul par Arrondi en http://en.wikipedia.org/wiki/Fibonacci_number). Inversement l'indice du plus grand nombre de Fibonacci inférieur à i est donné par floor (log (i * sqrt (5))/log (phi))
2. La somme des premiers nombres de N Fibonacci est le N + 2 ème nombre de fibonaccus moins 1 (Voir la deuxième identité sur la même page wikipedia)
3. Les nombres pairs de Fibonacci sont tous les trois nombres. (Regardez la séquence mod 2 et le résultat est trivial)
4. La somme des nombres pairs de Fibonacci est la moitié de la somme des nombres impairs de Fibonacci jusqu'au même point de la séquence. (Ceci résulte de 3. et la propriété que F (3N) = F (3N-1) + F (3N-2) donc F (3N-2) + F (3N-1) + F (3N) = 2 F (N) .. puis en additionnant les deux côtés.

convertir donc notre valeur maximum de 4.000.000 calculer l'indice du nombre de Fibonacci le plus moins que lui.

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

33 est divisible par 3 il est un nombre pair de Fibonacci, si ce ne nous aurions besoin d'ajuster n comme celui-ci.

n = (n/3)*3 

La somme d'al l nombres de Fibonacci jusqu'à ce point si on leur donne par

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

La somme de tous les nombres pairs est la moitié de celle-ci:

sum_even = 4613732 

chose à ce sujet est que son un O (1) (ou O (log (N)) si vous incluez le coût de l'algorithme pow/log), et travaille sur les doubles .. ainsi nous pouvons calculer la somme pour de très grandes valeurs.

Answer 7

Allez, la meilleure façon de calculer la séquence de Fibonacci utilise 2 tours:

ÉDITÉE, désolé plus tôt erreur

1:

N =|2 0 0| 
    |1 0 0| 
    |0 0 0| 

M =|3 2 1| 
    |2 1 0| 
    |0 0 1| 

Matrix N * M^(n/3) a la somme des n premiers nombres de fibonacci (filtré seulement aux pairs) est l'élément supérieur droit.

2:

Vous pouvez utiliser http://en.wikipedia.org/wiki/Exponentiation_by_squaring, car la multiplication de la matrice est un anneau.

Vous pouvez résoudre notre problème en O (log n)

Answer 8

Il y a d'autres trucs qui font de ce plus efficace que le simple calcul de la liste complète des numéros de Fibonacci, puis en additionnant les nombres pairs dans la liste.

Je voudrais, si c'était moi qui essaie de résoudre ce problème, faire une liste des nombres pairs de Fibonacci. Y a-t-il des caractéristiques intéressantes de cette liste? Pouvez-vous vous convaincre que ce modèle est vrai en général?

Ensuite, je pourrais chercher un moyen de calculer les membres de cette liste, et seulement les éléments qui sont nécessaires. Je pourrais même regarder s'il y a des formules à trouver qui donnent la somme d'une suite de nombres de Fibonacci. Bien sûr, tout cela prendrait plus de temps que de coder simplement la solution force brute, mais Project Euler a pour but de trouver la solution plutôt que la solution brute force. En fin de compte, si vous avez appris quelque chose sur les mathématiques, sur le calcul, alors vous avez gagné.

Answer 9

Vous pouvez être intéressé à connaître la The On-Line Encyclopedia of Integer Sequences!

Vous pouvez rechercher des informations par nom ou par séquence.

Si vous recherchez soit pour 0,2,8,34 ou « Même Fibonacci », vous allez être redirigé vers la séquence A014445

vous vous y trouver beaucoup d'informations, y compris les formules,
de celui coder un générateur qui donnera directement les nombres de fibonacci même est facile.

def evenfib(): 
    """ Generates the even fibonacci numbers """ 
    a, b = 2, 0 
    while True: 
     a, b = b, a+4*b 
     yield a 

Answer 10

## nice simple generator Mark Byers 
def fib(): 
    a = b = 1 
    while True: 
     yield a 
     a, b = b, a + b 

## does same as takewhile 5 
for fibonacci in zip(range(1,1+5),fib()): 
    print "fib(%i) = %i" % fibonacci 

## we can slice to take every second 
print "even sequence upto 100th" 
total=0 
for fibonacci in zip(range(1,1+100),fib())[::2]: 
    print "fib(%i) = %i" % fibonacci 
    total+=fibonacci[1] ## to double check 
print "Has sum: ", sum(b for a,b in zip(range(1,1+100),fib())[::2]),'that is ',total 

print "odd sequence upto 100th" 

total=0 
for fibonacci in zip(range(1,1+100),fib())[1::2]: 
    print "fib(%i) = %i" % fibonacci 
    total+=fibonacci[1] ## to double check 

print "Has sum: ", sum(b for a,b in zip(range(1,1+100),fib())[1::2]),'that is ',total