Vérifier à la main que le rendu glouton de 67 centimes donne quatre…

Dichotomie, voisins et gloutons · Voisins et gloutons · niveau 1 (application)

Énoncé

Vérifier à la main que le rendu glouton de $67$ centimes donne quatre pièces. Que se passe-t-il si l'on passe les pièces en ordre croissant ? sans pièce de $1$ ?

Corrigé


EURO = [200, 100, 50, 20, 10, 5, 2, 1]
assert rendu_monnaie(67, EURO) == [50, 10, 5, 2]
assert rendu_monnaie(0, EURO) == []

try:
    rendu_monnaie(10, [1, 2, 5])        # croissant
    assert False
except AssertionError as e:
    assert "decroissant" in str(e)

try:
    rendu_monnaie(10, [5, 2])           # sans piece de 1
    assert False
except AssertionError as e:
    assert "piece de 1" in str(e)

Les deux préconditions protègent de deux échecs très différents. En ordre croissant, l'algorithme rendrait dix pièces de $1$ : correct mais absurde. Sans pièce de $1$ , il resterait un reste non nul et la postcondition sum(rendu) == somme serait violée — sur $11$ avec [5, 2], il n'existe d'ailleurs aucune décomposition.