Autour du rendu de monnaie

Ce qui suit donne des réponses pour le TD sur le rendu de monnaie. Les démonstrations sont délibérément très détaillées

Question 1

Décomposition: 28€43 = 20€ + 5€ + 2€ + 1€ + 20c + 20c + 2c + 1c

Optimalité:

• Parce qu’on part des pièces de plus grande valeur ?
  Ce n’est pas une démonstration, juste une intuition.
• Quelque chose à voir avec les diviseurs de 10 ?
  À préciser.

Le but de ce qui suit est de mieux comprendre ce problème.

Question 2

En prenant les plus grandes pièces disponibles chaque fois, on obtient: 49 = 30 + 12 + 6 + 1

Cette décomposition n’est pas optimale parce u’on peut faire mieux: 49 = 24 + 24 + 1

Cette second proposition est optimale. Pour le justifier, il suffit de remarquer qu’aucune somme de deux pièces de vaut 49 (et bien sûr qu’aucune pièce seule ne vaut 49).

Question 3

On peut décomposer toutes les valeurs de v si et seulement si la plus petite pièce vaut 1 (donc s₁ = 1).

Justification:

• Si on a 1, on peut faire toutes les sommes (puisqu’un on ne considère que des sommes entières);
• si on n’a que des valeurs strictement plus grandes que 1, on ne peut pas faire 1.

Question 4 : algorithme glouton

Entrée:

• le système S = (s₁,...,s_n)
• la valeur v

Sortie:

• une décomposition D = (d₁,...,d_n) telle que $\sum_{i=1}^n d_i s_i = v$

Première proposition:

Une autre proposition fondée sur la division euclidienne:

C ’est équivalent sauf que le premier décompose explicitement la division euclidienne en soustractions successives.

Question 5 : terminaison

Toutes les boucles sont basées sur la valeur d’une variable entière qui sera strictement décroissante, avec une condition d’arrêt qui impose qu’elle reste positive, donc il ne peut y avoir qu’un nombre fini d’itérations.

Question 6 : correction

On cherche un invariant de boucle. On part de la formulation suivante de l’algorithme par division:

L’invariant doit faire intervenir D, r, i et aussi v et S.

Le principe de l’algorithme (et aussi de celui par soustraction successives) est de décomposer progressivement la valeur initiale en ajoutant des pièces à la décomposition: à tout moment la liste D contient un certain nombre de pièces pour la partie déjà décomposée et r indique ce qu’il reste à faire. Précisément, au début de l’itération pour i le tableau D est supposé défini à partir du rang i + 1 puisque le but de l’itération est de définir d_i. La propriété invariante est donc:

r + ∑_j > id_j × s_j = v

Notons cette propriété P(i). On la vérifie par récurrence.

Initialisation

On a i = n donc on n’a aucun j tel que j > n, donc on a ∑_j > id_j × s_j = 0 or r = v après la première instruction donc P(n) est vérifié lorsqu’on entre dans la boucle.

Étape de récurrence

On suppose que l’invariant P(i) est satisfait au début de l’itération numéro i on veut montrer que P(i−1) est vérifié au début de l’itération i − 1. Pour cela on montre que P(i−1) est vérifié à la fin de l’itération i.

Au cours de l’itération i, la valeur des d_j pour j > i ne change pas, la valeur de d_i est définie et celle de r est modifiée. On note r′ la valeur de r après modification. Alors par définition on a d_i = ⌊r/s_i⌋ et r′ = r − d_i × s_i, donc r = r′ + d_i × s_i.

Par l’hypothèse P(i), on a r + ∑_j > id_j × s_j = v donc par définition de r′ on a r′ + d_i × s_i + ∑_j > id_j × s_j = v et en rassemblant d_i × s_i avec la somme on en déduit r′ + ∑_{j > i − 1}d_j × s_j = v cette dernière égalité est exactement P(i−1).

Sortie de boucle

La dernière itération correpond à i = 1, donc par l’étape de récurrence la propriété P(0) est satisfaite en sortie de boucle:

$$ r + \sum_{j=1}^n d_j s_j = v $$

Par ailleurs on a par hypothèse s₁ = 1, donc lors de l’itération i = 1, on a un reste nul puisqu’on fait une division par 1, par conséquent en fin d’itération on a r = 0. On peut simplifier l’invariant en $$ \sum_{j=1}^n d_j s_j = v $$ qui est la propriété voulue.

Question 7

On a un contre-exemple dans la question 2.

Questions 8 et 9

Le principe de l’algorithme gouton est de décomposer une somme en utilisant autant que possible de pièces de la valeur maximale puis de recommencer avec la somme restante et le même système de pièces sans la plus grande. Pour prouver que cet algorithme donne un résultat optimal dans tous les cas pour un système (s₁,…,s_n) donné, on peut démontrer qu’il est optimal pour tous les systèmes (s₁,…,s_i) avec 1 ≤ i ≤ n, par récurrence sur i.

On commence par des observations générales qui s’appliqueront aux systèmes particuliers que l’on regarde.

