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 :

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 :

MoisCouples de
lapereaux
Couples de
lapins
Total
couples
Informations
0000Au moment zéro, nous n'avons pas encore de couple. Le compte commence après que nous ayons introduit notre premier couple.
1101Le premier mois, nous avons 1 couple de lapereaux.
2011Le second mois, notre couple de lapereaux devient pubère. Ils passent du bon temps, et Mme est enceinte.
3112Le troisième mois, Mme lapin accouche d'un couple de lapereaux après1 mois de gestation. Et ils reprennent leurs galipettes.
4123Notre premier couple acouche encore d'un couple de lapereaux, et leur première portée devient adulte.
5235Le premier couple et sa première portée ont chacun un couple, et la seconde portée du premier couple devient adulte.
6358Bon, comme à ce stade la famille devient un peu compliquée, le schéma animé plus bas est plus explicite...
75813 
881321Et ainsi de suite...

 

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é

 

Programmer les suites de Fibonacci


Code Java (Fibonacci avec simple récursivité) (9 lignes) :
  1. public class Fibonacci {
  2.  
  3. public static int fibonacci(int n) {
  4. if (n < 2)
  5. return (n);
  6. return (fibonacci(n - 1) + fibonacci(n - 2));
  7. }
  8.  
  9. }

Dans cette implémentation, nous pouvons remarquer deux appels récursifs[2], ce qui donne un ordre de grandeur de temps T(n) ≤ Ordre de grandeur(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.

[3]

Code Pascal (Suite de Fibonacci ) (9 lignes) :
  1. function fibonacci(var n : integer) : integer;
  2. {Pre: n>=0}
  3. begin
  4. if n < 2
  5. then
  6. fibonacci := n;
  7. else
  8. fibonacci := fibonacci(n-1) + fibonacci(n-2);
  9. end;

 

Réseaux sociaux

Vous pouvez modifier vos préférences dans votre profil pour ne plus afficher les interactions avec les réseaux sociaux sur ces pages.

 

Nuage de mots clés

19 mots clés dont 0 définis manuellement (plus d'information...).

Avertissement

Cette page ne possède pas encore de mots clés manuels, ceci est donc un exemple automatique (les niveaux de pertinence sont fictifs, mais les liens sont valables). Pour tester le nuage avec une page qui contient des mots définis manuellement, vous pouvez cliquer ici.

Vous pouvez modifier vos préférences dans votre profil pour ne plus afficher le nuage de mots clés.

 

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 :
    Afficher le fichier .cSuite de Fibonacci Exemple d'itération en C
    Afficher le fichier .cSuite de Fibonacci Exemple de récursion en C
    Afficher le fichier .cppSuite de Fibonacci Exemple d'itération en C++
    Afficher le fichier .cppSuite de Fibonacci Exemple de récursion en C++
    Afficher le fichier .csSuite de Fibonacci Exemple d'itération en C#
    Afficher le fichier .csSuite de Fibonacci Exemple de récursion en C#
    Afficher le fichier .pasSuite de Fibonacci Exemple de récursion en Pascal
    Afficher le fichier .pasSuite de Fibonacci Exemple de méoïsation en Pascal
    Afficher le fichier .adaSuite de Fibonacci Exemple d'itération en ADA
    Afficher le fichier .adaSuite de Fibonacci Exemple de récursion en ADA
    Afficher le fichier .phpSuite de Fibonacci Exemple d'itération en PHP
    Afficher le fichier .phpSuite de Fibonacci Exemple de récursion en PHP
    Afficher le fichier .javaSuite de Fibonacci Exemple de récursion en Java
    Afficher le fichier .rhtmlSuite de Fibonacci Exemple d'itération en Ruby
    Afficher le fichier .rhtmlSuite de Fibonacci Exemple de récursion en Ruby
    Afficher le fichier .stSuite de Fibonacci
    Afficher le fichier .forSuite de Fibonacci
    Afficher le fichier .aspSuite de Fibonacci Exemple d'itération en ASP
    Afficher le fichier .aspSuite de Fibonacci Exemple de récursion en ASP
    Afficher le fichier .jsSuite de Fibonacci Exemple de récursion en JavaScript
    Afficher le fichier .lspSuite de Fibonacci Exemple de récursion en Lisp
    Afficher le fichier .plSuite de Fibonacci Exemple d'itération en Perl
    Afficher le fichier .plSuite de Fibonacci Exemple d'itération en Perl avec bigint
    Afficher le fichier .plSuite de Fibonacci Exemple de récursion en Perl
    Afficher le fichier .pySuite de Fibonacci Exemple de récursion en Python
    Afficher le fichier .cobSuite de Fibonacci
    Afficher le fichier .eSuite de Fibonacci Exemple d'itération en Eiffel
    Afficher le fichier .eSuite de Fibonacci Exemple de récursion en Eiffel
    Afficher le fichier .scmSuite de Fibonacci Exemple d'itération en Scheme
    Afficher le fichier .scmSuite de Fibonacci Exemple de récursion en Scheme
    Afficher le fichier .camlSuite de Fibonacci Exemple de récursion en Ocaml
    Afficher le fichier .tclSuite de Fibonacci

 

Liste des images

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

 

Astuce pour imprimer les couleurs des cellules de tableaux : http://www.gaudry.be/ast-rf-450.html
Aucun commentaire pour cette page

© Ce document issu de l′infobrol est enregistré sous le certificat Cyber PrInterDeposit Digital Numbertection. Enregistrement IDDN n° 5329-11338
Document créé le 30/10/09 03:58, dernière modification le Vendredi 17 Juin 2011, 12:11
Source du document imprimé : http:///www.gaudry.be/algorithme-fibonacci.html
St.Gaudry©07.01.02
Outils (masquer)
||
Recherche (afficher)
Recherche :

Utilisateur (masquer)
Apparence (afficher)
Stats (afficher)
15838 documents
455 astuces.
550 niouzes.
3107 definitions.
447 membres.
8121 messages.

Document genere en :
0,14 seconde

Mises à jour :
Mises à jour du site
Citation (masquer)
On mesure l'intelligence d'un individu à la quantité d'incertitudes qu'il est capable de supporter.

Emmanuel Kant
 
l'infobrol
Nous sommes le Mercredi 18 Octobre 2017, 00:12, toutes les heures sont au format GMT+1.00 Heure, heure d'été (+1)