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 :

• 2 € + 2 € + 50 c + 2 c
• 2 € + 1 € + 50 c + 50 c + 20 c + 20 c + 10 c + 2 c
• etc.

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 :

• de la somme à rendre
• des pièces disponibles

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 €,

• La pièce la plus grosse pouvant être utilisée est 2 €.
• Une fois rendu 2 €, il reste 2,52 € à rendre. On peut encore rendre une pièce de 2 €.
• Il reste 52 c à rendre. La plus grosse pièce possible est 50 c.
• Il reste 2 c à rendre. La plus grosse pièce possible est 2c.

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)

• Les valeurs sont données en centimes pour que l'on n'ait que des nombres entiers.
• Vous pouvez considérer que le tuple est trié de la valeur la plus forte à la plus faible.

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 []