Suite de Fibonacci

Cet outil est un calculateur de la suite de Fibonacci. Il calcule :
- Le terme de la suite de fibonacci de rang n.
- La somme des n premiers termes de cette suite.

Suite de Fibonacci

On appelle suite de fibonacci la suite de nombres entiers naturels dans laquelle chaque terme s'obtient en additionnant les deux termes précédents, les deux premiers étant égaux à 0 et 1. Le terme général de la suite de Fibonacci s'écrit,

Formule de Binet

La formule de Binet donne une formule explicite du n-ième terme de la suite de Fibonacci. Ainsi, si `F_n` est le terme de la suite de Fibonaci de rang n alors, il s'écrit,

Une autre manière d'écrire cette formule en utilisant le nombre d'or `phi` :

Algorithmes de calcul

Algorithme simple

//Cet algorithme applique strictement la définition des nombres de Fibonacci
fonction fibonacci(n)
    si n = 0
        retourner 0

    si n = 1
        retourner 1
    	
    retourner fibonacci(n-1) + fibonacci(n-2)

Cet algorithme est précisé ici à titre pédagogique, il n'est pas conseillé de l'utiliser spécialement pour des grandes valeurs de n car il n'est pas optimal,
- il recalcule systématiquement plusieurs fois les termes de la suite précédant le n-ième terme.
- son temps d'exécution est exponentiel en fonction de n.

Algorithme dynamique

fonction fibonacci(n)
	//initialisation de la liste des nombres de fibonacci
	f = (0,1)

	Pour i de 2 à n
        ajouter à la liste f la valeur : f[i-1] + f[i-2]
 
    retourner f[n]

L'avantage de cet algorithme est qu'il évite les recalculs des termes tel que l'on a vu dans le premier algorithme.

Calcul avec la formule de Binet

//cette fonction calcule les nombres de Fibonacci à partir du nombre d'or
fonction fibonacci(n)
	phi = (1+sqrt(5))/2
	retourner (phi^n-(-phi)^(-n))/sqrt(5)

Cet algorithme est plus rapide puisqu'il ne nécessite pas de calcul des termes précédents. Son inconvénient est que selon la machine sur lequel il est exécuté, on peut se heurter plus ou moins rapidement, à partir d'un certain rang de n, à des problèmes d'arrondi qui viendront fausser le résultat.

Les 50 premiers termes de la suite de Fibonacci

Notations:
n : le rang
`F_n` : le terme de rang n de la suite de Fibonacci
`S_n` : la somme des n premiers termes de la suite de Fibonacci
`F_n/F_(n-1)` : le rapport entre 2 termes consécutifs (approximation du nombre d'or)

Nombre d'or : ` phi = (1+sqrt(5))/2 approx` 1.6180339887499
On remarque dans le tableau ci-dessous que le rapport `F_n/F_(n-1)` converge rapidement vers le nombre d'or.

Voir aussi

Suite arithmétique
Suite géométrique

---