Série de Fibonacci en Python | Code, Algorithme et Plus

Série de Fibonacci en Python

Introduction

La série de Fibonacci en python est une séquence mathématique qui commence par 0 et 1, chaque nombre suivant étant la somme des deux précédents. En Python, générer la série de Fibonacci n’est pas seulement un exercice de programmation classique mais aussi un excellent moyen d’explorer les solutions récursives et itératives.

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2) pour n > 1

Qu’est-ce que la série de Fibonacci?

La série de Fibonacci est une séquence où chaque nombre est la somme des deux nombres précédents, en commençant par 0 et 1.

Envie d’apprendre Python gratuitement? Explorez notre cours gratuit dès aujourd’hui!

Formule mathématique pour la séquence de Fibonacci

La formule mathématique pour calculer la séquence de Fibonacci est :

• Un pilier de RL – TD(λ) et 3 grands noms
• Aperçu des algorithmes de tri Tri fusion
• Aperçu des algorithmes de tri Tri par tas

F(n) = F(n-1) + F(n-2)

Où :

• F(n) est le nième nombre de Fibonacci
• F(n-1) est le (n-1)ème nombre de Fibonacci
• F(n-2) est le (n-2)ème nombre de Fibonacci

Définition récursive

La définition récursive de la série de Fibonacci dépend du système récursif.

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2) pour n > 1

Ainsi, chaque nombre dans la série de Fibonacci est calculé en incluant les deux nombres qui le précèdent. Cette méthode récursive continue à générer toute la séquence, en commençant par 0 et 1.

Lire aussi: Top 10 Utilisations de Python dans le Monde Réel avec des Exemples

Série de Fibonacci récursive en Python

Calcul des nombres de Fibonacci de manière récursive en Python en utilisant des fonctionnalités récursives. Voici un code Python pour calculer le nième nombre de Fibonacci en utilisant la récursion :

Def fibonacci(n):
    if n <= 0:
        return 0 
    elif n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci (n-2)
#import csv

Série de Fibonacci itérative en Python

Une méthode itérative pour calculer les nombres de Fibonacci en Python consiste à utiliser des boucles pour construire la séquence de manière itérative.

Algorithme itératif de Fibonacci en Python :

def fibonacci_iterative(n):
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    Else:
        fib_prev = 0  # Initialiser le premier nombre de Fibonacci
        fib_current = 1  # Initialiser le deuxième nombre de Fibonacci
        For _ in range(2, n + 1):
            fib_next = fib_prev + fib_current  # Calculer le prochain nombre de Fibonacci
            fib_prev, fib_current = fib_current, fib_next  # Mettre à jour les valeurs pour la prochaine itération 
        return fib_current
#import csv

Comparaison avec l’approche récursive

Critère de distinction	Approche récursive	Approche itérative
Efficacité	Cette approche est plus efficace pour de grandes valeurs de “n”, calculant les nombres de Fibonacci de manière itérative et sans calculs redondants.	Cette approche est moins efficace, surtout pour de grandes valeurs de “n”, car elle provoque des calculs redondants.
Complexité temporelle	O(n) (Linéaire)	O(2^n) (Exponentielle)
Complexité spatiale	O(1) (Constante)	O(n) (Linéaire)

Mémoïsation pour un calcul efficace

La mémoïsation est une méthode qui accélère les programmes informatiques ou les algorithmes en stockant les résultats d’appels de fonctions coûteux et en renvoyant le résultat mis en cache lorsque les mêmes entrées se produisent à nouveau. Elle est utile pour optimiser les calculs de Fibonacci car l’approche récursive recalcule les mêmes nombres de Fibonacci de nombreuses fois, ce qui conduit à une inefficacité.

Comment la mémoïsation réduit les calculs redondants

Dans les calculs de Fibonacci, sans mémoïsation, l’algorithme récursif recalcule les mêmes nombres encore et encore. La mémoïsation résout ce problème en stockant les résultats. Lorsque la fonction est appelée à nouveau avec la même entrée, elle utilise le résultat calculé pour le problème.

Mise en œuvre de la mémoïsation en Python pour Fibonacci

Voici comment vous mettez en œuvre la mémoïsation en Python pour optimiser les calculs de Fibonacci :

# Créez un dictionnaire pour stocker les nombres de Fibonacci calculés.
Fib_cache = {}
def fibonacci_memoization(n):
    if n <= 0:
        return 0
    elif n == 1:
        return 1

    # Vérifiez si le résultat est déjà dans le cache.
    Si n in fib_cache:
        return fib_cache[n]

    # Sinon, calculez-le de manière récursive et stockez-le dans le cache.
    fib_value = fibonacci_memoization(n - 1) + fibonacci_memoization(n - 2)
    fib_cache[n] = fib_value

    return fib_value
