Suite de Fibonacci

Objectifs

  • Connaître la suite de Fibonacci ;

  • Savoir construire la suite de Fibonacci.

Mise en situation

Dans leur observation de la nature, certains mathématiciens ont découvert la récurrence d'une suite de nombres bien précise : la suite de Fibonacci.

Suite de Fibonacci

La suite de Fibonacci est un suite infinie de nombres, définie de la manière suivante.

1
Fibonacci[0] = 0
2
Fibonacci[1] = 1

Puis, pour tout entier i plus grand que 1 :

1
Fibonacci[i] = Fibonacci[i-1] + Fibonacci[i-2]

  • Pour i = 2, Fibonacci[2] = Fibonacci[1] + Fibonacci[0] = 1 + 0 = 1.

  • Pour i = 3, Fibonacci[3] = Fibonacci[2] + Fibonacci[1] = 1 + 1 = 2.

  • Pour i = 4, Fibonacci[4] = Fibonacci[3] + Fibonacci[2] = 2 + 1 = 3.

  • ... Pour i = 10, Fibonacci[10] = Fibonacci[9] + Fibonacci[8] = 34 +  21 = 55.

  • Et ainsi de suite.

Douze premiers termes de la suite de FibonacciInformations[1]

Remarque

On retrouve, par exemple, cette suite dans la floraison de l'artichaut ou dans la disposition d'une pomme de pain. Cette présence énigmatique dans de nombreuses dispositions naturelles continuent d'intriguer les scientifiques et alimente encore aujourd'hui des recherches ou des créations artistiques.

MéthodeImplémentation

Voici l'implémentation du calcul des n premiers termes la suite de Fibonacci en Python puis en JavaScript. L'implémentation est assez simple car il suffit d'itérer en additionnant systématiquement les deux valeurs précédentes.

1
/** JavaScript : Suite de Fibonacci. */
2
const n = Number(prompt('Entrer un entier supérieur à 1 :')) // Par exemple, 4
3
4
const fibo = new Array(n)
5
fibo[0] = 0
6
fibo[1] = 1
7
8
for (let i = 2; i < n; i = i + 1) {
9
  fibo[i] = fibo[i - 1] + fibo[i - 2]
10
}
11
12
console.log(fibo)
13
1
"""Python : Suite de Fibonacci. """
2
n = int(input("Entrer un entier supérieur à 1:"))  #  Par exemple, 4
3
4
fibo = [0]*(n)
5
fibo[0] = 0
6
fibo[1] = 1
7
8
for i in range(2,n):
9
  fibo[i] = fibo[i-1] + fibo[i-2]
10
11
print(fibo)
ExempleDéroulement pas à pas
Déroulons l'algorithme pas à pas pour n = 5. Tout d'abord, une liste vide de taille 5 est créée et les éléments 0 et 1 sont positionnés sur les deux premières positions, fibo = [0, 1, _, _, _]. Ensuite, on entre dans la boucle :
  • Première itération, i = 2 : fibo[2] = fibo[1] + fibo[0] = 1. On a donc fibo = [0, 1, 1, _, _].
  • Deuxième itération, i = 3 : fibo[3] = fibo[2] + fibo[1] = 2. On a donc fibo = [0, 1, 1, 2, _].
  • Troisième itération, i = 4 : fibo[4] = fibo[3] + fibo[2] = 3. On a donc fibo = [0, 1, 1, 2, 3].
  • i = n donc la boucle se termine.
La liste des cinq premiers termes de la suite est affichée dans la console.
ComplémentComplexité
La complexité en temps de cet algorithme est O(n). On peut voir très clairement ce qui explique cette complexité car on voit deux boucles simples. On pourrait être plus précis en disant O(2 * n) mais cette complexité est considérée comme équivalente à O(n) car on souhaite simplement un ordre de grandeur.
À retenir
  • La suite de Fibonacci est une suite de nombres qu'on retrouve souvent dans la nature.
  • L'implémentation du calcul de ses termes est très simple.