La suite de Fibonacci est un moyen amusant de continuer à pratiquer Python. Dans cet article, vous apprendrez à mettre en œuvre la suite de Fibonacci en Python en utilisant différentes techniques Python, depuis l'écriture de fonctions efficaces et la gestion de la récursivité jusqu'à l'utilisation des principes orientés objet pour des solutions plus optimisées. Lorsque vous aurez terminé, suivez notre cours Writing Functions in Python pour renforcer des concepts tels que la portée et la gestion des erreurs, ou essayez notre cours Intermediate Object-Oriented Programming in Python pour en savoir plus sur l'héritage et les classes de base. Essayons maintenant la séquence de Fibonacci. La suite de Fibonacci est un concept mathématique qui apparaît dans de nombreux domaines de la science et de la nature. Il s'agit d'une série de nombres où chaque nombre est la somme des deux précédents, en commençant par 0 et 1. Ce modèle constitue la base d'applications dans des domaines tels que l'informatique et la finance. Deux aspects principaux définissent la suite de Fibonacci : la structure récursive de la suite et sa relation avec le nombre d'or. La suite de Fibonacci commence par 0 et 1. Chaque nouveau nombre est la somme des deux nombres qui le précèdent. Par exemple : 0 + 1 = 1 1 + 1 = 2 1 + 2 = 3 2 + 3 = 5 3 + 5 = 8 5 + 8 = 13 Et ainsi de suite. Mathématiquement, nous l'écrivons sous la forme Ce modèle récursif sert de base à certains algorithmes en informatique. Par exemple, la récursivité en programmation utilise cette séquence pour résoudre des problèmes tels que la génération de nombres de Fibonacci ou la division de tâches en éléments plus petits et plus faciles à gérer. La suite de Fibonacci est étroitement liée au nombre d'or, un nombre irrationnel représenté par 5 ÷ 3 ≈ 1.666 8 ÷ 5 ≈ 1.6 13 ÷ 8 ≈ 1.625 Plus vous avancez, plus vous vous rapprochez de 1,618. Il ne s'agit pas d'une coïncidence : le ratio apparaît naturellement dans la séquence de Fibonacci en raison de la façon dont les nombres croissent. Euclide l'a décrite pour la première fois dans la Grèce antique comme le rapport entre l'extrême et la moyenne. Depuis lors, il a été associé à des motifs dans la nature, comme les spirales dans les coquillages et les fleurs, ainsi que dans l'art et l'architecture. Le nombre d'or dans l'art. Source La séquence de Fibonacci apparaît de manière surprenante dans de nombreux domaines. Concentrons-nous sur deux de ses applications les plus notables : ses modèles dans la nature et son utilisation en informatique. La séquence de Fibonacci est omniprésente dans la nature. Observez les fleurs : le nombre de pétales correspond souvent aux nombres de Fibonacci. Par exemple, les marguerites peuvent avoir 34, 55 ou 89 pétales, et les lys en ont souvent 3, 5 ou 8. Ces schémas aident les plantes à pousser de manière à maximiser la lumière du soleil et les précipitations. Les spirales des pommes de pin et des tournesols suivent également les nombres de Fibonacci. La disposition des graines dans un tournesol, par exemple, correspond à la séquence. Il est fascinant de constater qu'une chose aussi simple que l'addition de deux nombres peut décrire une si grande partie du monde naturel. La suite de Fibonacci joue également un rôle clé dans les algorithmes et les structures de données. Par exemple, les nombres de Fibonacci sont utilisés dans les algorithmes de recherche pour décomposer efficacement les problèmes en parties plus petites. La séquence est même à l'origine des tas de Fibonacci, un type de structure de données utilisé pour accélérer certaines opérations telles que la recherche du chemin le plus court dans un réseau. Voici un exemple simple de la manière dont vous pouvez générer une séquence de Fibonacci en Python : Cette fonction récursive montre comment la suite de Fibonacci est construite. Si la récursivité est facile à comprendre, il existe également des versions optimisées, comme la programmation dynamique, qui permettent de calculer les nombres de Fibonacci beaucoup plus rapidement. En cryptographie, les nombres de Fibonacci peuvent aider à générer des clés sécurisées. Dans le domaine de l'intelligence artificielle, ils optimisent les réseaux neuronaux afin d'améliorer la manière dont les algorithmes apprennent et s'adaptent. Voici quelques autres exemples de l'apparition de cette séquence dans la vie quotidienne et dans des domaines spécialisés : Comme Python propose plusieurs façons de générer la suite de Fibonacci, j'ai abordé les plus couramment utilisées, étape par étape, avec des exemples. La méthode itérative est l'une des façons les plus simples de générer la suite de Fibonacci. Elle utilise une boucle pour calculer chaque terme de la séquence, ce qui la rend plus efficace en termes de mémoire que les méthodes récursives. Voici comment cela fonctionne : Je fixe deux variables, Voici un code Python pour cela : Si vous souhaitez utiliser une boucle Les deux méthodes sont très faciles à comprendre, ce qui les rend parfaites pour les débutants. La méthode récursive est une autre façon de générer des nombres de Fibonacci. Cette méthode n'est pas aussi rapide que la méthode itérative pour les séquences plus importantes, mais c'est un excellent moyen de comprendre la logique qui sous-tend la construction de la séquence. Par exemple, je crée une fonction appelée Voici le code pour cela : Cette méthode fonctionne bien pour les petites séquences, mais peut devenir lente lorsque la séquence s'agrandit, car elle recalcule les mêmes valeurs plusieurs fois. Pour remédier à l'inefficacité de la récursion simple, j'utilise souvent la mise en cache. Le site Voici comment je procède : Cette approche combine la clarté de la récursion et l'efficacité de la mise en cache. Si vous cherchez d'autres façons de calculer les nombres de Fibonacci, voici quelques techniques plus avancées : L'exponentiation matricielle est l'une des méthodes les plus efficaces pour calculer les nombres de Fibonacci pour de grandes valeurs de Voici comment j'ai mis cela en œuvre en Python : Dans ce code, si La formule de Binet calcule directement le nombre de Fibonacci La formule est la suivante : Où ? Voici le code Python pour la formule de Binet : Dans ce code, la fonction Vous pouvez même utiliser des tableaux pour générer et stocker l'ensemble de la séquence de Fibonacci. Cette fonction est utile lorsque vous avez besoin de plusieurs termes simultanément. Voici le code pour cela : Le backtracking est une autre option que je pourrais utiliser, en particulier lorsque je souhaite combiner la récursion avec la mémoïsation pour de meilleures performances. Voici le code pour cela : Nous avons eu l'occasion d'en voir un certain nombre d'exemples ! Examinons maintenant leurs différences en termes de complexité temporelle et spatiale. Comme nous l'avons mentionné, certaines méthodes sont rapides mais utilisent plus de mémoire, tandis que d'autres sont plus lentes mais nécessitent moins d'espace. J'ai préparé ce tableau pour comparer l'efficacité de chaque approche. Dans le tableau ci-dessus, voici ce que signifie chaque complexité de temps et d'espace : Complexité temporelle O(n): L'algorithme parcourt la séquence une fois en effectuant un nombre fixe d'opérations pour chaque élément. Le temps nécessaire croît linéairement avec la taille de l'entrée O(1): Le nombre de Fibonacci est calculé à l'aide d'un nombre fixe d'opérations, sans itération ni récurrence. O(2n) : L'algorithme effectue deux appels récursifs pour chaque entrée, ce qui entraîne une croissance exponentielle du nombre d'appels de fonctions à mesure que O(log n): La durée d'exécution augmente proportionnellement au logarithme de la taille de l'entrée Complexité de l'espace O(n): L'algorithme utilise une mémoire qui croît directement avec le nombre d'entrées O(1) : L'utilisation de la mémoire reste constante quelle que soit la taille de l'entrée. O(2n): Il utilise un espace exponentiel en raison de la création de nouveaux états pour chaque branche. O(log n): Les multiplications intermédiaires de matrices utilisent une mémoire logarithmique. Comme vous l'avez vu, en Python, vous pouvez calculer les nombres de Fibonacci à l'aide de nombreuses méthodes différentes, allant de simples boucles à des techniques avancées comme l'exponentiation matricielle et la formule de Binet. Chaque méthode a ses avantages et ses inconvénients. J'espère que vous avez appris quelque chose à la fois sur la suite de Fibonacci mais aussi sur la programmation Python. Si vous souhaitez en savoir plus sur Python et d'autres sujets connexes, consultez notre cours d'introduction à Python. Vous pouvez également essayer notre cursus complet de développeur Python et apprendre les techniques de programmation et même commencer à développer vos propres paquets !Qu'est-ce que la séquence de Fibonacci ?
Nature récursive de la suite de Fibonacci
F(n) = F(n-1) + F(n-2). La séquence se construit en ajoutant de manière répétée les deux derniers chiffres. Les deux premiers nombres, 0 et 1, constituent le point de départ ou les cas de base. Sans cela, la séquence ne fonctionnerait pas.Connexion au nombre d'or
φ (sa valeur est d'environ 1,618). Si vous divisez un nombre de Fibonacci par celui qui le précède, le rapport se rapproche de plus en plus de φ. Par exemple :
Applications pratiques de la suite de Fibonacci
Fibonacci dans la nature
Fibonacci dans l'informatique
def fibonacci(n): if n <= 1: return n return fibonacci(n - 1) + fibonacci(n - 2)# Example usagefor i in range(10): print(fibonacci(i), end=" ")0 1 1 2 3 5 8 13 21 34Autres exemples courants
Implémentation de la séquence de Fibonacci en Python
Utiliser une méthode itérative
a et b, à 0 et 1. Ils représentent les deux premiers chiffres de la séquence. Ensuite, j'utilise une boucle for pour calculer les nombres suivants. Je mets à jour a pour qu'il contienne la valeur de b, et b devient la somme des précédents a et b.n = 10a, b = 0, 1for i in range(n): print(a) a, b = b, a + b0112358132134while au lieu d'une boucle for, voici comment vous pouvez écrire le code :# Number of terms to print in the Fibonacci seriesn = 10# Initialize the first two termsa, b = 0, 1i = 0while i < n: print(a, end=' ') # Update the terms a, b = b, a + b i += 10 1 1 2 3 5 8 13 21 34Utiliser une méthode récursive
fibonacci_recursive. Cette fonction prend un nombre n comme entrée. Si n est 0 ou 1, la fonction renvoie n. Ce sont les cas de base qui indiquent à la récursion quand s'arrêter. Pour tout autre nombre, la fonction s'appelle elle-même pour calculer les deux nombres précédents et les additionner.def fibonacci_recursive(n): if n <= 1: return n else: return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)num_terms = 10for i in range(num_terms): print(fibonacci_recursive(i), end=" ")0 1 1 2 3 5 8 13 21 34Utilisation d'une méthode récursive optimisée avec mise en cache
lru_cache de Python stocke les valeurs calculées précédemment afin que la fonction n'ait pas à refaire le travail.from functools import lru_cache@lru_cache(maxsize = None)def fib_cache(n): if n == 0: return 0 elif n == 1: return 1 else: return fib_cache(n-1) + fib_cache(n-2)print(f"The Fibonacci Number is {fib_cache(10)}")The Fibonacci Number is 55.Des façons plus avancées de réaliser la séquence de Fibonacci en Python
Exponentiation de la matrice
n. Au lieu de recalculer les termes à plusieurs reprises, cette méthode utilise la multiplication matricielle pour obtenir des résultats en temps logarithmique.import numpy as npdef fibonacci_matrix(n): def matrix_power(matrix, power): return np.linalg.matrix_power(matrix, power) if n == 0: return 0 matrix = np.array([[1, 1], [1, 0]]) result = matrix_power(matrix, n-1) return result[0][0]for i in range(10): print(fibonacci_matrix(i) , end=" ")0 1 1 2 3 5 8 13 21 34n est 0, il renvoie 0 comme cas de base. Pour d'autres valeurs, la matrice est élevée à la puissance (n-1) à l'aide de la fonction numpy matrix_power. Le nombre de Fibonacci à la position n se trouve dans l'élément supérieur gauche de la matrice résultante.Formule de Binet
nth sans itération ni récursion. Il est basé sur le nombre d'or, φ, et utilise une expression mathématique pour calculer le résultat instantanément.
import mathdef fibonacci_binet(n): phi = (1 + math.sqrt(5)) / 2 return round((phi ** n - (1 - phi) ** n) / math.sqrt(5))# Find the 10th Fibonacci numbern = 10result = fibonacci_binet(n)print(f" The Fibonacci Number of {n}th term is {result}" ) The Fibonacci number of 10th term is 55fibonacci_binet(n) calcule le nombre de Fibonacci nth à l'aide de la formule de Binet. Dans la fonction, je calcule phi (le nombre d'or) comme (1 + math.sqrt(5)) / 2, en utilisant math.sqrt() pour la racine carrée de 5. La formule (phi ** n - (1 - phi) ** n) / math.sqrt(5) est ensuite appliquée pour trouver directement le nombre de Fibonacci nth. Ensuite, j'utilise la fonction round() pour gérer les petites imprécisions en virgule flottante.Tableaux
def fibonacci(n): if n <= 0: return "Incorrect Output" data = [0, 1] # Initialize list with first two Fibonacci terms: 0 and 1 if n > 2: for i in range(2, n): # Start loop from the third term data.append(data[i-1] + data[i-2]) # Calculate next term as sum of previous two return data[n-1] # Return the nth termprint(f"Fibonacci Number: {fibonacci(10)}")Fibonacci number: 34Retour en arrière
def fibonacci_backtracking(n, computed ={0: 0, 1: 1}): if n in computed: return computed[n] computed[n] = fibonacci_backtracking(n - 1) + fibonacci_backtracking(n - 2) return computed[n]n = 10result = fibonacci_backtracking(n)print(f"The {n}th Fibonacci term is {result}")The 10th Fibonacci term is 55Complexité des algorithmes de Fibonacci en Python
Méthode Complexité temporelle Complexité de l'espace Itératif (boucle for) O(n) O(1) Itératif (boucle d'attente) O(n) O(1) Récursion simple O(2ⁿ) O(n) Mémoïsation/Caching O(n) O(n) Basé sur des tableaux O(n) O(n) Méthode du retour en arrière O(2ⁿ) O(2ⁿ) Exponentiation de la matrice O(log n) O(log n) n.n augmente.n.n. Ici, chaque élément nécessite un espace fixe.Réflexions finales
