Aller au contenu

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 :

🐍 Script Python
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 :

🐍 Script Python
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

🐍 Console Python
>>> rendu_monnaie(68)
[50, 10, 5, 2, 1]
>>> rendu_monnaie(291)
[100, 100, 50, 20, 20, 1]
# testsbksl-nlbksl-nlassert rendupy-undmonnaie(68) == [50, 10, 5, 2, 1], "Erreur sur ce test"bksl-nlassert rendupy-undmonnaie(291) == [100, 100, 50, 20, 20, 1], "Erreur sur ce test"bksl-nlbksl-nlbksl-nl# autres testsbksl-nlbksl-nlassert rendupy-undmonnaie(0) == []bksl-nlassert rendupy-undmonnaie(1) == [1]bksl-nlassert rendupy-undmonnaie(2) == [2]bksl-nlassert rendupy-undmonnaie(sum(pieces)) == piecesbksl-nlassert rendupy-undmonnaie(4) == [2, 2]bksl-nlassert rendupy-undmonnaie(500) == [100, 100, 100, 100, 100]bksl-nlbksl-nl ∞/∞

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⚓︎

🐍 Script Python
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 !

🐍 Script Python
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⚓︎

🐍 Script Python
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

Retour en haut de la page