#import csv

Programmation dynamique pour la série de Fibonacci en Python

La programmation dynamique est une stratégie utilisée pour résoudre les problèmes en les décomposant en sous-problèmes plus petits et en fixant chaque sous-problème une seule fois, en stockant les résultats pour éviter les calculs redondants. Cette approche est très efficace pour résoudre des problèmes complexes comme le calcul des nombres de Fibonacci.

Explication de l’approche de la programmation dynamique pour Fibonacci :

La programmation dynamique consiste à stocker les nombres de Fibonacci dans un tableau ou un dictionnaire lorsqu’ils sont calculés afin de les réutiliser lorsque cela est nécessaire. Au lieu de recalculer les mêmes nombres de Fibonacci, la programmation dynamique les stocke une fois et les récupère selon les besoins.

Utilisation d’un tableau ou d’un dictionnaire pour stocker les résultats intermédiaires

L’approche de la programmation dynamique peut être utilisée avec un tableau ou un dictionnaire (table de hachage) pour stocker les nombres de Fibonacci intermédiaires.

def fibonacci_dynamic_programming(n):
    fib = [0] * (n + 1)  # Initialisez un tableau pour stocker les nombres de Fibonacci.
    Fib[1] = 1  # Définissez les cas de base.
    
    Pour i dans la plage(2, n + 1):
        fib[i] = fib[i - 1] + fib[i - 2]  # Calculez et stockez les nombres de Fibonacci.
    Return fib[n]  # Renvoyez le nième nombre de Fibonacci.
#import csv

Avantages de la programmation dynamique en termes de complexité temporelle

La méthode de la programmation dynamique pour calculer les nombres de Fibonacci offre plusieurs avantages en termes de complexité temporelle :

Complexité temporelle réduite : La programmation dynamique réduit la complexité temporelle des calculs de Fibonacci, passant d’exponentielle (O(2^n)) dans l’approche récursive naïve à linéaire (O(n)).

Réutilisation efficace : En stockant les résultats intermédiaires, la programmation dynamique évite les calculs redondants. Chaque nombre de Fibonacci est calculé une fois, puis récupéré depuis la mémoire lorsque cela est nécessaire, ce qui améliore l’efficacité.

Scalabilité améliorée : La méthode de la programmation dynamique reste efficace même pour de grandes valeurs de “n”, ce qui la rend appropriée pour des applications pratiques.

Optimisation de l’espace pour Fibonacci

Les stratégies d’optimisation de l’espace pour calculer les nombres de Fibonacci visent à réduire l’utilisation de la mémoire en ne stockant que les valeurs précédentes importantes plutôt que toute la séquence. Ces techniques sont particulièrement utiles lorsque l’efficacité de la mémoire est une préoccupation.

Utilisation de variables pour stocker uniquement les valeurs précédentes nécessaires

L’une des stratégies d’optimisation de l’espace les plus couramment utilisées pour Fibonacci consiste à utiliser des variables pour stocker uniquement les deux nombres de Fibonacci les plus récents plutôt qu’un tableau pour stocker la séquence complète.

def fibonacci_space_optimized(n):
    if n <= 0:
        return 0
    elif n == 1:
        return 1

    fib_prev = 0  # Initialisez le nombre de Fibonacci précédent.
    Fib_current = 1  # Initialisez le nombre de Fibonacci actuel.

    Pour _ dans la plage(2, n + 1):
        fib_next = fib_prev + fib_current  # Calculez le prochain nombre de Fibonacci.
        fib_prev, fib_current = fib_current, fib_next  # Mettez à jour les valeurs pour la prochaine itération.

    Return fib_current  # Renvoyez le nième nombre de Fibonacci.

#import csv

Échanges entre complexité spatiale et complexité temporelle

Les techniques optimisées en termes d’espace pour Fibonacci impliquent des compromis entre la complexité spatiale et la complexité temporelle :

Efficacité spatiale : Les approches optimisées en termes d’espace utilisent beaucoup moins de mémoire car elles ne stockent que quelques variables (généralement deux) pour suivre les derniers nombres de Fibonacci. Cela est relativement efficace en termes d’espace, ce qui le rend adapté aux environnements à mémoire limitée.

Efficacité temporelle : Bien que ces stratégies ne soient pas linéaires (O(n)) en termes de complexité temporelle, elles peuvent être légèrement plus lentes que la programmation dynamique avec un tableau en raison des affectations de variables. Cependant, la différence est généralement négligeable pour des valeurs pratiques de “n”.

Générer les nombres de Fibonacci jusqu’à N

