Rendu de monnaie

De nos jours, tous les systèmes de monnaie sont canonique, on peut donc utiliser l'algorithme glouton.

On cherche donc à écrire l'algorithme utilisé par la caisse automatique pour rendre la monnaie.

Question

Écrivez une fonction prochaine_piece, telle que :

  • Entrées :

    • Une liste (pieces) d'entiers triée par ordre croissant représentant un système de monnaie

    • Un entier (valeur) représentant une somme à rendre

  • Sortie : Un entier qui représente la plus grosse pièce (de pieces) pouvant être utilisée pour rendre une partie de valeur.

On admet qu'il existe toujours une pièce valide.

Indice

Le fait que la liste de pièces soit triée est un avantage à prendre en compte.

Question

Écrivez une fonction rendu, telle que :

  • Entrée :

    • Une liste (pieces) d'entiers triée par ordre croissant représentant un système de monnaie

    • Un entier (valeur) représentant une somme à rendre

  • Sortie : La liste de pièces (de pieces) utilisée pour rendre valeur.

Indice

Il s'agit d'appels successif à la fonction prochaine_piece.

Pour le caissier, voir apparaître plusieurs fois la même pièce dans une liste n'est pas pratique ; il préférera voir \(2\times 2€\) plutôt que \(2€, 2€\).

On va donc modifier notre fonction précédente.

Question

Écrivez une fonction rendu_mieux, en modifiant une copie de la fonction rendu, telle que :

  • Entrées :

    • Une liste (pieces) d'entiers triée par ordre croissant représentant un système de monnaie

      Un entier (valeur) représentant une somme à rendre

  • Sortie : Un dictionnaire qui représente pour chaque pièce (de pieces) le nombre de fois où elle est utilisée pour rendre valeur.

    Les pièces n'étant pas utilisées peuvent être présente ou non dans la sortie (au choix de l'élève mais doit être cohérent)