Initialisation

Dans les systèmes considérés, on a toujours s₁ = 1. Dans ce cas, pour une somme v, il y a touours une décomposition et une seule, avec d₁ = v, et l’algorithme glouton produit effectivement ce résultat. Le système composé d’une seule pièce de valeur 1 est donc canonique.

Étape de récurrence

Soit un système (s₁,…,s_n + 1), supposons que (s₁,…,s_n) est canonique. Pour montrer que (s₁,…,s_n + 1) est canonique, il suffit de montrer que dans une décomposition $\sum_{j=1}^{n+1}d_js_i=v$ supposée optimale, le coefficient d_n + 1 est le quotient de v par s_n + 1. De façon équivalente, il suffit de montrer que si v ≥ s_n + 1 alors d_n + 1 ≥ 1, c’est-à-dire que pour décomposer une somme supérieure ou égale à s_n + 1 il y a toujours intérêt à utiliser une pièce de valeur s_n + 1.

Cas de s_n + 1 multiple de s_n

Considérons un cas où s_n + 1 = bs_n avec b ≥ 2. Soit une décomposition $\sum_{j=1}^{n+1}d_js_i=v$ pour une valeur v ≥ s_n + 1. Si on a d_n + 1 = 0, alors on a une décomposition $\sum_{j=1}^nd_js_i=v$ dans le système sans s_n + 1. Par hypothèse ce système est canonique donc l’algorithme glouton donne un résultat optimal, or celui-ci donne pour d_n le quotient euclidien de v par s_n, et comme v ≥ s_n + 1 = bs_n on a d_n ≥ b. Si à partir de la décomposition (d₁,…,d_n + 1) on décrémente d_n de b et on pose d_n + 1 = 1, on obtient une somme identique avec un nombre de pièces réduit de b − 1, la décomposition considérée au départ n’est donc pas optimale. Par conséquent, dans une décomposition $\sum_{j=1}^{n+1}d_js_i=v$ optimale, si v ≥ s_n + 1 alors d_n + 1 ≥ 1. C’est ce qu’on voulait démontrer.

Ce cas permet de conclure pour le système des puissances de 2 en question 8.

Il permet aussi de traiter l’étape de récurrence pour les sous-systèmes de l’euro qui terminent par 2, 10, 20, 100 et 200.

Schéma (1,2,5)

On cherche maintenant à traiter l’étape de récurrence pour les sous-systèmes de l’euro qui terminent par 5 ou 50. Considérons un cas où n ≥ 2 et où s_n = 2s_n − 1 et s_n + 1 = 5s_n − 1. Soit une décomposition $\sum_{j=1}^{n+1}d_js_i=v$ pour une valeur v ≥ s_n + 1. Si on a d_n + 1 = 0, alors on a une décomposition $\sum_{j=1}^nd_js_i=v$ dans le système sans s_n + 1. Par le même argument qu’au dessus, d_n est donc le quotient de v par s_n, en notant r le reste de cette division on a donc v = d_ns_n + r = 2d_ns_n − 1 + r ≥ 5s_n − 1 avec r < 2s_n − 1. On a donc d_n ≥ 2.

• Si d_n ≥ 3 (ce qui correspond au cas v ≥ 6s_n − 1) alors on obtient une meilleure décomposition dans (s₁,…,s_n + 1) en décrémentant d_n de 3 et en incrémentant d_n − 1 et d_n + 1 de 1 (c’est-à-dire en remplaçant 2 + 2 + 2 par 5 + 1). Par conséquent, pour v ≥ 6s_n − 1 un décomposition optimale doit avoir s_n + 1 ≥ 1.

• Sinon on a d_n = 2, ce qui correspond à 5s_n − 1 ≤ v < 6s_n − 1, puisqu’on a supposé v ≥ s_n + 1. Alors on a r = v − 2s_n = v − 4s_n − 1, donc s_n − 1 ≤ r < 2s_n − 1. Comme (s₁,…,s_n − 1) est canonique, d_n − 1 est le quotient de r par s_n − 1, donc d_n − 1 ≥ 1. On obtient une meilleure décomposition de v en décrémentant d_n de 2 et d_n − 1 de 1 et en incrémentant d_n + 1 de 1 (c’est-à-dire en replaçant 2 + 2 + 1 par 5). Par conséquent, pour 5s_n − 1 ≤ v < 6s_n − 1, un décomposition optimale doit aussi avoir s_n + 1 ≥ 1.

Tous les cas sont traité, ce qui permet de conclure dans les cas où n ≥ 2 et où s_n = 2s_n − 1 et s_n + 1 = 5s_n − 1.

Cela démontre en particulier que le système de l’euro est canonique.

Question 10

On ne connaît pas de caractérisation exacte des systèmes canoniques, mais les remarques précédentes permettent de donner des conditions suffisantes.

Par exemple, si chaque pièce est multiple de la pièce immédiatement inférieure, la démonstration donnée plus haut justifie que le système est canonique.