Rendu de monnaie 💰☘

Téléchargez le fichier à compléter TPG05.20.py (clic droit -> [Enregistrer sous]) et enregistrez-le dans le dossier [G05_Algo_Glouton].

Consignes communes à chaque partie

Le programme principal contient un appel au module doctest :

##----- Programme principal et tests -----##
if __name__ == '__main__':
    import doctest
    doctest.testmod()

Chacune des fonctions devra passer les tests proposés.
Il faudra aussi ajouter vos propres tests dans le « main » afin de vous entraîner à en réaliser.

Partie A - Implémenter l'algorithme☘

Complétez la définition de la fonction rendu_glouton() qui implémente l'algorithme glouton de rendu de monnaie.

Le paramètre tab_pieces est un tableau des valeurs faciales des pièces et billets disponibles. Ces valeurs sont trièes par ordre décroissant.
a_rendre correspond au montant à rendre, c'est-à-dire à la somme à décomposer en utilisant le moins de pièces possibles parmi les valeurs disponibles dans le tableau tab_pieces.

Enfin, cette fonction renvoie un tableau des valeurs faciales des pièces (et billets) permettant de décomposer le montant a_rendre.

def rendu_glouton(tab_pieces, a_rendre):
    """
    tab_pieces - list, tableau des valeurs faciales disponibles (entières)
                    triée par ordre décroissant et terminant par 1
    a_rendre - int, entier strictement positif (montant à rendre)
    Sortie: list - tableau des valeurs (pièces) nécessaires pour obtenir
            le montant à rendre selon la stratégie gloutonne

    >>> pieces = [50, 20, 10, 5, 2, 1]
    >>> rendu_glouton(pieces, 9)
    [5, 2, 2]
    >>> rendu_glouton(pieces, 47)
    [20, 20, 5, 2]

    >>> pieces = [18, 7, 1]
    >>> rendu_glouton(pieces, 21)
    [18, 1, 1, 1]
    """
    resultat = []
    indice = 0                          # indice d'un élément de tab_pieces
    while...

Une piste

On rappelle ci-dessous la stratégie gloutonne à mettre en place :

On commence par rendre la pièce (ou le billet) de la plus grande valeur possible tout en restant inférieure au montant à rendre ;
On actualise le montant à rendre (par soustraction).
Le montant (qui reste) à rendre est plus petit que le précédent : le problème a été simplifié.
On recommence le 1. jusqu'à obtenir un montant égal à zéro.
On renvoie la liste des « valeurs rendues ».

Partie B - Améliorer l'algorithme☘

La fonction rendu_glouton() définie dans la partie précédente utilise la méthode des soustractions successives.

Étudiez tout d'abord cette page html qui vous rappellera la notion de division apprise à l'école élémentaire.

Complétez la définition de la fonction rendu_glouton2() en utilisant les divisions entières.

def rendu_glouton2(tab_pieces, a_rendre):
    """
    tab_pieces - list, tableau des valeurs faciales disponibles (entières)
                    triée par ordre décroissant et terminant par 1
    a_rendre - int, entier strictement positif (montant à rendre)
    Sortie: list - tableau des valeurs (pièces) nécessaires pour obtenir
            le montant à rendre selon la stratégie gloutonne (avec division)
    >>> pieces = [50, 20, 10, 5, 2, 1]
    >>> rendu_glouton2(pieces, 9)
    [5, 2, 2]
    >>> rendu_glouton2(pieces, 47)
    [20, 20, 5, 2]

    >>> pieces = [18, 7, 1]
    >>> rendu_glouton2(pieces, 21)
    [18, 1, 1, 1]
    """

Une piste

On désigne par $F$ la plus forte valeur de « pièce ».
On peut remarquer que le nombre de pièces (ou billets) de valeur $F$ obtenus par l'algorithme est tout simplement le quotient de la division euclidienne de la somme à payer par $F$ .

Il faut ensuite ajouter autant de fois que nécessaire cette valeur de pièce dans la liste resultat.

