Algorithme de rendu de monnaie⚓︎
On s'intéresse à un algorithme récursif qui permet de rendre la monnaie à partir d'une liste donnée de valeurs de pièces et de billets.
Le système monétaire est donné sous forme d'une liste décroissante fixée :
pieces = [100, 50, 20, 10, 5, 2, 1]
On supposera qu'il n'y a pas de limitation quant à leur nombre.
On cherche à donner la liste de pièces à rendre pour une somme donnée en argument. Compléter le code Python ci-dessous de la fonction rendu_monnaie
qui implémente cet algorithme et renvoie la liste des pièces à rendre. La fonction prend un deuxième entier i
qui correspond à l'indice de la pièce actuellement considérée. Par défaut, il vaut 0
et peut donc être omis lors des tests.
Compléter le code :
pieces = [100, 50, 20, 10, 5, 2, 1]
def rendu_monnaie(a_rendre, i=0):
if a_rendre == 0:
return ...
p = pieces[i]
if p <= ... :
return [...] + rendu_monnaie(..., i)
else :
return rendu_monnaie(a_rendre, ...)
Exemples
>>> rendu_monnaie(68)
[50, 10, 5, 2, 1]
>>> rendu_monnaie(291)
[100, 100, 50, 20, 20, 1]
pieces = [100, 50, 20, 10, 5, 2, 1]bksl-nlbksl-nldef rendupy-undmonnaie(apy-undrendre, i=0):bksl-nl if apy-undrendre == 0:bksl-nl return ...bksl-nl p = pieces[i]bksl-nl if p <= ... :bksl-nl return [...] + rendupy-undmonnaie(..., i)bksl-nl else :bksl-nl return rendupy-undmonnaie(apy-undrendre, ...)bksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlassert rendupy-undmonnaie(68) == [50, 10, 5, 2, 1]bksl-nlassert rendupy-undmonnaie(291) == [100, 100, 50, 20, 20, 1]bksl-nlbksl-nlpieces = [100, 50, 20, 10, 5, 2, 1]bksl-nlbksl-nldef rendupy-undmonnaie(apy-undrendre, i=0):bksl-nl if apy-undrendre == 0:bksl-nl return []bksl-nl p = pieces[i]bksl-nl if p <= apy-undrendre :bksl-nl return [p] + rendupy-undmonnaie(apy-undrendre - p, i)bksl-nl else :bksl-nl return rendupy-undmonnaie(apy-undrendre, i + 1)bksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlassert rendupy-undmonnaie(68) == [50, 10, 5, 2, 1]bksl-nlassert rendupy-undmonnaie(291) == [100, 100, 50, 20, 20, 1]bksl-nlbksl-nl
A
Commentaires⚓︎
version itérative⚓︎
def rendu_monnaie(a_rendre):
solution = []
i = 0
while a_rendre > 0:
if piece[i] > a_rendre:
i += 1
else:
a_rendre -= piece
solution.append(piece)
return solution
Version récursive très discutable...⚓︎
Il ne faut pas utiliser de paramètre par défaut mutable !
def rendu_monnaie(a_rendre, solution=[], i=0):
if a_rendre == 0:
return solution
piece = pieces[i]
if piece <= a_rendre:
solution.append(piece)
return rendu_monnaie(a_rendre - piece, solution, i)
else :
return rendu_monnaie(a_rendre, solution, i + 1)
Version récursive avec fonction interne⚓︎
def rendu_monnaie(a_rendre):
solution = []
def rendu_glouton_rec(a_rendre, i):
"Ajoute à `solution` les pièces à rendre à partir de l'indice `i`"
if a_rendre == 0:
return
piece = pieces[i]
if piece <= a_rendre:
solution.append(piece)
rendu_glouton(a_rendre - piece, i)
else :
rendu_glouton(a_rendre, i + 1)
rendu_glouton_rec(a_rendre, 0)
return solution
Z