La génération des nombres de Fibonacci jusqu’à N en Python peut être réalisée avec une boucle. Voici un code Python qui génère les nombres de Fibonacci jusqu’à N :

def generate_fibonacci(restriction):
    if restriction <= 0:
        return []

    fibonacci_sequence = [0, 1]  # Initialiser avec les deux premiers nombres de Fibonacci.
    while True:
        next_fib = fibonacci_sequence[-1] + fibonacci_sequence[-2]
        if next_fib > restriction:
            break
        fibonacci_sequence.append(next_fib)
    return fibonacci_sequence
#import csv

Applications de la génération de séquences de Fibonacci dans une plage

• Analyse de séries de nombres : La génération de nombres de Fibonacci dans une limite peut être utile pour analyser et étudier des séquences de nombres, identifier des motifs et explorer des propriétés mathématiques.
• Analyse des performances : En informatique et en évaluation d’algorithmes, les séquences de Fibonacci peuvent être utilisées pour analyser les performances des algorithmes et des structures de données, principalement en termes de complexité temporelle et spatiale.
• Tests d’application : Dans les tests d’application, les nombres de Fibonacci peuvent être utilisés pour créer des cas de test avec des tailles d’entrée variables afin d’évaluer les performances et la robustesse des applications logicielles.
• Modélisation financière : Les séquences de Fibonacci ont des applications en modélisation financière, notamment dans l’étude des tendances du marché et des mouvements de prix dans des domaines tels que le trading d’actions et l’analyse des investissements.

Applications de la série de Fibonacci

La série de Fibonacci a de nombreuses applications dans le monde réel. Dans la nature, elle décrit l’agencement des feuilles, des pétales et des graines dans les plantes, illustrant un emballage efficace. Le Nombre d’Or, dérivé des proportions de Fibonacci, est utilisé pour créer des compositions et des designs esthétiquement désirables. En technologie, les nombres de Fibonacci jouent un rôle dans l’optimisation des algorithmes, tels que la programmation dynamique et la mémoïsation, améliorant les performances dans des tâches telles que le calcul de valeurs de Fibonacci massives ou la résolution de problèmes d’optimisation. De plus, les séquences de Fibonacci sont utilisées en modélisation financière, aidant à l’analyse du marché et à la prédiction des tendances des prix. Ces applications du monde réel soulignent l’importance de la série de Fibonacci dans les mathématiques, la nature, l’art et la résolution de problèmes.

Le Nombre d’Or de Fibonacci

Le Nombre d’Or de Fibonacci, souvent désigné par Phi (Φ), est une valeur irrationnelle approximativement égale à 1,61803398875. Cette constante mathématique est profondément liée à la suite de Fibonacci. En progressant dans la suite de Fibonacci, le rapport entre deux nombres consécutifs se rapproche de plus en plus de Phi. Cette relation donne naissance à des principes esthétiques en design, où les éléments sont souvent proportionnés selon Phi, créant des compositions visuellement harmonieuses. Des exemples pratiques comprennent l’architecture du Parthénon, des œuvres d’art comme la Mona Lisa et les proportions du visage humain, mettant en évidence l’utilisation étendue du Nombre d’Or dans la réalisation de designs esthétiquement fascinants et équilibrés dans de nombreux domaines, de l’art et de l’architecture au design graphique et web.

Fibonacci dans le trading et la finance

Les proportions de Fibonacci jouent un rôle crucial dans le trading et la finance grâce aux niveaux de retracement et d’extension de Fibonacci dans l’analyse technique. Les traders utilisent ces niveaux pour identifier les points de support et de résistance potentiels sur les marchés financiers. La suite de Fibonacci aide à prédire les tendances du marché boursier en identifiant les niveaux de prix clés où des retournements ou des extensions sont probables. Les techniques de trading basées sur Fibonacci consistent à utiliser ces niveaux en combinaison avec des indicateurs techniques pour prendre des décisions de trading éclairées. Les traders recherchent régulièrement des motifs de Fibonacci, tels que le Nombre d’Or, pour aider à anticiper les mouvements des prix.

Conclusion

Bien qu’il semble être enraciné dans les mathématiques, la suite de Fibonacci a également une pertinence dans la science des données. Comprendre les principes de génération de séquences et de reconnaissance de motifs inhérents à la suite de Fibonacci peut aider les scientifiques des données à reconnaître et à analyser les motifs récurrents au sein des ensembles de données, un aspect fondamental de l’analyse de données et de la modélisation prédictive en science des données. Inscrivez-vous à notre cours Python gratuit pour améliorer vos compétences en Python.

Foire aux questions

We will continue to update IPGirl; if you have any questions or suggestions, please contact us!