C21.1 : Rendu de monnaie
Présentation du problème
Énoncé
Étant donné un système de monnaie, comment rendre une somme donnée avec le nombre minimal de pièces et de billets ?
Exemple avec le système monétaire européen
Pour rendre 6 €, les combinaisons possibles sont :
• 1 billet de 5 € et 1 pièce de 1 € ;
• 3 pièces de 2 € ;
• 6 pièces de 1 € ;
Le rendu avec le nombre minimal de pièce ou billets et le premier.
Proposition de solution
Démarche générale
🖊️ Proposer une méthode systématique pour répondre à ce problème.
Programmation de la solution
Le système monétaire choisi sera stocké dans une liste du plus grand au plus petit. Ex : liste_euro = [200, 100, 50, 20, 10, 5, 2, 1].
La combinaison retenue sera présentée sous la forme d'une liste dont la somme des valeurs est égale au montant à rendre : liste_rendu = [20, 5, 2, 2].
💻 Proposer une fonction qui prend le montant à rendre et le système monétaire en paramètre et renvoie la combinaison optimale.
Algorithmes glouton
Les problèmes d'optimisation
En informatique, les problèmes d'optimisation sont des problèmes pour lesquels on cherche la meilleure solution suivant un critère donné (critère d'optimisation).
La force brute
L'une des méthodes pour répondre à ce type de problème consiste :
- à rechercher de façon exhaustive toutes les solutions,
- à trier ces solutions suivant le critère d'optimisation,
- à garder la solution optimale.
Cette méthode, dite par force brute, peut être valable pour des problèmes faisant appel à un petit nombre de données. Cependant, elle n'est souvent pas envisageable avec un grand nombre de données.
La méthode gloutonne
La méthode gloutonne consiste à découper le problème en étapes successives similaires et plus simples que le problème global. Il s'agit alors, pour chaque étape, de rechercher une solution optimale (dite solution locale), sans modifier les résultats des étapes précédentes.
Remarque : en général, la méthode gloutonne conduit à une solution approchée.
Complément : système monétaire canonique
Un exemple qui pose problème...
Considérons le système monétaire constitué des trois pièces suivantes : 1, 3 et 4.
🖊️ Quelle est la combinaison de pièces qui contient le moins de pièces pour rendre la valeur 6 ?
💻 Quelle combinaison l'algorithme glouton va-t-il proposer ? Conclure.
Système canonique
Un système monétaire est dit canonique lorsque l'algorithme glouton donne une solution optimale.
Actuellement tous les systèmes monétaires du monde sont des systèmes canoniques.