Problème du rendu de monnaie (Bac 🎯)⚓︎
Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.
Sources et crédits pour ce cours
Pour préparer ce cours, j'ai utilisé :
- le manuel NSI chez Ellipses de Balabonski, Conchon, Filliâtre, Nguyen dont est tirée la discussion sur les systèmes canoniques (correction de l'exercice 1 question 3).
- le livre part 3 : greedy algorithms and dynamic programming de Tim Roughgarden
- page sur le problème du voyageur de commerce du site Interstices
🔖 Synthèse de ce qu'il faut retenir pour le bac
Un problème d'optimisation⚓︎
Problème du rendu de monnaie
On se place dans la position du caissier qui doit rendre en monnaie un certain montant avec un nombre minimal de pièces. On suppose que le caissier dispose en nombre illimité de toutes les valeurs de pièces disponibles. L'ensemble des valeurs de pièces disponibles constitue le système monétaire.
Il s'agit d'un problème d'optimisation dont la spécification est la suivante :
- Entrée du problème : un montant à rendre et une liste de valeurs de pièces d'un système monétaire ; on suppose qu'on dispose d'un nombre illimité de pièces de chaque valeur
- Sortie du problème : une liste de pièces dont la somme est égale au montant à rendre et dont le nombre de pièces est minimal ; ou une liste vide si le montant ne peut être atteint avec les pièces du système
Une heuristique gloutonne⚓︎
Algorithme glouton de rendu de monnaie
Comme pour le problème du voyageur de commerce, la recherche exhaustive d'une solution n'est pas raisonnable : il faudrait déterminer toutes les décompositions en somme de pièces de la monnaie à rendre. Une heuristique gloutonne de construction d'une solution est assez naturelle et peut se résumer en une phrase :
- tant qu'il reste un montant à rendre on choisit la plus grande valeur de pièce disponible inférieure ou égale à la somme et on la retranche du montant à rendre
Si l'algorithme se termine, sa complexité sera excellente, car le choix de la plus grande pièce possible pourra se faire par une boucle descendante si on a classé les valeurs des pièces par ordre décroissant (le prétraitement dont on a parlé dans les caractéristiques des algorithmes gloutons).
Deux questions peuvent se poser :
- Question 1 : l'algorithme glouton se termine-t-il toujours ?
- Question 2 : l'algorithme glouton est-il exact ?
Exercice 3
Question 1
On considère le système monétaire européen dont les valeurs des pièces par ordre décroissant sont : 500, 200, 100, 50, 20, 10, 5, 2, et 1.
Donner la liste des pièces rendues avec l'algorithme glouton pour un montant de 34 euros, puis de 47 euros.
\(34 = 20 + 10 + 2 + 2\) soit quatre pièces avec l'algorithme glouton.
\(47 = 20 + 20 + 5 + 2\) soit quatre pièces avec l'algorithme glouton.
Question 2
On considère le système monétaire dont les valeurs des pièces par ordre décroissant sont : 30, 24, 12, 6, 3, 1.
L'algorithme glouton rend-il un nombre minimal de pièces sur un montant de 49 euros ?
Avec un algorithme glouton, \(49=30+12+6+1\) ce qui donne un rendu avec quatre pièces. On peut faire mieux en décomposant ainsi : \(49=24 + 24 + 1\) ce qui donne un rendu avec moins de pièces. Dans ce cas l'algorithme glouton n'est pas optimal.
L'optimalité de l'algorithme glouton dépend du système monétaire. Un système monétaire où l'algorithme glouton rend toujours la monnaie en un nombre minimum de pièces est dit canonique. On ne connaît pas de critère simple pour déterminer si un système canonique mais on peut démontrer que le système de l'euro est canonique. Par ailleurs, on peut s'assurer qu'un système est canonique en vérifiant que l'algorithme glouton est optimal pour toutes les sommes inférieures à la somme des deux pièces de valeurs maximales.
Question 3
Donner un exemple de système monétaire et de montant à rendre pour lequel l'algorithme glouton ne se termine pas (en supposant qu'ont peut disposer d'un nombre illimité de pièces de chaque valeur).
Il suffit de prendre un système monétaire sans pièce de \(1\) : il est impossible de rendre la monnaie sur un montant de 1. Si le système monétaire propose de pièces de \(1\), l'algorithme glouton se termine toujours, à condition de ne pas être limité en nombre de pièces de \(1\) !
Exercice 4
💻 Saisir ses réponses sur Capytale
Question 1
Compléter la fonction rendu_glouton qui prend en paramètres un montant à rendre et une liste de valeurs de pièces disponibles dans l'ordre croissant et construit puis renvoie avec l'algorithme glouton, une liste de pièces dont la somme est égale au montant à rendre. On suppose disposer d'un nombre illimité de pièces de chaque sorte.
def rendu_glouton(restant, pieces):
# pieces tableau de valeurs de pièces disponibles dans l'ordre croissant
indice_pieces = len(pieces) - 1
rendu = []
while restant > 0 and indice_pieces >= 0:
if pieces[indice_pieces] <= restant:
restant = restant - pieces[indice_pieces]
rendu.append(pieces[indice_pieces])
else:
indice_pieces = indice_pieces - 1
# rendu possible
return rendu
def test_rendu_glouton():
systeme_euro = [1, 2, 5, 10, 20, 50, 100, 200, 500]
assert rendu_glouton(76, systeme_euro) == [50, 20, 5, 1]
assert rendu_glouton(49, systeme_euro) == [20, 20, 5, 2, 2]
assert rendu_glouton(843, systeme_euro) == [500, 200, 100, 20, 20, 2, 1]
systeme_non_canonique = [1, 3, 6, 12, 24, 30]
assert rendu_glouton(49 , systeme_non_canonique) == [30, 12, 6, 1]
assert rendu_glouton(53 , systeme_non_canonique) == [30, 12, 6, 3, 1, 1]
print("tests réussis pour rendu_glouton")
Question 2
Compléter la fonction récursive rendu_rec qui prend en paramètres un montant à rendre, une liste de valeurs de pièces disponibles dans l'ordre croissant et l'indice de la plus grande pièce possible et qui construit puis renvoie avec l'algorithme glouton une liste de pièces dont la somme est égale au montant à rendre. On suppose disposer d'un nombre illimité de pièces de chaque sorte.
def rendu_rec(restant, pieces, indice_pieces):
# pieces contient les valeurs des pièces disponibles par ordre croissant
if restant == 0:
rep = []
elif pieces[indice_pieces] <= restant:
rep = rendu_rec(restant - pieces[indice_pieces], pieces, indice_pieces)
rep.append(pieces[indice_pieces])
else:
rep = rendu_rec(restant, pieces, indice_pieces - 1)
return rep
def rendu_glouton2(restant, pieces):
return rendu_rec(restant, pieces, len(pieces) - 1)
def test_rendu_glouton2():
systeme_euro = [1, 2, 5, 10, 20, 50, 100, 200, 500]
assert rendu_glouton2(76, systeme_euro) == [1, 5, 20, 50]
assert rendu_glouton2(49, systeme_euro) == [2, 2, 5, 20, 20]
assert rendu_glouton2(843, systeme_euro) == [1, 2, 20, 20, 100, 200, 500]
systeme_non_canonique = [1, 3, 6, 12, 24, 30]
assert rendu_glouton2(49 , systeme_non_canonique) == [1, 6, 12, 30]
assert rendu_glouton2(53 , systeme_non_canonique) == [1, 1, 3, 6, 12, 30]
print("tests réussis pour rendu_glouton2")