Fibonacci et la programmation

Sommaire du document

Leonardo Fibonacci

Leonardo Fibonacci est un mathématicien italien qui a très tôt pris conscience que les chiffres arabes et le système décimal permettaient de manipuler les nombres plus aisément et plus rapidement que le système des chiffres romains^[1].

Ses travaux sur l'arithmétique et leurs applications commerciales sont encore utilisés, mais ses contemporains n'ont pas saisi la portée de ces changements, diabolisant même l'apparition de ce nouveau chiffre zéro qui représentait le vide.

La suite de Fibonacci

La suite d'entiers de Fibonacci est très souvent utilisée en informatique pour comprendre certains principes algorithmiques, comme la récursivité. Le problème posé par Fibonacci concerne la croissance d'une population de lapins :

Cependant, certaines distances sont prises par rapport à la réalité :

• aucun lapin ne meurt pendant la durée du test.
• chaque couple de lapins pubères engendre chaque mois exactement un nouveau couple( un mâle et une femelle) de lapins.

Nous pouvons en déduire pour notre algorithme que :

Les lapins de Fibonacci en image...

Si nous consultons le rapport entre les mois, les nombres de couples de lapereaux, de couples de lapins pubères et le total de la population, nous pouvons en déduire qu'au moment m la population est égale à la population du mois prédcédent(m - 1) plus la population deux mois auparavant(m - 2). Les seules exceptions sont les deux premières lignes de notre tableau, car nous devons attendre de placer un couple dans notre laboratoire, que ce couple soit pubère, et le temps de la gestation.

Programmer les suites de Fibonacci

public class Fibonacci {
 
	public static int fibonacci(int n) {
		if (n < 2)
			return (n);
		return (fibonacci(n - 1) + fibonacci(n - 2));
	}
 
}

Dans cette implémentation, nous pouvons remarquer deux appels récursifs^[2], ce qui donne un ordre de grandeur de temps T(n) ≤ (2ⁿ)

Nous pouvons optimiser ce code par l'application des principes de la programmation dynamique, comme nous l'avons vu lors d'exemple de la mémoïsation appliquée à la suite de Fibonacci.

(define fibo
 (lambda (x)
   (if (< x 2)
     x
     (+ (fibo (- x 1)) (fibo (- x 2))))))

Notes

1. ↑ Liber Abaci : C'est dans ce livre que Leonardo Fibonacci tenta de convaincre ses contemporains de l'utilité des chiffres arabes. Le titre peut se traduire par "Livre de calcul", ou encore "Livre de l'abaque (car l'abaque, ou boulier était l'instrument de calcul de l'époque)."
   
   
2. ↑ Double récursion : fibonacci(n-1) + fibonacci(n-2)
   
   
3. ↑ Autres codes en relation avec Fibonacci :
   Suite de Fibonacci Exemple d'itération en C
   Suite de Fibonacci Exemple de récursion en C
   Suite de Fibonacci Exemple d'itération en C++
   Suite de Fibonacci Exemple de récursion en C++
   Suite de Fibonacci Exemple d'itération en C#
   Suite de Fibonacci Exemple de récursion en C#
   Suite de Fibonacci Exemple de récursion en Pascal
   Suite de Fibonacci Exemple de méoïsation en Pascal
   Suite de Fibonacci Exemple d'itération en ADA
   Suite de Fibonacci Exemple de récursion en ADA
   Suite de Fibonacci Exemple d'itération en PHP
   Suite de Fibonacci Exemple de récursion en PHP
   Suite de Fibonacci Exemple de récursion en Java
   Suite de Fibonacci Exemple d'itération en Ruby
   Suite de Fibonacci Exemple de récursion en Ruby
   Suite de Fibonacci
   Suite de Fibonacci
   Suite de Fibonacci Exemple d'itération en ASP
   Suite de Fibonacci Exemple de récursion en ASP
   Suite de Fibonacci Exemple de récursion en JavaScript
   Suite de Fibonacci Exemple de récursion en Lisp
   Suite de Fibonacci Exemple d'itération en Perl
   Suite de Fibonacci Exemple d'itération en Perl avec bigint
   Suite de Fibonacci Exemple de récursion en Perl
   Suite de Fibonacci Exemple de récursion en Python
   Suite de Fibonacci
   Suite de Fibonacci Exemple d'itération en Eiffel
   Suite de Fibonacci Exemple de récursion en Eiffel
   Suite de Fibonacci Exemple d'itération en Scheme
   Suite de Fibonacci Exemple de récursion en Scheme
   Suite de Fibonacci Exemple de récursion en Ocaml
   Suite de Fibonacci
   
   

Liste des images

1. Suite de Fibonacci par récursivité _{(Référence : infobrol)}

Structure du document