Fibonacci et la programmation

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

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 :

Contents Haut

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.

Contents Haut

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

function fib(n : integer) return integer is
  first  : integer := 0;
  second : integer := 1;
  tmp    : integer;
begin
  for i in 1..n loop
    tmp    := first + second;
    first  := second;
    second := tmp;
  end loop;
  return first;
end fib;

U bevindt zich op de Engels versie van de site, maar uw systeem geeft aan dat u liever de Nederlandse taal gebruikt.
De hele site is nog niet vertaald, maar de menu's en knoppen op de interface zijn grotendeels vertaald.

Wilt u de pagina in het Nederlands bereiken?
Klik hier om door te gaan in het Nederlands: Raadpleeg de Nederlandse versie van deze pagina

Sie befinden sich in der Englisch Version der Website, Ihr System gibt jedoch an, dass Sie die deutsche Sprache bevorzugen.
Die gesamte Site ist noch nicht übersetzt, aber die Menüs und Schaltflächen auf der Benutzeroberfläche sind weitgehend übersetzt.

Möchten Sie die Seite auf Deutsch erreichen?
Klicken Sie hier, um fortzufahren: Konsultieren Sie die deutsche Version dieser Seite

Vous vous trouvez sur la version anglaise du site, mais votre système indique que vous préférez utiliser la langue française.

Souhaitez-vous atteindre la page en français?
Cliquez ici pour continuer en français: Consulter la page en français