rendre la monnaie

On considère dans cet exercice un algorithme glouton pour le rendu de monnaie. Pour rendre une somme en monnaie, on utilise à chaque fois la plus grosse pièce possible et ainsi de suite jusqu’à ce que la somme restante à rendre soit nulle.

Les pièces de monnaie utilisées sont :

pieces = [1, 2, 5, 10, 20, 50, 100, 200]

On souhaite écrire une fonction rendu_monnaie qui prend en paramètres

  • un entier somme_due représentant la somme à payer ;
  • un entier somme_versee représentant la somme versée qui est supérieure ou égale à somme_due ;

et qui renvoie un tableau de type list contenant les pièces qui composent le rendu de la monnaie restante, c’est-à-dire de somme_versee - somme_due.

Ainsi, l’instruction rendu_monnaie(452, 500) renvoie le tableau [20, 20, 5, 2, 1].

En effet, la somme à rendre est de 48 euros soit 20 + 20 + 5 + 2 + 1.

Compléter le code ci dessous, puis le tester :

A tester
>>> rendu_monnaie(700, 700)
[]
>>> rendu_monnaie(102, 500)
[200, 100, 50, 20, 20, 5, 2, 1]
Compléter ci-dessous

###
# Testsbksl-nlassert rendupy-undmonnaie(452, 500) == [20, 20, 5, 2, 1]bksl-nlbksl-nl# Autres testsbksl-nlassert rendupy-undmonnaie(452, 500) == [20, 20, 5, 2, 1]bksl-nlassert rendupy-undmonnaie(100, 100) == []bksl-nlassert rendupy-undmonnaie(102, 500) == [200, 100, 50, 20, 20, 5, 2, 1]bksl-nlassert rendupy-undmonnaie(101, 500) == [200, 100, 50, 20, 20, 5, 2, 2]bksl-nlbksl-nl 5/5
pieces = [1, 2, 5, 10, 20, 50, 100, 200]bksl-nlbksl-nldef rendupy-undmonnaie(sommepy-unddue, sommepy-undversee):bksl-nl '''Renvoie la liste des pièces à rendre pour rendre la monnaiebksl-nl lorsqu'on doit rendre sommepy-undversee - sommepy-unddue'''bksl-nl rendu = ... bksl-nl apy-undrendre = ... bksl-nl i = len(pieces) - 1bksl-nl while apy-undrendre > ...: bksl-nl while pieces[i] > apy-undrendre:bksl-nl i = i - 1bksl-nl rendu.append(...) bksl-nl apy-undrendre = ... bksl-nl return rendubksl-nlbksl-nl# Testsbksl-nlassert rendupy-undmonnaie(452, 500) == [20, 20, 5, 2, 1]bksl-nlbksl-nlpieces = [1, 2, 5, 10, 20, 50, 100, 200]bksl-nlbksl-nldef rendupy-undmonnaie(sommepy-unddue, sommepy-undversee):bksl-nl '''Renvoie la liste des pièces à rendre pour rendre la monnaiebksl-nl lorsqu'on doit rendre sommepy-undversee - sommepy-unddue'''bksl-nl rendu = [] bksl-nl apy-undrendre = sommepy-undversee - sommepy-unddue bksl-nl i = len(pieces) - 1bksl-nl while apy-undrendre > 0: bksl-nl while pieces[i] > apy-undrendre:bksl-nl i = i - 1bksl-nl rendu.append(pieces[i]) bksl-nl apy-undrendre = apy-undrendre - pieces[i] bksl-nl return rendubksl-nl

On a ici un algorithme glouton, car on part de la fin de la liste pieces qui est triée par ordre croissant.

Dans l'algorithme de rendu de monnaie vu en cours, la liste des pièces était triée par ordre décroissant, et donc l'algorithme la parcourait à partir du début.