La série de Fibonacci a été découverte par le mathématicien italien Leonardo Fibonacci en 1202 et même plus tôt par des mathématiciens indiens. La série apparaît dans des domaines inattendus tels que l'économie, les mathématiques, l'art et la nature.
Esquisse d'algorithme
Dans ce qui suit, nous donnons un algorithme simple pour calculer les nombres de Fibonacci.
La série commence par les nombres de Fibonacci zéro et un. L'algorithme calcule l'élément suivant de la série comme la somme des deux derniers éléments. Pour cela, l'algorithme doit garder une trace uniquement des deux derniers éléments de la série. Ainsi, nous maintenons deux variables a et b , étant respectivement l'avant-dernier et le dernier élément de la série.
Ce calcul se répète pendant 10 itérations en utilisant un for standard boucle :
# Algorithm to Computer
# Fibonacci Series
a, b = 0, 1
for i in range(10):
print(b)
a, b = b, a+b
La sortie sont les 10 premiers nombres de Fibonacci :
1 1 2 3 5 8 13 21 34 55
Pour plus de clarté dans le code, nous avons utilisé la fonctionnalité linguistique des devoirs multiples dans la première et la dernière ligne.
Cette fonction fonctionne comme suit.
- Sur le côté gauche de l'affectation, il existe une séquence de variables telle qu'une liste ou un tuple.
- Sur le côté droit de l'affectation, nous précisons les valeurs à affecter à ces variables.
Les deux séquences à gauche et à droite doivent avoir la même longueur. Sinon, l'interpréteur Python renverra une erreur.
Notez que toutes les expressions du côté droit sont d'abord évaluées avant d'être affectées. C'est une propriété importante pour notre algorithme. Sans cette propriété, la dernière ligne serait erronée car l'expression a+b considérerait la mauvaise valeur pour a .
Comment stocker les n premiers nombres de Fibonacci dans une liste ?
Récapitulons, la série de Fibonacci est la série de nombres qui apparaît lors de l'addition répétée des deux derniers nombres à partir de 0 et 1. Voici un algorithme qui stocke les n premiers nombres de Fibonacci dans une liste et renvoie la liste :
def fibo(n):
result = []
a, b = 0, 1
while a < n:
result.append(a)
a, b = b, a+b
return result
fib100 = fibo(100)
print(fib100[-1]== fib100[-2]+fib100[-3])
# True
Le fibo la fonction dans le code calcule tous les nombres de Fibonacci jusqu'à l'argument de la fonction n .
Encore une fois, nous utilisons la méthode concise des affectations multiples pour stocker la valeur de b dans la variable a et de calculer la nouvelle valeur de b comme la somme des deux. On maintient toute la séquence dans la variable liste result en ajoutant la valeur de séquence a à la fin de la liste.
Le code calcule la suite de Fibonacci jusqu'à 100 et stocke toute la liste dans la variable fib100 . Mais pour comprendre le code, vous n'avez pas besoin de calculer toute la séquence. L'instruction d'impression compare uniquement si le dernier élément est égal à la somme de l'avant-dernier et de l'avant-dernier élément de la séquence. Ceci est vrai par définition de la série de Fibonacci.
Un puzzle Python simple sur la série Fibonacci
Pouvez-vous résoudre l'énigme suivante concernant l'algorithme de Fibonacci ?
Êtes-vous un codeur maître?
Testez vos compétences maintenant !
Regardez la vidéo associée Fibonacci One-Liner
J'adore les one-liners. À tel point que j'ai écrit un livre Python One-Liners sur la façon de compresser le code Python en une seule ligne de code Python. Il s'avère que vous pouvez exprimer l'algorithme de Fibonacci en une seule ligne de code. Regardez la vidéo pour voir comment !
Le code en une ligne pour calculer les nombres de Fibonacci sur une seule ligne est le suivant :
# Dependencies from functools import reduce # The Data n = 10 # The One-Liner fibs = reduce(lambda x, _: x + [x[-2] + x[-1]], [0] * (n-2), [0, 1]) # The Result print(fibs)
Vous pouvez lire une explication détaillée dans mon tutoriel complet.
Tutoriel associé : L'algorithme de Fibonacci dans une seule ligne de code Python
Vidéo explicative basée sur les mathématiques Fibonacci
Maintenant que vous avez tout appris sur l'algorithme de Fibonacci, je suis sûr que vous voulez tester vos compétences !
Un puzzle Python avancé sur Fibonacci
Le puzzle suivant est un puzzle de Fibonacci de niveau avancé. Pouvez-vous le résoudre ?
Êtes-vous un codeur maître?
Testez vos compétences maintenant !
