Vous achetez un sandwich à 5,48 € et vous payez avec un billet de 10 €. Le vendeur doit vous rendre 4,52 €. Comment peut-il vous rendre cette somme ?
Quelques exemples :
Parmi toutes ces possibilités, on cherche celle qui utilise le moins de pièces
Je ne parlerai que de pièces, mais cela pourrait être des billets, peu importe.
La réponse attendue dépend donc :
Dans ce problème, on considère que le vendeur n'a pas de problème de monnaie, il n'est pas à cours de pièces de 2 € ou autre. Quand je parle de pièces disponibles, je veux parler des pièces existantes dans la monnaie considérée. Il n'y a pas de pièces de 3 € par exemple.
Pour résoudre le problème de rendu de monnaie, l'algorithme glouton consiste à choisir la plus grosse pièce possible. Par exemple, pour rendre 4,52 €,
L'algorithme glouton consistera donc à choisir la solution 2 € + 2 € + 50 c + 2 c, soit 4 pièces.
On souhaite implémenter cet algorithme. On ne veut pas se limiter au cas normal des pièces disponibles en euros. On veut un cas plus général pour pouvoir utiliser notre programme même dans un pays qui utiliserait des pièces de valeurs différentes.
On utiliser un tuple PIECES pour indiquer les pièces disponibles. En euro on aurait :
PIECES = (50000, 20000, 10000, 5000, 2000, 1000, 500, 200, 100, 50, 20, 10, 5, 2, 1)
Vous devez programmer une fonction rendu qui, en fonction de la somme à rendre et des pièces disponibles, renvoie un tableau donnant les pièces rendues.
def rendu(a_rendre, pieces):
'''
a_rendre: somme à rendre
pieces: tuple contenant les pièces disponibles
renvoie les pièces utilisées
exemple :
si a_rendre = 452 et pieces = PIECES,
renvoie [200, 200, 50, 2]
'''
# à compléter
return []