Pour aller plus loin, ajoutez une assertion qui vérifie que le tableau des pièces (et des billets) contient bien une pièce de valeur 1.
Profitez-en pour trier par ordre décroissant ce tableau (au cas où).
Exemple de tests
```
>>> pieces = [4, 2]
>>> rendu_glouton2(pieces, 121)
AssertionError: La dernière valeur doit être 1...

>>> pieces = [1, 50, 2, 20, 5, 5]
>>> rendu_glouton2(pieces, 121)
[50, 50, 20, 1]
```

Partie C - Améliorer la réponse☘

En exécutant la fonction rendu_glouton2(), on obtient parfois de très long tableaux :

>>> rendu_glouton2([100, 60, 1], 121)
[100, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

Il semble plus agréable (et pertinent) de renvoyer qu'il y a une valeur 100 et vingt-et-une valeur 1 sous la forme d'un dictionnaire :

>>> rendu_glouton3([100, 60, 1], 121)
{100: 1, 60: 0, 1: 21}

Complétez la définition de la fonction rendu_glouton3() afin qu'elle renvoie un dictionnaire comme dans l'exemple ci-dessus.

def rendu_glouton3(tab_pieces, a_rendre):
    """
    tab_pieces - list, tableau des valeurs faciales disponibles (entières)
                    triée par ordre décroissant et terminant par 1
    a_rendre - int, entier strictement positif (montant à rendre)
    Sortie: dict - dictionnaire qui associe à chaque valeur (pièce) le
            nombre nécessaire pour décomposer le montant à rendre selon la
            stratégie gloutonne

    >>> pieces = [50, 20, 10, 5, 2, 1]
    >>> rendu_glouton3(pieces, 9)
    {50: 0, 20: 0, 10: 0, 5: 1, 2: 2, 1: 0}
    >>> rendu_glouton3(pieces, 47)
    {50: 0, 20: 2, 10: 0, 5: 1, 2: 1, 1: 0}

    >>> pieces = [18, 7, 1]
    >>> rendu_glouton3(pieces, 21)
    {18: 1, 7: 0, 1: 3}
    """

Partie D - Prouver l'optimalité (dans certains cas)☘

Cette partie est à réaliser sur le cahier d'exercice. Contrairement aux parties précédentes, vous trouverez des propositions de solution. Toutefois prenez le temps de formuler et rédiger vos propres réponses avant de vous précipiter sur ces solutions.

Dans chaque question (hormis la dernière), on considère l'algorithme glouton de rendu de monnaie avec les valeurs de pièces (et billets) suivantes : 10€, 5€, 2€, 1€.

On suppose qu'à une certaine étape $i$ , un billet de 5€ a été donné.
Expliquez pourquoi cet algorithme ne donnera pas un autre billet de 5€.

Une réponse
Notons $S$ le montant restant à payer au début de l'étape $i$ .
L'algorithme « distribue » un billet de 5€ au cours de cette étape, cela signifie que $S \geqslant 5$ . Après ce choix, le reste à payer est donc $S-5$ .

Si l'algorithme « distribue » à nouveau un billet de 5€, cela signifie que $S - 5 \geqslant 5$ , soit $S \geqslant 10$ .
Mais dans ce cas, l'algorithme n'aurait pas distribué un billet de 5€ à l'étape $i$ : il aurait choisi un billet de 10€ puisque l'algorithme choisit toujours de donner la plus grande valeur possible.

Par conséquent, le nombre de billets de 5€ donnés avec cet algorithme est toujours 0 ou 1, quel que soit le montant à payer...
En raisonnant de façon analogue à la question précédente, que pouvez-vous dire sur le nombre de pièces de 2€ et le nombre de pièces de 1€ rendues avec cet algorithme glouton.
Les pièces de 2
L'algorithme donnera deux pièces de 2€ au maximum (soit zéro, soit une, soit deux suivant les montants à payer).

Par exemple :
- Pour un montant restant de 5 euros ou plus, l'algorithme cherchera d'abord à rendre 10€ ou 5€.
- Pour un montant restant de 4€, deux pièces de 2€ seront rendues.
- Pour un montant restant de 3€, une pièce de 2€ sera rendue (ainsi qu'une pièce de 1€).
- Pour un montant restant de 2€, une pièce de 2€ sera rendue.
- Pour un montant restant de 1€, aucune pièce de 2€ ne sera rendue.
Pour prouver que l'algorithme ne peut pas donner plus de 2 pièce de 2€, on suit le même raisonnement que précédemment avec 5€ :
- Notons $S$ le montant restant à payer au début de l'étape $i$ .
- On suppose qu'au cours de l'étape $i$ , l'algorithme donne une première pièce de 2€. Cela signifie que $S \geqslant 2$ . Après ce choix, le reste à payer est donc $S-2$ .
- Si l'algorithme « distribue » à nouveau une pièce de 2€, cela signifie que $S - 2 \geqslant 2$ , soit $S \geqslant 4$ . Après ce choix, le reste à payer est donc $S-4$ .
- Si l'algorithme choisit à nouveau une pièce de 2€, on a nécessairement $S - 4 \geqslant 2$ , soit $S \geqslant 6$ . Mais, dans ce cas, l'algorithme n'aurait pas choisi de donner une pièce de 2€ à l'étape $i$ : il aurait choisi une valeur supérieure (un billet de 5€ ou de 10€) puisque l'algorithme choisit toujours de donner le plus grand montant possible.
Par conséquent, le nombre de pièces de 2€ données avec cet algorithme est toujours zéro, une ou deux, quel que soit le montant à payer...
Les pièces de 1
De la même façon, on établit que le nombre de pièces de 1€ rendues avec cet algorithme est 0 ou 1 (reprendre la démonstration de la question précédente avec $S \geqslant 1$ lors de l'étape $i$ ).
Nous avons vus sur des exemples que l'algorithme semble mener à une solution optimale avec liste de valeurs 10€, 5€, 2€, 1€. Comment le prouver ?
1. Combien de billets de 5€ une solution optimale peut-elle utiliser ?
  
  Une piste
  Si on utilisait deux billets de 5€ (ou plus), la solution serait-elle optimale?
  
  Une réponse
  Dans une solution optimale (c'est-à-dire utilisant le moins de pièces et/ou billets possibles pour payer le montant $S$ ), on utilise au maximum un billet de 5€. En effet, si on avait utilisé deux billets de 5€, il suffirait de les remplacer par un billet de 10€ pour avoir une meilleure solution, ce qui contredit le caractère optimal de la solution.
2. Combien de pièces de 2€ une solution optimale peut-elle utiliser ?
  
  Une réponse
  Dans une solution optimale (c'est-à-dire utilisant le moins de pièces et/ou billets possibles pour payer le montant $S$ ), on utilise au maximum deux pièces de 2€. En effet, si on avait utilisé trois pièces de 2€, il suffirait de les remplacer par deux valeurs (un billet de 5€ et une pièce de 1€) pour avoir une meilleure solution, ce qui contredit le caractère optimal de la solution.
3. Combien de pièces de 1€ une solution optimale peut-elle utiliser?
  
  Une réponse
  Dans une solution optimale (c'est-à-dire utilisant le moins de pièces et/ou billets possibles pour payer le montant $S$ ), on utilise au maximum une pièce de 1€. En effet, si on avait utilisé deux pièces de 1€, il suffirait de les remplacer par une pièce de 2€ pour avoir une meilleure solution, ce qui contredit le caractère optimal de la solution.
4. En déduire que le nombre de billets de 10€ utilisés dans une solution optimale est identique à celui du nombre de billets de 10€ utilisés par l'algorithme glouton.
  
  Une réponse
  Dans une solution optimale :
  Pour payer un montant $S$ , on utilise au maximum une pièce de 1€, deux pièces de 2€ et un billet de 5€. On paye donc avec ces valeurs au maximum 1+2+2+5 = 10€.
  
  En fait, on paye strictement moins de 10€ (sinon, en remplaçant ces valeurs par un billet de 10€, on améliorerait la solution, or celle-ci est considérée optimale). On paye donc une somme $r$ d'au maxumum 9€.
  Le nombre $q$ de billets de 10€ donnés vérifie donc : $S = 10q +r$ avec $r < 10$ . $q$ est donc le quotient de la division euclidienne de $S$ par 10, c'est-à-dire exactement le nombre de billets utilisés par l'algorithme glouton.
5. Vérifiez de même que le nombre de billets de 5€ utilisées dans une solution optimale est identique à celui du nombre de billets de 5€ utilisés par l'algorithme glouton.
  
  Une réponse
  Une fois versés les billets de 10€, il nous reste à payer un montant $S$ d'au plus 9€. Le même raisonnement que ci-dessus montre qu'une solution optimale n'utilise qu'au maximum deux pièces de 2€ et au maximum une pièce de 1€. Avec ces pièces, on paye donc au maximum 5€.
  Mais bien sûr on paye en fait au maximum 4€ (car si on paye 5€, on améliorerait la solution avec un billet de 5€).
  Le raisonnement réalisé pour les billets de 10€ montre que le nombre de billets de 5€ dans une solution optimale est exactement le quotient entier de $S$ par 5, c'est-à-dire le nombre de billets de 5€ utilisés par notre algorithme glouton.
6. Terminez le raisonnement pour établir qu'avec la liste de valeurs [10, 5, 2, 1], l'algorithme glouton calcule bien une solution utilisant le plus petit nombre de pièces/billets possibles.
  
  Une réponse
  On montre de même qu'une solution optimale utilise le même nombre de pièces de 2€ que l'algorithme glouton (et a fortiori le même nombre de pièces de 1€). Ainsi les nombres de pièces utilisées dans une solution optimale sont les mêmes que les nombres de pièces utilisées par l'algorithme glouton. L'algorithme glouton est donc optimal avec cette liste de valeurs.
Généralisation : soit $p$ un entier tel que $p\geqslant 2$ .
La liste des valeurs faciales des pièces en cours sont $1, p, p^2, p^3, \dots, p^k$ , où $k$ est un entier naturel.
Prouver que l'algorithme glouton est optimal avec cette liste de valeurs.

Propriété

Une somme de termes en progression géométrique : $$ 1 + p + p^2 + p^3 + \dots + p^k = \frac{p^{k+1}-1}{p-1} $$
Montant R payé avec les pièces $1, p, p^2, p^3, \dots, p^{k-1}$
- Une solution optimale utilise au maximum $p-1$ pièces de valeur $p^{k-1}$ (sinon on peut remplacer $p$ pièces de cette valeur par une seule pièce de valeur $p^k$ , ce qui contredit le caractère optimal de la solution).
- Une solution optimale utilise au plus $p-1$ pièces de valeur $p^{k-2}$ (sinon on peut remplacer $p$ pièces de cette valeur par une seule pièce de valeur $p^{k-1}$ , ce qui contredit le caractère optimal de la solution).
- ...
- Dans une solution optimale, le montant $R$ payé avec les pièces de valeur $1, p, p^2, p^3, \dots, p^{k-1}$ est donc d'au plus $(p-1)(1+p+p^2+p^3+\dots+p^{k-1}) = p^k - 1$ .
Montant payé avec les pièces de valeur $p^{k}$
Dans une solution optimale pour payer le montant $S$ , le nombre $q$ de pièces de valeur $p^k$ utilisées vérifie donc $S = q \times p^k + R$ avec $0 \leqslant R < p^k$ .
En d'autres termes, $q$ est le quotient de la division euclidienne de $S$ par $p^k$ , c'est-à-dire le nombre de pièces de valeur $p^k$ utilisées par notre algorithme glouton.

On poursuit alors le raisonnement avec $k-1$ , puis $k-2$ ... Toute solution optimale utilise donc, pour chaque montant, le même effectif de pièces que notre algorithme glouton.