Algorithme glouton

I/ Position du problème

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 ① ).

Solution

Version tuple

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

Version tuple nommé

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)

Avec postcondition

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  ⑤  ⑤  ⑤  ②  ② 

Propriétés

Variant

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.

Invariant

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.

Complexité

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.