Modifier rendu monnaie pour qu'il renvoie un dictionnaire \{valeur

def rendu_dictionnaire(somme, pieces):
    """{valeur: nombre} au lieu d'un tableau.

    Postcondition : sum(v * n for v, n in resultat.items()) == somme, et
                    aucune entree de valeur nulle.
    """
    assert somme >= 0
    assert pieces == sorted(pieces, reverse=True), "pieces doit etre decroissant"
    assert 1 in pieces, "sans piece de 1, la decomposition peut echouer"
    rendu, reste = {}, somme
    for p in pieces:
        n = reste // p
        if n > 0:
            rendu[p] = n
            reste = reste - n * p
    assert sum(v * n for v, n in rendu.items()) == somme
    assert all(n > 0 for n in rendu.values())
    return rendu

La postcondition change de forme, pas de sens. Elle passe de sum(rendu) == somme à une somme pondérée : chaque clé compte autant de fois que sa valeur associée. C'est la traduction exacte de la même exigence dans la nouvelle structure.

Une seconde postcondition apparaît, et elle est propre au dictionnaire : aucune entrée ne doit valoir zéro. Rien ne l'imposait avec un tableau — on n'y écrit pas « zéro pièce de 20 ». Ici, il faut le décider : le if n > 0 choisit de ne pas créer l'entrée, ce qui rend len(rendu) égal au nombre de types de pièces effectivement utilisés.

La boucle while disparaît. La division entière reste // p donne d'un coup le nombre de pièces que la boucle intérieure aurait ajoutées une à une. Le variant du cours — « reste décroît strictement » — devient inutile puisqu'il n'y a plus qu'une boucle for sur un tableau fini.

Vérification.

EURO = [200, 100, 50, 20, 10, 5, 2, 1]
assert rendu_dictionnaire(67, EURO) == {50: 1, 10: 1, 5: 1, 2: 1}
assert rendu_dictionnaire(0, EURO) == {}
assert rendu_dictionnaire(999, EURO) == {200: 4, 100: 1, 50: 1, 20: 2, 5: 1, 2: 2}

for _ in range(2000):
    s = random.randint(0, 500)
    d = rendu_dictionnaire(s, EURO)
    assert sum(v * n for v, n in d.items()) == s
    assert sum(d.values()) == len(rendu_monnaie(s, EURO))   # MEME nombre de pieces

Le dernier assert est le plus intéressant : il confronte les deux versions. Elles ne renvoient pas la même chose, mais elles doivent rendre le même nombre de pièces — sinon l'une des deux ne serait pas le même algorithme.