Le but de cet exercice est de déterminer le nombre minimal de pièces à utiliser pour rendre un certain montant m (qui est ici un nombre entier) à un client. On suppose que l'on dispose d'un nombre illimité de chaque type de pièces. La présence de pièces de valeur 1 garantit que l'on peut toujours trouver les pièces pour un montant donné.
Systèmes monétaires et algorithme glouton
Deux exercices proposent des solutions utilisant un algorithme glouton (Rendu de monnaie et Rendu de monnaie (récursif)), qui consiste à toujours rendre d'abord les pièces de plus grande valeur.
Prenons l'exemple où les pièces possibles ont pour valeur 1, 4 et 6. Avec un algorithme glouton rendre 8 nécessite trois pièces : une de 6, et deux de 1. Ce n'est pas la solution attendue car on peut utiliser seulement deux pièces de 4. L'algorithme glouton donne la meilleure réponse seulement dans le cas où le système monétaire (les pièces ou billets que l'on peut utiliser) est dit canonique. Ce n'est pas forcément le cas dans cet exercice.
Pour un montant \(m\), on peut rendre une pièce de valeur \(p\) avec \(p \leq m\) et le montant \(m - p\). Pour résoudre le problème pour un montant \(M\), nous allons résoudre tous les problèmes pour tous les montants \(m\) allant de \(1\) à \(M\) compris. Nous utiliserons un tableau memo pour mémoriser les résultats calculés. memo[i] est le nombre minimal de pièces à rendre pour un montant i.
memo[m] sera donc égal au nombre \(1\) auquel on ajoute le plus petit des résultats memo[m-p] avec p valeur d'une pièce inférieure ou égale à m.
On peut initialiser memo avec pour tout entier i : memo[i]=i. En effet memo[0]=0, et pour tout i strictement positif, on peut rendre i pièces de valeurs \(1\).
Compléter la fonction rendu_monnaie qui prend en paramètres un entier montant représentant le montant à rendre et la liste pieces représentant la liste des pièces utilisables, qui renvoie le nombre minimal de pièces à utiliser pour rendre ce montant.
... peut représenter plusieurs lignes de code.
###(Dés-)Active le code après la ligne # Tests (insensible à la casse) (Ctrl+I)
Entrer ou sortir du mode "deux colonnes" (Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran" (Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)