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 romains1.
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 :
- Colonne 1 : Xeme 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)
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
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écursifs2, ce qui donne un ordre de grandeur de temps T(n) ≤ (2n)
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.
3Code 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;
English translation
You have asked to visit this site in English. For now, only the interface is translated, but not all the content yet.If you want to help me in translations, your contribution is welcome. All you need to do is register on the site, and send me a message asking me to add you to the group of translators, which will give you the opportunity to translate the pages you want. A link at the bottom of each translated page indicates that you are the translator, and has a link to your profile.
Thank you in advance.
Document created the 30/10/2009, last modified the 12/03/2019
Source of the printed document:https://www.gaudry.be/en/algorithme-fibonacci-rf-pascal/fibonacci-memo.pas.html/programmer-dynamique.html
The infobrol is a personal site whose content is my sole responsibility. The text is available under CreativeCommons license (BY-NC-SA). More info on the terms of use and the author.
- ↑ 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
References
- IHDCB331 - Méthodes de Programmation : PY Schobbens,
Cours de Méthodes de Programmation
(September 2009)
These references and links indicate documents consulted during the writing of this page, or which may provide additional information, but the authors of these sources can not be held responsible for the content of this page.
The author This site is solely responsible for the way in which the various concepts, and the freedoms that are taken with the reference works, are presented here. Remember that you must cross multiple source information to reduce the risk of errors.