Flashcards: Programmation dynamique : Fibonacci et rendu monnaie — 22 cards

Suite de Fibonacci — définition ?

Suite numérique où chaque terme est la somme des deux précédents.

Problème de redondance — dans Fibonacci ?

Appels récursifs répétés avec mêmes paramètres, gaspillage de temps.

Programmation dynamique — rôle ?

Éviter les recalculs en mémorisant résultats intermédiaires.

Mémoire cache — utilité ?

Stocker résultats pour éviter recalculs redondants.

Forme Top Down — approche ?

Récursive, vérifie la mémoire avant de calculer.

Forme Bottom Up — approche ?

Itérative, calcule du plus petit sous-problème vers le grand.

Fibonacci Top Down — principe ?

Mémoïsation pour rendre le calcul efficace et sans redondance.

Récursion Fibonacci — problème ?

Appels multiples avec mêmes paramètres, inefficace.

Rendu monnaie — objectif ?

Minimiser le nombre de pièces pour une somme donnée.

Problème récursif rendu monnaie ?

Minimiser nbre de pièces avec formule : nbre[som] = 1 + min(nbre[som - pi]).

Appels récursifs redondants — dans rendu monnaie ?

Même sous-problèmes résolus plusieurs fois, inefficace.

Programmation dynamique rendu monnaie — méthode ?

Mémoïsation avec cache pour stocker résultats intermédiaires.

Mémoire cache — construction ?

Tableau ou liste de taille som+1, initialisé à zéro.

Garde — rôle ?

Enregistrer l’indice de la pièce utilisée pour chaque somme.

Algorithme rendu monnaie — étape clé ?

Reconstruction de la liste pièces via garde après calcul.

Algorithme modifié — pour liste pièces ?

Retourne à la fois nombre et composition des pièces.

Exemple rendu monnaie — résultat ?

Pour somme 9, solution optimale : [2,2,5].

Problème Fibonacci — formule récursive ?

fib(n) = fib(n-1) + fib(n-2), avec conditions de base.

Approche Bottom Up — principe ?

Calculer en ordre croissant, stocker dans tableau.

Approche Top Down — principe ?

Récursion avec mémoïsation, vérifie cache avant calcul.

Optimisation rendu monnaie — avantage ?

Réduction du nombre d’appels, calcul plus rapide.

Mémoïsation — différence avec programmation dynamique ?

Mémoïsation est une technique, PD est une stratégie globale.