Séquence de Fibonacci en Python : Apprendre et explorer les techniques de codage

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.

Qu'est-ce que 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.

Nature récursive de la suite de Fibonacci

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 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.

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.

Connexion au nombre d'or 

La suite de Fibonacci est étroitement liée au nombre d'or, un nombre irrationnel représenté par φ (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 :

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

Applications pratiques de la suite de Fibonacci

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.

Fibonacci dans la nature

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.

Fibonacci dans l'informatique

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 :

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

# Example usage
for i in range(10):
    print(fibonacci(i), end=" ")

0 1 1 2 3 5 8 13 21 34

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. 

Autres exemples courants

Voici quelques autres exemples de l'apparition de cette séquence dans la vie quotidienne et dans des domaines spécialisés :

• Dans l'art : La suite de Fibonacci est utilisée par les artistes et les architectes depuis des siècles. Des structures célèbres comme le Parthénon présentent ces proportions parce qu'elles sont naturellement agréables à l'œil.
• En musique : Les compositeurs utilisent les nombres de Fibonacci pour créer des rythmes et des mélodies. Par exemple, ils attribuent des notes entières au chiffre 1, des demi-notes au chiffre 2 et des noires au chiffre 3 pour créer des motifs harmonieux.
• Dans le commerce : Les négociants en bourse utilisent les nombres de Fibonacci pour analyser les tendances du marché. Ils les utilisent pour prédire les niveaux de prix potentiels auxquels les actions pourraient s'inverser, ce qui les aide à décider du moment de l'achat ou de la vente.
• En physique : En physique quantique, des motifs de Fibonacci ont été observés dans les interactions et le comportement des particules, révélant comment ces séquences apparaissent même aux plus petites échelles de la nature.

Implémentation de la séquence de Fibonacci en Python

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.

Utiliser une méthode itérative

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, 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.

Voici un code Python pour cela :

n = 10
a, b = 0, 1

for i in range(n):
    print(a)
    a, b = b, a + b

0
1
1
2
3
5
8
13
21
34

Si vous souhaitez utiliser une boucle while au lieu d'une boucle for, voici comment vous pouvez écrire le code :

# Number of terms to print in the Fibonacci series
n = 10

# Initialize the first two terms
a, b = 0, 1
i = 0

while i < n:
    print(a, end=' ')
    # Update the terms
    a, b = b, a + b
    i += 1

0 1 1 2 3 5 8 13 21 34

Les deux méthodes sont très faciles à comprendre, ce qui les rend parfaites pour les débutants. 

Utiliser une méthode récursive

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 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.

Voici le code pour cela :

def fibonacci_recursive(n):
    if n <= 1:
        return n
    else:
        return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

num_terms = 10
for i in range(num_terms):
    print(fibonacci_recursive(i), end=" ")

0 1 1 2 3 5 8 13 21 34

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.

Utilisation d'une méthode récursive optimisée avec mise en cache

Pour remédier à l'inefficacité de la récursion simple, j'utilise souvent la mise en cache. Le site lru_cache de Python stocke les valeurs calculées précédemment afin que la fonction n'ait pas à refaire le travail.

Voici comment je procède :

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.

Cette approche combine la clarté de la récursion et l'efficacité de la mise en cache.

Des façons plus avancées de réaliser la séquence de Fibonacci en Python

Si vous cherchez d'autres façons de calculer les nombres de Fibonacci, voici quelques techniques plus avancées :

Exponentiation de la matrice

L'exponentiation matricielle est l'une des méthodes les plus efficaces pour calculer les nombres de Fibonacci pour de grandes valeurs de n. Au lieu de recalculer les termes à plusieurs reprises, cette méthode utilise la multiplication matricielle pour obtenir des résultats en temps logarithmique.

Voici comment j'ai mis cela en œuvre en Python :

import numpy as np

def 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 34

Dans ce code, si n 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

La formule de Binet calcule directement le nombre de Fibonacci 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.

La formule est la suivante :

Où ?

• φ = (1 + √5) / 2​, le nombre d'or.
• 1 - φ est le conjugué de φ.

Voici le code Python pour la formule de Binet :

import math

def fibonacci_binet(n):
    phi = (1 + math.sqrt(5)) / 2
    return round((phi ** n - (1 - phi) ** n) / math.sqrt(5))

# Find the 10th Fibonacci number
n = 10
result = fibonacci_binet(n)
print(f" The Fibonacci Number of {n}th term is {result}" ) 

The Fibonacci number of 10th term is 55

Dans ce code, la fonction fibonacci_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

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 :

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 term

print(f"Fibonacci Number: {fibonacci(10)}")

Fibonacci number: 34

Retour en arrière

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 :

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 = 10
result = fibonacci_backtracking(n)
print(f"The {n}th Fibonacci term is {result}")

The 10th Fibonacci term is 55

Complexité des algorithmes de Fibonacci en Python

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 n.

• O(1): Le nombre de Fibonacci est calculé à l'aide d'un nombre fixe d'opérations, sans itération ni récurrence.

• O(²ⁿ) : 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 n augmente.

• O(log n): La durée d'exécution augmente proportionnellement au logarithme de la taille de l'entrée n.

Complexité de l'espace

• O(n): L'algorithme utilise une mémoire qui croît directement avec le nombre d'entrées n. Ici, chaque élément nécessite un espace fixe.

• O(1) : L'utilisation de la mémoire reste constante quelle que soit la taille de l'entrée.

• O(²ⁿ): 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.

Réflexions finales

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 !