Cases remplies
Additions
Appels sans tableau

  • En cours de remplissage
  • Lue
  • Réponse

En savoir plus sur Fibonacci par programmation dynamique

Fibonacci par programmation dynamique

Les nombres de Fibonacci sont le premier exemple classique de programmation dynamique. La récursion simple redemande sans cesse les mêmes termes, mais avec un tableau qui retient chaque terme, le travail ne croît qu'avec n. Choisissez un terme, optez pour la méthode ascendante ou descendante, et avancez pas à pas pour voir chaque case remplie une seule fois. Appuyez sur Lecture pour voir le tableau se remplir, ou sur Étape et Retour pour avancer pas à pas. Faites glisser le curseur d'étapes pour aller n'importe où. Choisissez n, le terme à calculer, et la méthode : Ascendante remplit le tableau à partir de la gauche, Descendante garde la récursion mais regarde d'abord dans le tableau, et la ligne sous le tableau est alors la pile des appels en cours. Nouvel exemple choisit un autre n. Quand le plateau est sélectionné, les flèches avancent ou reculent d'une étape, la barre d'espace lance et met en pause, et Origine et Fin vont au début et à la fin.

Comment ça marche

  1. Saisissez n, le terme à calculer, et choisissez Ascendante ou Descendante.
  2. Appuyez sur Lecture, ou utilisez Étape et Retour pour avancer pas à pas. Faites glisser le curseur d'étapes pour aller n'importe où.
  3. Regardez chaque case lire les deux cases qui la précèdent. Avec Descendante, la ligne sous le tableau est la pile des appels en cours.

Ascendante et descendante

La méthode ascendante (bottom-up), aussi appelée tabulation, part de F(0) = 0 et F(1) = 1 et remplit le tableau de gauche à droite : chaque nouvelle case est la somme des deux cases précédentes. La méthode descendante (top-down), aussi appelée mémoïsation, garde la définition récursive : pour trouver F(n), on demande F(n − 1) et F(n − 2). La différence avec la récursion simple, c'est que chaque appel regarde d'abord dans le tableau et ne calcule un terme que si sa case est encore vide. Les deux remplissent chaque case une fois et font n − 1 additions.

Pourquoi la récursion simple est si lente

Sans tableau, F(n) appelle F(n − 1) et F(n − 2), qui appellent tous deux F(n − 3), et ainsi de suite : les appels forment un arbre où les mêmes termes reviennent sans cesse. Le nombre d'appels est 2·F(n + 1) − 1, qui croît aussi vite que les nombres de Fibonacci eux-mêmes : 177 appels pour F(10), 21 891 pour F(20) et plus de 331 millions pour F(40). Ces sous-problèmes qui se chevauchent sont exactement ce pour quoi la programmation dynamique existe.

Questions fréquemment posées

Qu'est-ce que la programmation dynamique ?

Une façon de résoudre un problème en le découpant en problèmes plus petits qui se chevauchent, en résolvant chacun une seule fois et en gardant sa réponse dans un tableau. Les nombres de Fibonacci sont l'exemple le plus simple : chaque terme se construit à partir des deux précédents.

Quelle est la différence entre mémoïsation et tabulation ?

La mémoïsation garde le code récursif et enregistre chaque réponse la première fois qu'elle est calculée, si bien que les appels suivants n'ont qu'à la lire. La tabulation remplit le tableau dans un ordre qui garantit que chaque réponse dont une case a besoin est déjà là. Les deux font les mêmes additions ; la tabulation évite la pile d'appels, et la mémoïsation ne calcule que les cases réellement nécessaires.

Combien d'additions faut-il pour F(n) ?

n − 1 avec un tableau : une pour chaque terme de F(2) à F(n). Seuls les deux derniers termes sont lus, donc un programme peut aussi ne garder que deux nombres au lieu du tableau entier.

Pourquoi l'application s'arrête-t-elle à n = 40 ?

F(40) = 102 334 155 tient encore facilement à l'écran, et la récursion simple aurait déjà besoin de 331 160 281 appels pour le calculer. Les termes suivants grandissent vite : F(78) est le plus grand qu'un nombre JavaScript représente exactement.

Des données sont-elles envoyées quelque part ?

Non. Tout est calculé dans votre navigateur, et vos derniers réglages restent dans le stockage local de ce navigateur.

Prêt à l'essayer ?

Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.

Aller à l'éditeur