© Sashkin/Shutterstock.com
La suite de Fibonacci est sans aucun doute l’une des suites mathématiques les plus célèbres de tous les temps. Les mathématiciens et les scientifiques utilisent cette séquence depuis des siècles en mathématiques et en sciences, en la nommant d’après le célèbre mathématicien italien du Moyen Âge, Fibonacci.
La suite de Fibonacci est une série de nombres où chaque nombre suivant est la somme des deux précédents, en commençant par 0 et 1. La suite est souvent notée Fn et ressemble à ceci : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, etc.
Mais quel est le problème ? Pourquoi devrions-nous nous soucier de la suite de Fibonacci ? Eh bien, il s’avère que cette séquence n’est pas simplement une série arbitraire de nombres.
La suite de Fibonacci se trouve partout dans la nature et dans de nombreux domaines scientifiques, et elle a d’importantes applications en informatique et en programmation. L’importance de la série en informatique découle des divers algorithmes qui peuvent générer ses nombres.
Les langages de programmation comme Python ont des fonctions intégrées pour générer la séquence de Fibonacci. Si vous souhaitez comprendre les algorithmes derrière ces fonctions, restez dans les parages, car cet article expliquera 7 algorithmes et méthodes principaux utilisés pour générer les nombres de Fibonacci.
Différentes méthodes de création de programmes pour les nombres de Fibonacci
Plusieurs méthodes/approches existent pour générer des nombres de Fibonacci, chacune avec des complexités temporelles et spatiales variables. La façon la plus simple de trouver le nième nombre de Fibonacci est d’utiliser la récursivité.
Cependant, cette approche n’est pas très efficace et peut conduire à de nombreux calculs redondants. Nous allons donc explorer la récursivité aux côtés d’autres méthodes pour voir lesquelles peuvent être considérées comme les plus efficaces.
Récursivité
La récursivité est une méthode de résolution d’un problème où le La solution dépend des solutions aux instances plus petites du même problème. Dans le contexte de la séquence de Fibonacci, la solution récursive fonctionne en décomposant le problème de la recherche du nième nombre de Fibonacci en deux problèmes plus petits: trouver le (n-1)ème nombre de Fibonacci et trouver le (n-2)ème nombre de Fibonacci.
Ce processus se poursuit de manière récursive jusqu’à ce que le cas de base soit atteint, où n vaut 0 ou 1. Le cas de base représente la condition que la fonction doit satisfaire pour cesser de s’appeler. Une fois rencontrée, la fonction renvoie simplement n. Pour toutes les autres valeurs de n, la fonction s’appelle elle-même de manière récursive, en passant n-1 et n-2 comme arguments/paramètres.
L’exemple suivant montre un programme Python simple qui implémente la récursivité pour générer des nombres de Fibonacci :
def fibonacci(n) :
if n=1 : # cas de base
return n
else :
return fibonacci(n-1) + fibonacci(n-2)
print(fibonacci(7)) # Sortie : 13
La fonction vérifie d’abord le cas de base sur quoi il revient n. Si n est supérieur à 1, la fonction s’appelle elle-même de manière récursive avec n-1 et n-2 comme arguments et additionne leurs valeurs de retour. En effet, le n-ième nombre d’une séquence de Fibonacci est égal à la somme des (n-1)-ième et (n-2)-ième nombres de la séquence.
Les appels récursifs continuent jusqu’à ce que le cas de base soit atteint et que la fonction renvoie le nième nombre de la séquence. Nous pouvons obtenir la complexité temporelle de la solution récursive-elle est exponentielle étant O (2n), car la fonction s’appelle deux fois pour chaque valeur de n.
Cela peut rapidement devenir inefficace au fur et à mesure que n augmente, rendant cette méthode impraticable pour les grandes valeurs de n. La complexité spatiale est O(n), qui est linéaire, car la profondeur maximale de l’arbre de récursivité est n.
Itération
L’itération est une approche plus efficace pour résoudre la suite de Fibonacci problème. L’approche itérative consiste à résoudre un problème en exécutant à plusieurs reprises un ensemble d’instructions jusqu’à ce qu’une condition spécifique soit remplie.
Dans le contexte de la séquence de Fibonacci, la solution itérative fonctionne en commençant par les deux premiers nombres de Fibonacci et en calculant le prochain nombre de Fibonacci en utilisant les deux précédents. Ce processus se poursuit jusqu’à ce que le nième nombre de Fibonacci soit calculé.
La séquence de Fibonacci est apparue pour la première fois dans le manuscrit latin”Liber Abaci”(1202), où elle a été utilisée pour calculer la croissance des populations de lapins.
©TippaPatt/Shutterstock.com
Nous pouvons implémenter un programme simple utilisant l’itération pour créer des nombres de Fibonacci de la manière suivante :
def fibonacci(n) :
if n==0 :
return 0
elif n==1 :
return 1
else :
fib1, fib2=0, 1
pour i dans la plage (2, n+1) :
fib=fib1 + fib2
fib1, fib2=fib2, fib
return fib2
Ici, nous utilisons une boucle pour calculer le n-ième nombre de Fibonacci en temps linéaire. Nous y parvenons en commençant par les deux premiers nombres de la séquence (0 et 1) et en calculant de manière itérative le nombre suivant comme la somme des deux précédents.
Nous gardons une trace des deux nombres précédents dans des variables et les mettons à jour à chaque itération. Après n itérations, nous renvoyons le n-ième nombre.
La complexité temporelle de la solution itérative est O(n), qui est linéaire. En effet, la boucle for s’exécute n-1 fois pour calculer le nième nombre de Fibonacci. Comme la fonction n’utilise qu’un nombre constant de variables pour calculer le nième nombre de Fibonacci, sa complexité spatiale est O(1), qui est constante.
Mémoisation
Mémoisation est une méthode de résoudre un problème en stockant les résultats d’appels de fonction coûteux et en renvoyant le résultat mis en cache lorsque les mêmes entrées se reproduisent.
Dans le contexte de la séquence de Fibonacci, la solution de mémorisation fonctionne en stockant les solutions aux sous-problèmes et en renvoyant le résultat mis en cache, s’il est disponible.
De cette façon, le programme calcule la solution à chaque sous-problème une seule fois et le réutilise si nécessaire.
Voici un exemple d’implémentation de la mémorisation :
def fibonacci(n, memo={}) :
if n in memo :
return memo[n]
elif n=1 :
return n
else :
memo[n]=fibonacci(n-1, memo) + fibonacci(n-2, memo)
return memo[n]
Cet exemple utilise un sommet Approche descendante pour calculer le n-ième nombre de Fibonacci en mettant en cache les valeurs précédemment calculées pour éviter les calculs redondants. La fonction vérifie d’abord si elle a déjà calculé et mis en cache la valeur du n-ième nombre de Fibonacci dans un dictionnaire Python. Si c’est le cas, il renvoie la valeur mise en cache.
Si ce n’est pas le cas, il calcule la valeur de manière récursive comme la somme des (n-1)-ème et (n-2)-ème nombres de Fibonacci, met en cache la valeur calculée dans le dictionnaire, et le renvoie.
La complexité temporelle de la solution de mémorisation est O(n), qui est linéaire. En effet, le programme calcule chaque nombre de Fibonacci une seule fois et le stocke dans le dictionnaire de mémos pour une utilisation future. La complexité de l’espace est également O(n), qui est linéaire, car le dictionnaire de mémo stocke les solutions aux sous-problèmes jusqu’à n.
Programmation dynamique
La programmation dynamique est une méthode de résolution d’un problème en le décomposant en sous-problèmes plus petits et en stockant les solutions à ces sous-problèmes pour éviter des calculs redondants.
Dans le contexte de la séquence de Fibonacci, la solution de programmation dynamique fonctionne en calculant les nombres de Fibonacci de manière ascendante et en stockant les solutions dans un tableau. De cette façon, la solution à chaque sous-problème n’est calculée qu’une seule fois et réutilisée si nécessaire.
Considérez l’exemple suivant :
def fibonacci(n) :
fib=[0, 1]
for i in range(2, n+1):
fib.append(fib[i-1] + fib[i-2])
return fib[n]
La fonction utilise une liste Python pour stocker les valeurs calculées de la séquence, en commençant par les deux premières valeurs. Ensuite, il itère de 2 à n, en calculant la i-ième valeur comme la somme des (i-1)-ième et (i-2)-ième valeurs et en la stockant dans la liste. Enfin, il renvoie la n-ième valeur de la liste.
La complexité temporelle de la solution de programmation dynamique est O(n), qui est linéaire. La complexité temporelle de l’algorithme est O(n) car la boucle for calcule le nième nombre de Fibonacci en exécutant n-1 fois, et chaque calcul prend un temps constant.
De plus, la complexité spatiale de l’algorithme est O(n) car il utilise une liste de taille n pour stocker les solutions aux sous-problèmes.
Exponentiation matricielle
L’exponentiation matricielle est une méthode de résolution d’un problème en élevant une matrice à une puissance. Dans le contexte de la séquence de Fibonacci, la solution d’exponentiation matricielle fonctionne en utilisant une matrice avec des nombres de Fibonacci pour l’élever à la puissance n-1 pour obtenir le nième nombre de Fibonacci.
Nous pouvons utiliser l’exponentiation matricielle pour créez un programme Python pour les nombres de Fibonacci, comme indiqué :
import numpy as np
def fibonacci(n) :
F=np.array([[ 1, 1], [1, 0]])
return np.linalg.matrix_power(F, n-1)[0, 0]
Dans cet exemple, nous’re en utilisant une technique d’exponentiation matricielle pour calculer le n-ième nombre de Fibonacci en temps logarithmique. Pour ce faire, nous élevons une matrice 2×2 à la puissance n-1 et la multiplions par le vecteur d’état initial [0, 1]. La matrice résultante contient les n-ième et (n+1)-ième nombres de Fibonacci, et nous renvoyons le n-ième nombre.
La complexité temporelle de la solution d’exponentiation de la matrice est O(log n), qui est bien sûr logarithmique. L’algorithme diviser pour régner utilisé dans la multiplication matricielle réduit le nombre de multiplications nécessaires. Par conséquent, la complexité spatiale est O(1), qui est constante, car seule une quantité constante de mémoire est utilisée.
Formule de Binet
La formule de Binet est une formule directe pour calculer la nième nombre de Fibonacci sans avoir à calculer tous les nombres de Fibonacci précédents.
La formule s’écrit souvent : Fn=round((Φ^n – (1-Φ)^n)/√5), où Φ (phi) est le nombre d’or.
La formule de Binet suggère que le rapport de deux nombres de Fibonacci consécutifs tend vers le nombre d’or lorsque n augmente.
©TippaPatt/Shutterstock.com
Dans le contexte de la suite de Fibonacci, la formule de Binet fonctionne en utilisant le nombre d’or, qui est (1 + √5)/2, et son conjugué, qui est 1-√5)/2.
Un exemple en Python serait:
def fibonacci(n) :
golden_ratio=(1 + 5**0.5)/2
tour de retour((golden_ratio**n – (1 – golden_ratio)**n)/5**0.5 )
La fonction définit d’abord le nombre d’or. Ensuite, nous calculons le n-ième terme à l’aide de la formule de Binet et renvoyons la valeur entière arrondie du résultat.
Cette implémentation de la formule de Binet est efficace en termes de calcul car elle ne nécessite que quelques opérations arithmétiques simples pour calculer n’importe quel terme de la suite de Fibonacci, sans avoir besoin de calculer tous les termes précédents.
Ceci est prouvé par la complexité temporelle de la formule de Binet est O (1), qui est constante. En effet, la formule ne nécessite que quelques opérations arithmétiques pour calculer le nième nombre de Fibonacci. La complexité spatiale est O(1), qui est constante, car le programme n’utilise que quelques variables pour calculer le nième nombre de Fibonacci.
Algorithme glouton
L’algorithme glouton est une technique utilisé pour résoudre des problèmes d’optimisation. Cela fonctionne en prenant la meilleure décision à chaque étape et en espérant que les décisions prises mèneront à une solution optimale. Cet algorithme suit la stratégie”gourmande”consistant à toujours choisir le plus grand nombre possible à chaque étape.
On peut générer des nombres de Fibonacci en utilisant cette approche en commençant par les deux cas de base, puis en parcourant la série pour trouver le numéro suivant.
Tout d’abord, enregistrez les deux nombres précédents dans deux variables, puis additionnez-les pour obtenir le prochain nombre de Fibonacci. Ce processus se poursuit jusqu’à ce que le nième nombre de la séquence soit généré.
Nous pouvons implémenter un programme pour les nombres de Fibonacci en utilisant l’algorithme Greedy de manière simple, comme suit :
def fibonacci(n) :
if n=1 :
return n
prev, curr=0, 1
for i in range(2, n+1):
prev, curr=curr, prev + curr
return curr
Nous vérifions d’abord si n satisfait le cas de base , auquel cas nous avons renvoyé la valeur appropriée. Sinon, nous créons une liste pour stocker les deux nombres de Fibonacci précédents (0 et 1), puis utilisons une boucle pour générer les nombres suivants dans la séquence en ajoutant les deux derniers nombres de la liste. La boucle continue jusqu’à ce que le n-ième numéro de la séquence soit généré, auquel cas nous le renvoyons.
La complexité temporelle de l’algorithme glouton est O(n), qui est linéaire, car nous devons itérer n fois pour générer le n-ième numéro de la séquence. La complexité spatiale est également O(n), car nous devons stocker les deux nombres précédents dans la séquence pour chaque itération de la boucle.
Cependant, nous pourrions optimiser la complexité de l’espace en ne stockant que les deux nombres précédents au lieu de tous les nombres générés jusqu’à présent.
Arrondir
La suite de Fibonacci est un concept mathématique important et intemporel avec de nombreuses applications en informatique et en programmation. Avec le bon algorithme, vous pouvez générer rapidement et facilement n’importe quel nombre de Fibonacci.
D’une manière générale, l’itération et la programmation dynamique sont les algorithmes les plus efficaces en termes de complexité temporelle et spatiale, tandis que l’exponentiation matricielle est la plus efficace en termes de complexité temporelle pour les grandes valeurs de n. La récursivité est la plus intuitive mais aussi la moins efficace en termes de complexité temporelle et de complexité spatiale.
Au final, le meilleur algorithme à utiliser dépend du problème à traiter. Il est donc important de les comprendre pour savoir quand utiliser chaque méthode pour optimiser les performances de vos programmes de Fibonacci.
Programme pour les nombres de Fibonacci avec exemples FAQ (Foire aux questions)
Spirale d’Archimède, nombre d’or, séquence de Fibonacci : quel est le lien ?
La spirale d’Archimède et la séquence de Fibonacci peuvent être liées par le nombre d’or.
La le nombre d’or est une constante mathématique qui est égale au rapport de deux nombres dans la suite de Fibonacci. Ce rapport peut également être trouvé sous la forme de la spirale d’Archimède.
Par conséquent, les trois concepts sont interdépendants et ont des applications importantes en mathématiques, en sciences et en art.
Quelle est la différence entre la récursivité et l’itération lors de la génération de nombres de Fibonacci ?
La récursivité est une technique dans laquelle une fonction s’appelle elle-même pour résoudre un problème, tandis que l’itération est une structure en boucle qui répète un ensemble de instructions jusqu’à ce qu’une certaine condition soit remplie.
La récursivité est l’approche la plus simple pour générer des nombres de Fibonacci, mais elle est inefficace en raison de sa complexité temporelle exponentielle. L’itération est plus efficace et peut calculer le n-ième nombre en temps linéaire.
Comment la séquence de Fibonacci est-elle appliquée à l’informatique et à la programmation ?
La La séquence de Fibonacci a de nombreuses applications, telles que les algorithmes de génération de nombres aléatoires, de graphiques, d’arbres, d’algorithmes de tri et de compression de données. De plus, la séquence de Fibonacci est utilisée en cryptographie et dans l’analyse des performances des algorithmes.
Quelle est la signification de la séquence de Fibonacci ?
C’est souvent utilisé pour modéliser les modèles de croissance dans la nature, tels que la ramification des arbres, la disposition des feuilles sur une tige et les spirales dans un coquillage ou une pomme de pin. Il est également utilisé dans l’analyse technique pour prédire les tendances du marché et dans la cryptographie pour générer des nombres aléatoires.
Quels sont quelques exemples de nombres de Fibonacci dans la nature et l’art ?
Le nombre d’or se retrouve dans de nombreux phénomènes naturels comme les spirales de certaines plantes et animaux (par exemple, les ananas, les tournesols, les coquillages, etc.).
On le retrouve également dans certaines structures comme le Parthénon à Athènes, en Grèce, de la musique comme la Cinquième Symphonie de Beethoven, de l’art comme la Joconde de Léonard de Vinci et de l’astronomie comme les orbites des planètes autour des étoiles.