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 :

Un homme met un couple de lapins dans un lieu isolé de tous les côté par un mur. Combien de couples obtient-on en un an si chaque couple engendre tous les mois un nouveau couple à compter du troisième mois de son existence ?

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 :

Tableau des naissances pour les lapins de Fibonacci

0 | 0 | 0 | 0 | Au moment zéro, nous n'avons pas encore de couple. Le compte commence après que nous ayons introduit notre premier couple. |

1 | 1 | 0 | 1 | Le premier mois, nous avons 1 couple de lapereaux. |

2 | 0 | 1 | 1 | Le second mois, notre couple de lapereaux devient pubère. Ils passent du bon temps, et Mme est enceinte. |

3 | 1 | 1 | 2 | Le troisième mois, Mme lapin accouche d'un couple de lapereaux après1 mois de gestation. Et ils reprennent leurs galipettes. |

4 | 1 | 2 | 3 | Notre premier couple acouche encore d'un couple de lapereaux, et leur première portée devient adulte. |

5 | 2 | 3 | 5 | Le premier couple et sa première portée ont chacun un couple, et la seconde portée du premier couple devient adulte. |

6 | 3 | 5 | 8 | Bon, comme à ce stade la famille devient un peu compliquée, le schéma animé plus bas est plus explicite… |

7 | 5 | 8 | 13 | |

8 | 8 | 13 | 21 | Et ainsi de suite… |

Colonne 1 : X^eme mois
Colonne 2 : Nombre de couples de lapereaux après X mois
Colonne 3 : Nombre de couples de lapins après X mois
Colonne 4 : Nombre total de couples après X mois (suite de Fibonacci)

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

Suite de Fibonacci par récursivité

Inhoudsopgave Haut

Programmer les suites de Fibonacci

Code Java (Fibonacci avec simple récursivité) (9 lignes)

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.

Code Pascal (Suite de Fibonacci ) (9 lignes)

function fibonacci(var n : integer) : integer;
{Pre: 	n>=0}
begin
	if n < 2 
	then
		fibonacci := n;
	else
		fibonacci := fibonacci(n-1) +  fibonacci(n-2);		
end;

Nederlandse vertaling

U hebt gevraagd om deze site in het Nederlands te bezoeken. Voor nu wordt alleen de interface vertaald, maar nog niet alle inhoud.

Als je me wilt helpen met vertalingen, is je bijdrage welkom. Het enige dat u hoeft te doen, is u op de site registreren en mij een bericht sturen waarin u wordt gevraagd om u toe te voegen aan de groep vertalers, zodat u de gewenste pagina's kunt vertalen. Een link onderaan elke vertaalde pagina geeft aan dat u de vertaler bent en heeft een link naar uw profiel.

Bij voorbaat dank.

Document heeft de 30/10/2009 gemaakt, de laatste keer de 12/03/2019 gewijzigd
Bron van het afgedrukte document:https://www.gaudry.be/nl/algorithme-fibonacci-rf-ruby/programmer-dynamique.html

De infobrol is een persoonlijke site waarvan de inhoud uitsluitend mijn verantwoordelijkheid is. De tekst is beschikbaar onder CreativeCommons-licentie (BY-NC-SA). Meer info op de gebruiksvoorwaarden en de auteur.

Notes

↑ 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)."
↑ Double récursion : fibonacci(n-1) + fibonacci(n-2)
↑ 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

Inhoudsopgave Haut

Referenties

IHDCB331 - Méthodes de Programmation : PY Schobbens, Cours de Méthodes de Programmation (September 2009)

Deze verwijzingen en links verwijzen naar documenten die geraadpleegd zijn tijdens het schrijven van deze pagina, of die aanvullende informatie kunnen geven, maar de auteurs van deze bronnen kunnen niet verantwoordelijk worden gehouden voor de inhoud van deze pagina.
De auteur Deze site is als enige verantwoordelijk voor de manier waarop de verschillende concepten, en de vrijheden die met de referentiewerken worden genomen, hier worden gepresenteerd. Vergeet niet dat u meerdere broninformatie moet doorgeven om het risico op fouten te verkleinen.

Inhoudsopgave Haut