1  Approche gloutonne

1. Une première question est celle de la possibilité de payer. Trouver une condition nécessaire et suffisante pour qu'un système monétaire permette de payer n'importe quel montant.
   
   
2. Une seconde question est de payer avec le minimum d'espèces (paiement optimal).
   
   Décrire une approche gloutonne du paiement optimal.
   
   
3. Programmer l'approche gloutonne.

   static int [] glouton(int [] d, int m) ;

   Pour un système monétaire ⟨ d₀, d₁, … d_k-1 ⟩ et un montant m, La méthode (statique) glouton renvoie un tableau d'entiers t tel que.

   k-1 ∑ i=0

   ti × di = m

   Attention, on se contraindra à atteindre une complexité en O(k).
   
   Au passage et plus précisément, les paiements sont représentés par des tableaux t de taille k. Le cardinal d'un paiement est tout bêtement le nombre d'espèces concrètes dans un paiement, c'est-à-dire la somme des t_i. Un paiement de m est optimal quand son cardinal est minimal parmi ceux des paiements de m.
   
   
4. On va montrer que la stratégie gloutonne est optimale dans le cas du système européen.
   
   Soit un paiement donné T = ⟨ t₀, t₁, …, t_k-1 ⟩, on note V_i(T) le montant obtenu en annulant tous les t_j de 0 à i-1.

   V

   i(T) =

   k-1 ∑ j=i

   tj × dj

   (On constate que si T est un paiement optimal, T_i obtenu en annulant tous les t_j de 0 à i-1 est également un paiement optimal.)
   1. Montrer que, dans système européen et pour tout paiement T optimal on a :
      V_i(T) < d_i-1
      Le plus simple me semble de compléter le tableau suivant, qui donne pour chaque entier i entre 9 et 2, le plus grand V_i(T) possible (noté b_i).

      i	8	7	6	5	4	3	2	1
      di-1	2	5	10	20	50	100	200	500
      bi	1	4

      La borne b₈ s'explique en considérant que T optimal ne peut pas contenir plus d'une pièce d'un euro (car on peut remplacer deux pièces d'un euro par une pièce de deux euros). La borne b₇ s'explique de façon à peine plus complexe, T optimale ne peut pas contenir 3 pièces de deux euros ou plus (par le remplacement 2 + 2 + 2 → 5 + 1), et deux pièces de deux euros ne peuvent être accompagnées d'une pièce d'un euro (car 1 + 2 + 2 = 5).
      
      
   2. Monter que la condition ci-dessus entraîne l'optimalité de la stratégie gloutonne.
   
   
   
5. Montrer que la stratégie gloutonne n'est pas optimale dans le cas du système britannique.

2  Recherche exhaustive

1. Décrire une technique inductive pour engendrer l'ensemble des paiements d'une somme donnée m dans un système donné (d_i).
   
   
2. Écrire une méthode tous, qui affiche tous les paiements possibles.

   static void tous(int [] d, int m)

   
   On suppose donnée une méthode d'affichage dump que voici :

   static void dump(PrintStream out, int [] system, int [] t) {     for (int i = 0 ; i < t.length ; i++) {       int d = system[i] ;       for (int j = 0 ; j < t[i] ; j++)         out.print(" " + d) ;     }     out.println() ;   }

   
   Dans ce type de programmes (comme par exemple dans le devoir maison numéro deux, ou le contrôle hors-classement) on essaie d'éviter d'allouer trop. Représentons un paiement par le tableau des t_i (un tableau t) de taille k (nombre d'espèces du système).
   
   Il s'agit en gros de fabriquer tous les t possible. Une solution économique en espace utilisera une méthode zyva.

   static void zyva(int [] d, int m, int i, int [] t)

   Dans un appel à zyva, le tableau t n'est « rempli » que de 1 à i-1 et m est un prix à atteindre en utilisant seulement les espèces d'indice supérieur ou égal à i. Les arguments t, i, et m sont liés :

   m +

   i-1 ∑ j=0

   tj × dj = m0

   (Où m₀ est le prix initial.)
   
   Ainsi tous s'écrit très simplement :

   static void tous(int [] d, int m) {     zyva(d, m, 0, new int[d.length]) ;   }

   
   
   
3. Transformer tous en exhaustif, qui renvoie une somme optimale.

   static int [] exhaustif(int [] d, int m)

   
   
   
4. Il n'est pas besoin de parcourir tous les paiements possibles pour trouver un paiement optimal. En effet supposons connu un paiement de cardinal c₀. Pour un appel donné de zyva, on dispose d'un paiement partiel ⟨ t₀, t₁, …, t_i-1 ⟩ de cardinal c, et il reste à payer m à l'aide des espèces ⟨ d_i, d_i+1, …, d_k-1 ⟩. On ne peut certainement pas compléter t en un paiement optimal dans les deux cas suivants :
   • Si c est déjà strictement supérieur à c₀.
   • Si la somme maximale payable à l'aide de c₀-c espèces d_i est strictement inférieure à m.
   On peut alors élaguer la recherche, c'est-à-dire renoncer à compléter le paiement partiel t. Modifier la recherche exhaustive pour profiter de ces remarques.

3  Paiement dynamique

1. Expliquer le commentaire de la ligne 5.
   
   
2. Comment comprendre la boucle des lignes 9-10 ? Pourquoi termine-t-elle toujours ?
   
   
3. Montrer que tous les accès dans les tableaux sont légaux.
   
   
4. Donner le coût de la méthode dynamiqueCard.
   
   
5. Argumenter la correction de la méthode dynamiqueCard. On se contentera d'une définition inductive de M(n), cardinal d'un paiement optimal de n.
   
   
6. Comment faire pour trouver un paiement optimal de m et non plus seulement son cardinal ?

Note

Ce document a été traduit de L^AT_EX par H^EV^EA et H^AC^HA.