Comment écrire la séquence de Fibonacci en Python

Question

J'avais initialement codé le programme à tort. Au lieu de retourner les nombres de Fibonacci entre une gamme (ie. startNumber 1, endNumber 20 = uniquement les numéros entre 1 et 20), j'ai écrit pour le programme pour l'affichage de tous les nombres de Fibonacci entre une gamme (ie. startNumber 1, endNumber 20 affiche = 20 Premiers nombres de Fibonacci). Je pensais que j'avais un sûr-code de prévention des incendies. Aussi je ne vois pas pourquoi ce qui se passe.

startNumber = int(raw_input("Enter the start number here "))
endNumber = int(raw_input("Enter the end number here "))

def fib(n):
    if n < 2:
        return n
    return fib(n-2) + fib(n-1)

print map(fib, range(startNumber, endNumber))

Quelqu'un l'a souligné dans ma Partie II (qui a été fermé pour être un doublon http://stackoverflow.com/questions/504193/how-to-write-the-fibonacci-sequence-in-python-part-ii) que j'ai besoin de passer le startNumber et endNumber par l'intermédiaire d'un générateur à l'aide d'une boucle while. Quelqu'un peut-il svp m'indiquer la direction sur la façon de faire cela? Toute aide est la bienvenue.

---

Je suis un apprentissage programmeur et j'ai couru dans un peu pêle-mêle. Je me demande d'écrire un programme qui permettra de calculer et d'afficher de Fibonacci de la Séquence par un utilisateur saisi numéro de début et de fin de numéro (ie. startNumber = 20 endNumber = 100 et il affiche uniquement les chiffres entre cette plage). L'astuce consiste à utiliser inclusivement (dont je ne sais pas comment le faire en Python? - Je suppose que cela signifie d'utiliser un large éventail?).

Ce que j'ai jusqu'ici n'est pas de codage réel, mais plutôt:

• Écrire Fib séquence de formule à l'infini
• Affichage startNumber à endNumber seulement à partir de Fib séquence.

Je n'ai aucune idée par où commencer et je vous demande des idées ou des indications sur la façon d'écrire cela. J'ai aussi essayé d'écrire le Fib séquence forumla mais je me suis perdu.

Je vous remercie pour l'aide. Je vais être de participer activement à cette question et vous remercions d'avance de TOUTE aide.

Answer 1

Il y a beaucoup d'informations à propos de la suite de Fibonacci sur wikipédia et sur wolfram. Beaucoup plus que vous pourriez avoir besoin. De toute façon c'est une bonne chose pour apprendre à utiliser ces ressources pour trouver (rapidement si possible) ce dont vous avez besoin.

Écrire Fib séquence de formule à l'infini

En mathématiques, il est donné sous une forme récursive:

Dans la programmation de l' infini n'existe pas. Vous pouvez utiliser une forme récursive de traduire les mathématiques formulaire directement dans votre langue, par exemple en python, il devient:

def F(n):
    if n == 0: return 0
    elif n == 1: return 1
    else: return F(n-1)+F(n-2)

Essayez-la dans votre langue préférée et voir ce formulaire nécessite beaucoup de temps que n est plus grand, en fait, c'est de O(2ⁿ) dans le temps.

Aller sur les sites que j'ai lié à vous et allez voir ceci (wolfram):

Celui-ci est assez facile à mettre en œuvre et très, très rapide à calculer, en Python:

def F(n):
    return ((1+sqrt(5))**n-(1-sqrt(5))**n)/(2**n*sqrt(5))

Une autre façon de le faire est à la suite de la définition (de wikipedia):

Le premier numéro de la séquence est de 0, le deuxième nombre est 1, et chaque le nombre est égal à la somme les deux numéros précédents de la séquence elle-même, cédant la séquence 0, 1, 1, 2, 3, 5, 8, etc.

Si votre langue prend en charge les itérateurs vous pouvez faire quelque chose comme:

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

Affichage startNumber à endNumber seulement à partir de Fib séquence.

Une fois que vous savez comment générer des Nombres de Fibonacci, vous avez juste à passer le nombre et vérifier si elles vérifient les conditions données.

Supposons maintenant que vous avez écrit a f(n) qui renvoie le n-ième terme de la suite de Fibonacci (comme celui avec sqrt(5) )

Dans la plupart des langues, vous pouvez faire quelque chose comme:

def SubFib(startNumber, endNumber):
    n = 0
    cur = f(n)
    while cur <= endNumber:
        if startNumber <= cur:
            print cur
        n += 1
        cur = f(n)

En python, je serais d'utiliser l'itérateur forme et aller pour:

def SubFib(startNumber, endNumber):
    for cur in F():
        if cur > endNumber: return
        if cur >= startNumber:
            yield cur

for i in SubFib(10, 200):
    print i

Mon astuce est d' apprendre à lire ce que vous avez besoin. Projet Euler (google) va vous former à faire :P Bonne chance et amusez-vous!

Answer 2

Réponse tardive, mais je m'amusais à essayer d'obtenir la représentation la plus courte de cet algorithme en Pythonic, et je n'ai remarqué personne d'autre qui ait proposé ma solution spécifique (bien que la réponse principale se rapproche, mais reste assez inélégante), alors voici c’est, avec des commentaires décrivant la première itération, parce que je pense que cela peut aider un lecteur donné:

 def fib():
    a, b = 0, 1
    while True:            # First iteration:
        yield a            # yield 0 to start with and then
        b, a = a + b, b    # b will be 1, and a will be 1.
 

et utilisation:

 for i, f in enumerate(fib()):
     print(i, f)
     if i > 10:
         break
 

impressions:

 (0, 0)
(1, 1)
(2, 1)
(3, 2)
(4, 3)
(5, 5)
(6, 8)
(7, 13)
(8, 21)
(9, 34)
(10, 55)
(11, 89)
 

Answer 3

Pourquoi ne pas simplement faire ce qui suit?

 x = [1,1]
for i in xrange(10):    
    x.append(x[-1] + x[-2]) 
print ', '.join(str(y) for y in x)
 

Answer 4

L'idée derrière la séquence de Fibonacci est indiqué dans le code Python suivant:

def fib(n):
   if n == 1:
      return 1
   elif n == 0:   
      return 0            
   else:                      
      return fib(n-1) + fib(n-2)

Cela signifie que le fib est une fonction qui permet de faire une des trois choses. Il définit fib(1) == 1, fib(0) == 0, et fib(n):

fib(n-1) + fib(n-2)

Où n est un entier arbitraire. Cela signifie que fib(2) par exemple, développe à la suite de l'arithmétique:

fib(2) = fib(1) + fib(0)
fib(1) = 1
fib(0) = 0
# Therefore by substitution:
fib(2) = 1 + 0
fib(2) = 1

Nous pouvons calculer fib(3) de la même façon avec l'arithmétique indiqué ci-dessous:

fib(3) = fib(2) + fib(1)
fib(2) = fib(1) + fib(0)
fib(2) = 1
fib(1) = 1
fib(0) = 0
# Therefore by substitution:
fib(3) = 1 + 1 + 0

La chose importante à réaliser est ici que fib(3) ne peut pas être calculé sans calcul de fib(2), qui est calculée en connaissant les définitions de fib(1) et fib(0). Avoir un appel de fonction comme la fonction de fibonacci n'est appelé la récursivité, et c'est un sujet important dans la programmation.

Cela sonne comme un devoir à la maison donc je ne vais pas vous faire le début/la fin de la partie pour vous. Python est un merveilleux langage expressif pour ce bien, ce qui devrait avoir un sens si vous comprenez bien les maths, et j'espère vous apprendre à propos de la récursivité. Bonne chance!

Edit: Un potentiel critique de mon code, c'est qu'il n'utilise pas le super-pratique Python fonction du rendement, ce qui rend la fib(n) la fonction beaucoup plus courte. Mon exemple est un peu plus générique, mais, depuis pas mal de langues en dehors du Python ont réellement le rendement.

Answer 5

Vous pouvez obtenir un bon point de départ ici:

• Numéros de Fibonacci (LiteratePrograms)

Vous avez suffisamment de matériel, une approche récursive, une approche itérative, la formule de Binet et des techniques de calcul de grands nombres individuels de Fibonacci ...