J'avais initialement codé le programme de manière incorrecte. Au lieu de renvoyer les nombres de Fibonacci entre une plage (par exemple, startNumber 1, endNumber 20 devrait = seulement les nombres entre 1 & ; 20), j'ai écrit pour que le programme affiche tous les nombres de Fibonacci entre une plage (par exemple, startNumber 1, endNumber 20 affiche = les 20 premiers nombres de Fibonacci). Je pensais avoir un code infaillible. Je ne vois pas non plus pourquoi cela se produit.
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 m'a fait remarquer dans ma deuxième partie (qui a été fermée pour cause de doublon - https://stackoverflow.com/questions/504193/how-to-write-the-fibonacci-sequence-in-python-part-ii) que je dois faire passer le startNumber et le endNumber par un générateur en utilisant une boucle while. Quelqu'un peut-il m'indiquer comment faire ? Toute aide est la bienvenue.
J’apprends à programmer et je me retrouve un peu dans le pétrin. On me demande d'écrire un programme qui calculera et affichera la séquence de Fibonacci en fonction d'un nombre de départ et d'un nombre d'arrivée saisis par l'utilisateur (par exemple, nombre de départ = 20 nombre d'arrivée = 100 et il n'affichera que les nombres compris dans cette plage). L'astuce consiste à l'utiliser de manière inclusive (ce que je ne sais pas faire en Python ? - Je suppose que cela signifie utiliser une plage inclusive).
Ce que j'ai jusqu'à présent n'est pas un codage réel mais plutôt :
Je n'ai aucune idée de par où commencer et je demande des idées ou un aperçu de la façon d'écrire ceci. J'ai également essayé d'écrire la formule de la séquence Fib, mais je suis perdue là aussi.
Vous trouverez de nombreuses informations sur la séquence de Fibonacci sur [wikipedia][1] et sur [wolfram][2]. Bien plus que ce dont vous pourriez avoir besoin. Quoi qu'il en soit, il est bon d'apprendre à utiliser ces ressources pour trouver (rapidement si possible) ce dont vous avez besoin.
En mathématiques, elle est donnée sous une forme récursive :
En programmation, infini n'existe pas. Vous pouvez utiliser une forme récursive traduisant la forme mathématique directement dans votre langage, par exemple en Python cela devient :
def F(n):
if n == 0: return 0
elif n == 1: return 1
else: return F(n-1)+F(n-2)
Essayez-le dans votre langage préféré et voyez que cette forme nécessite beaucoup de temps lorsque n devient plus grand. En fait, c'est O(2n) en temps.
Allez sur les sites que je vous ai indiqués et vous verrez ceci (sur wolfram) :
[!Equation de Fibonacci][4]][4]
Celle-ci est assez facile à implémenter et très, très rapide à calculer, en Python :
from math import sqrt
def F(n):
return ((1+sqrt(5))**n-(1-sqrt(5))**n)/(2**n*sqrt(5))
Une autre façon de le faire est de suivre la définition (de wikipedia) :
Le premier nombre de la séquence est 0, le second nombre est 1, et chaque nombre suivant est égal à la somme des deux nombres précédents de la séquence elle-même. séquence elle-même, ce qui donne la séquence 0, 1, 1, 2, 3, 5, 8, etc.
Si votre langage supporte les itérateurs, vous pouvez faire quelque chose comme :
def F():
a,b = 0,1
while True:
yield a
a, b = b, a + b
Une fois que vous savez comment générer des nombres de Fibonacci, il vous suffit de parcourir les nombres et de vérifier s'ils vérifient les conditions données.
Supposons maintenant que vous ayez écrit une fonction f(n) qui renvoie le n-ième terme de la séquence de Fibonacci (comme celle avec sqrt(5) )
Dans la plupart des langages, 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, j’utiliserais la forme de l’itération et je ferais :
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 conseil est d'apprendre à lire ce dont vous avez besoin. Le projet Euler (cherchez-le sur Google) vous apprendra à le faire :P Bonne chance et amusez-vous bien !
[1] : http://en.wikipedia.org/wiki/Fibonacci_number [2] : http://mathworld.wolfram.com/FibonacciNumber.html
L'idée de la séquence de Fibonacci est illustrée 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 fib est une fonction qui peut faire l'une des trois choses suivantes. Elle définit fib(1) == 1, fib(0) == 0, et fib(n) comme étant :
fib(n-1) + fib(n-2)
où n est un nombre entier arbitraire. Cela signifie que fib(2) par exemple, s'étend à l'arithmétique suivante :
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 manière avec l'arithmétique suivante :
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
Ce qu'il est important de comprendre ici, c'est que la fonction fib(3) ne peut être calculée sans calculer la fonction fib(2), qui est calculée en connaissant les définitions de fib(1) et fib(0). Le fait qu'une fonction s'appelle elle-même comme le fait la fonction fibonacci s'appelle la récursion, et c'est un sujet important en programmation.
Cela ressemble à un devoir à la maison, je ne vais donc pas faire la partie début/fin pour vous. Python est un langage merveilleusement expressif pour cela, donc cela devrait avoir du sens si vous comprenez les maths, et j'espère que vous apprendrez ce qu'est la récursion. Bonne chance !
Edit : Une critique potentielle de mon code est qu’il n’utilise pas la très pratique fonction Python yield, qui rend la fonction fib(n) beaucoup plus courte. Mon exemple est cependant un peu plus générique, puisque peu de langages en dehors de Python disposent de yield.