Suite de Fibonacci (1)

Les premiers termes de la suite de Fibonacci sont :

\[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, \cdots\]

• Les deux premiers termes sont \(0\) et \(1\).
• À partir du troisième, un terme est la somme des deux précédents.

Écrire une fonction telle que fibonacci(n) renvoie le terme d'indice \(n\) de la suite de Fibonacci.

On demande ici de programmer une fonction très élémentaire, pour des valeurs de \(n\) inférieures à \(25\).

Exemples :

🐍 Console Python

>>> fibonacci(0)
0
>>> fibonacci(3)
2
>>> fibonacci(7)
13
>>> fibonacci(8)
21
>>> fibonacci(9)
34
>>> fibonacci(4)
3

On a bien fibonacci(9) égal à fibonacci(7) + fibonacci(8)

###

Lancer # testsbksl-nlbksl-nlassert fibonacci(0) == 0bksl-nlassert fibonacci(1) == 1bksl-nlassert fibonacci(2) == 1bksl-nlassert fibonacci(3) == 2bksl-nlassert fibonacci(9) == 34bksl-nlassert fibonacci(4) == 3bksl-nlbksl-nlbksl-nl# autres testsbksl-nlbksl-nlbksl-nlPHI = (1 + 5py-strpy-str0.5) / 2bksl-nlbksl-nlfor n in range(25):bksl-nl attendu = round(PHIpy-strpy-strn / 5py-strpy-str0.5)bksl-nl assert fibonacci(n) == attendu, f"Erreur pour n = {n}"bksl-nlbksl-nl Valider 5/5 Télécharger Téléverser Recharger Sauvegarder

def fibonacci(n):bksl-nl ...bksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlassert fibonacci(0) == 0bksl-nlassert fibonacci(1) == 1bksl-nlassert fibonacci(2) == 1bksl-nlassert fibonacci(3) == 2bksl-nlassert fibonacci(9) == 34bksl-nlassert fibonacci(4) == 3bksl-nlbksl-nldef fibonacci(n):bksl-nl if n < 2:bksl-nl return nbksl-nl else:bksl-nl return fibonacci(n - 1) + fibonacci(n - 2)bksl-nlbksl-nl

A

Cette version est très simple à écrire, mais devient très lente à partir de n = 25 environ. Les mêmes calculs sont demandés de très nombreuses fois.

Version itérative

🐍 Script Python

def fibonacci(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a+b
    return a

Il s'agit de programmation dynamique. On part de a, b = 0, 1, les deux premiers termes consécutifs, et on progresse de n étapes.

À chaque étape,

• Le nouveau a devient le terme suivant a : l'ancien b.
• Le nouveau b devient le terme suivant b : la somme de a et de b.

À la fin, le terme d'indice n est a, b est le suivant.

Version avec une liste pour mémoïser

🐍 Script Python

fibonacci_mem = [0, 1]

def fibonacci(n):
    i = len(fibonacci_mem)
    while i <= n:
        fib_i = fibonacci_mem[i - 1] + fibonacci_mem[i - 2]
        fibonacci_mem.append(fib_i)
        i += 1
    return fibonacci_mem[n]

Cette fonction complète si nécessaire une liste fibonacci_mem.

• fibonacci_mem[n] stocke le résultat de fibonacci(n)
• Tant que la longueur de cette liste est insuffisante, on ajoute un nouveau terme.
• fib_i sera le terme d'indice i
• i est la taille de la liste, qui augmente de 1 à chaque tour de boucle.

Version mathématique

Il existe une formule utilisant les flottants qui permet de trouver rapidement le résultat.

🐍 Script Python

from math import sqrt
PHI_1 = (1 + sqrt(5)) / 2
PHI_2 = (1 - sqrt(5)) / 2

def fibonacci(n):
    return round((PHI_1**n - PHI_2**n) / sqrt(5))

Cette version devient fausse dès que le résultat entier dépasse la capacité de la mantisse du conteneur flottant.

On peut aussi utiliser une version simplifiée

🐍 Script Python

from math import sqrt
PHI = (1 + sqrt(5)) / 2

def fibonacci(n):
    return round(PHI**n / sqrt(5))

Z