GoupillWiki

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.
====== Problème du rendu de monnaie ======

===== Présentation =====

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.

===== Algorithme glouton =====

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.

===== Implémentation dans un cas général =====

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 :

<code python>
PIECES = (50000, 20000, 10000, 5000, 2000, 1000, 500, 200, 100, 50, 20, 10, 5, 2, 1)
</code>

  * //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.

<code python>
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 []
</code>