Fibonacci et la programmation

Inhaltsverzeichnis

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 :

Tableau des naissances pour les lapins de Fibonacci 
Date | lapereaux(*2) | lapins(*2) | Total | Explications |
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 : 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)

Inhaltsverzeichnis 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é

Inhaltsverzeichnis Haut

Programmer les suites de Fibonacci

  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écursifs2, 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
  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;

Deutsche Übersetzung

Sie haben gebeten, diese Seite auf Deutsch zu besuchen. Momentan ist nur die Oberfläche übersetzt, aber noch nicht der gesamte Inhalt.

Wenn Sie mir bei Übersetzungen helfen wollen, ist Ihr Beitrag willkommen. Alles, was Sie tun müssen, ist, sich auf der Website zu registrieren und mir eine Nachricht zu schicken, in der Sie gebeten werden, Sie der Gruppe der Übersetzer hinzuzufügen, die Ihnen die Möglichkeit gibt, die gewünschten Seiten zu übersetzen. Ein Link am Ende jeder übersetzten Seite zeigt an, dass Sie der Übersetzer sind und einen Link zu Ihrem Profil haben.

Vielen Dank im Voraus.

Dokument erstellt 30/10/2009, zuletzt geändert 12/03/2019
Quelle des gedruckten Dokuments:https://www.gaudry.be/de/algorithme-fibonacci-rf-python/programmer-dynamique.html

Die Infobro ist eine persönliche Seite, deren Inhalt in meiner alleinigen Verantwortung liegt. Der Text ist unter der CreativeCommons-Lizenz (BY-NC-SA) verfügbar. Weitere Informationen auf die Nutzungsbedingungen und dem Autor.

Aufzeichnungen
  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 .c Suite de Fibonacci Exemple d'itération en C
    Afficher le fichier .c Suite de Fibonacci Exemple de récursion en C
    Afficher le fichier .cpp Suite de Fibonacci Exemple d'itération en C++
    Afficher le fichier .cpp Suite de Fibonacci Exemple de récursion en C++
    Afficher le fichier .cs Suite de Fibonacci Exemple d'itération en C#
    Afficher le fichier .cs Suite de Fibonacci Exemple de récursion en C#
    Afficher le fichier .pas Suite de Fibonacci Exemple de récursion en Pascal
    Afficher le fichier .pas Suite de Fibonacci Exemple de méoïsation en Pascal
    Afficher le fichier .ada Suite de Fibonacci Exemple d'itération en ADA
    Afficher le fichier .ada Suite de Fibonacci Exemple de récursion en ADA
    Afficher le fichier .php Suite de Fibonacci Exemple d'itération en PHP
    Afficher le fichier .php Suite de Fibonacci Exemple de récursion en PHP
    Afficher le fichier .java Suite de Fibonacci Exemple de récursion en Java
    Afficher le fichier .rhtml Suite de Fibonacci Exemple d'itération en Ruby
    Afficher le fichier .rhtml Suite de Fibonacci Exemple de récursion en Ruby
    Afficher le fichier .st Suite de Fibonacci
    Afficher le fichier .for Suite de Fibonacci
    Afficher le fichier .asp Suite de Fibonacci Exemple d'itération en ASP
    Afficher le fichier .asp Suite de Fibonacci Exemple de récursion en ASP
    Afficher le fichier .js Suite de Fibonacci Exemple de récursion en JavaScript
    Afficher le fichier .lsp Suite de Fibonacci Exemple de récursion en Lisp
    Afficher le fichier .pl Suite de Fibonacci Exemple d'itération en Perl
    Afficher le fichier .pl Suite de Fibonacci Exemple d'itération en Perl avec bigint
    Afficher le fichier .pl Suite de Fibonacci Exemple de récursion en Perl
    Afficher le fichier .py Suite de Fibonacci Exemple de récursion en Python
    Afficher le fichier .cob Suite de Fibonacci
    Afficher le fichier .e Suite de Fibonacci Exemple d'itération en Eiffel
    Afficher le fichier .e Suite de Fibonacci Exemple de récursion en Eiffel
    Afficher le fichier .scm Suite de Fibonacci Exemple d'itération en Scheme
    Afficher le fichier .scm Suite de Fibonacci Exemple de récursion en Scheme
    Afficher le fichier .caml Suite de Fibonacci Exemple de récursion en Ocaml
    Afficher le fichier .tcl Suite de Fibonacci

Inhaltsverzeichnis Haut

Referenzen

  1. Buch Sprache des Dokuments:fr IHDCB331 - Méthodes de Programmation : PY Schobbens, Cours de Méthodes de Programmation (September 2009)

Diese Verweise und Links verweisen auf Dokumente, die während des Schreibens dieser Seite konsultiert wurden, oder die zusätzliche Informationen liefern können, aber die Autoren dieser Quellen können nicht für den Inhalt dieser Seite verantwortlich gemacht werden.
Der Autor Diese Website ist allein dafür verantwortlich, wie die verschiedenen Konzepte und Freiheiten, die mit den Nachschlagewerken gemacht werden, hier dargestellt werden. Denken Sie daran, dass Sie mehrere Quellinformationen austauschen müssen, um das Risiko von Fehlern zu reduzieren.

Inhaltsverzeichnis Haut