On dispose de pièces de ⑤ , de pièces de ② et de pièces de ① .
On doit rendre la monnaie d'une valeur n
. On doit faire l'appoint.
Par exemple pour constituer 13, on peut faire ⑤⑤②① car 5+5+2+1=13.
Comme le nombre de pièces de ⑤ , de pièces de ② et de pièces de ① dépend de
n
, on demande d'écrire une fonction Python. Elle prend en
argument un entier n
et renvoie un triplet d'entiers (nombre de pièces
de ⑤ , de pièces de ② et de pièces de ① ).
def monnaie(n): assert n>0 and int(n)==n cinq,deux,un = 0,0,0 while n>=5: cinq += 1 n -= 5 while n>=2: deux += 1 n -= 2 while n>=1: un += 1 n -= 1 return cinq,deux,un
from collections import namedtuple Bourse = namedtuple('Bourse','cinq deux un') def monnaie(n): assert n>0 and int(n)==n (c,d,u) = (0,0,0) while n>=5: c += 1 n -= 5 while n>=2: d += 1 n -= 2 while n>=1: u += 1 n -= 1 return Bourse(cinq=c, deux=d, un=u)
Dans cette version, on renvoie une chaîne de caractères.
def monnaie(n): N = n assert n>0 and int(n)==n (c,d,u) = (0,0,0) while n>=5: c += 1 n -= 5 while n>=2: d += 1 n -= 2 while n>=1: u += 1 n -= 1 assert 5*c+2*d+u==N return c*' ⑤ '+d*' ② '+u*' ① '
On a ce genre de résultats :
1 ① 2 ② 3 ② ① 4 ② ② 5 ⑤ 6 ⑤ ① 7 ⑤ ② 8 ⑤ ② ① 9 ⑤ ② ② 10 ⑤ ⑤ 11 ⑤ ⑤ ① 12 ⑤ ⑤ ② 13 ⑤ ⑤ ② ① 14 ⑤ ⑤ ② ② 15 ⑤ ⑤ ⑤ 16 ⑤ ⑤ ⑤ ① 17 ⑤ ⑤ ⑤ ② 18 ⑤ ⑤ ⑤ ② ① 19 ⑤ ⑤ ⑤ ② ②
La somme d'argent restant à rembourser est un variant : à chaque étape de l'algorithme, elle diminue de 5, de 2 ou de 1. Son existence garantit que l'algorithme glouton termine.
L'algorithme est correct parce qu'il a un invariant : c'est le fait que
5*c+2*d+u==N
, autrement dit, la quantité 5×⑤+2×②+① déjà remboursée,
additionnée au variant, donne la somme totale (initialement à rembourser). En
effet il n'y a ni création, ni destruction de monnaie dans la transaction.
L'algorithme glouton ne donne jamais plus d'une pièce de ① et jamais plus de 2
pièces de ②. Les calculs sur les pièces autres que ⑤ (addition et soustraction) sont
donc effectués moins de 3 fois. Le calcul du nombre de pièces de ⑤ nécessite moins de
n/5+1
additions (et soustractions). L'algorithme est donc de
complexité linéaire.