Exercice : Rendu de monnaie

Un commerçant doit rendre de la monnaie à l'un de ses clients en minimisant le nombre de pièces et de billets possibles. On admettra par la suite que le commerçant dispose toujours de la réserve nécessaire dans chaque espèce monétaire.

Question

En prenant pour exemple la monnaie européenne et en oubliant les centimes, si le commerçant doit rendre 9 euros, donner toutes les combinaisons possibles de pièces et de billets. Extraire celle qui minimise le nombre de pièces et de billets.

Solution

Le commerçant a 8 combinaisons qui utilisent entre 3 et 9 espèces. La combinaison permettant de minimiser est celle bien entendu d'utiliser deux pièces de 2€ et un billet de 5€.

Question

En prenant pour exemple la monnaie européenne et en oubliant les centimes, déterminer la stratégie pour rendre la monnaie sur un montant inférieur à 50 € de tel sorte que le nombres de pièces et de billets soit minimal.

Indice

On peut commencer par le billet ou la pièce qui a la plus grande valeur...

Solution

La stratégie gloutonne pour résoudre ce problème va consister à prendre la monnaie la plus grande (autant de fois que nécessaire) et de la retirer de la somme à rendre. Il faudra répéter cette opération jusqu'à ce la somme à rendre soit nulle.

En reprenant l'exemple précédent, admettons que le commerçant adopte cette méthode, il procédera alors ainsi :

• Il tente de donner 10€, ce n'est pas possible car trop grand

• Il donne 5€, il reste donc 4€ à rendre au client

• Il tente de donner 5€, ce n'est pas possible car trop grand

• Il donne 2€, il reste donc 2€ à rendre au client

• Il donne 2€, il ne reste plus rien à rendre au client

Question

Écrire un programme qui implémente cet algorithme. On utilisera la monnaie européenne avec des espèces allant de 20€ à 1€.

Pour une somme à rendre, le programme affichera par exemple les messages suivants :

Indice

Vous avez une liste d'entiers reprenant les différentes valeurs des espèces que l'on appellera espece et qui sera définie ainsi :

1
espece=[20,10,5,2,1]

Solution

1
def rendu_monnaie(montant, espece):
2
    rendu = {}
3
    for coin in espece:
4
        if montant // coin != 0:
5
            rendu[coin] = montant // coin
6
            montant = montant % coin
7
    return rendu
8
Question
Que donne votre programme avec le système de pièces (4, 3, 1 )
Solution
Dans le système de pièces (1, 3, 4), l'algorithme glouton n'est pas optimal, comme le montre l'exemple simple :
le programme donne 6  = 4+1+1, alors que 3+3 est optimal.