DS 6 (MP2I 2021-2022) — Le problème du monnayeur¶

Devoir surveillé · MP2I · 2021-2022 · partie II du DS 6 (4 h au total)

Cours : Cas du rendu de monnaie · Programmation dynamique

D'après l'épreuve d'informatique du concours Centrale-Supélec 2002.

Notations¶

\(|E|\) désigne le cardinal de l'ensemble fini \(E\).
\(\lfloor x\rfloor\) désigne la partie entière inférieure du réel \(x\), et \(\lceil x\rceil\) sa partie entière supérieure : ce sont les relatifs définis respectivement par \(\lfloor x\rfloor \leqslant x<\lfloor x\rfloor+1\) et \(\lceil x\rceil-1<x \leqslant\lceil x\rceil\).
\(\llbracket p, q \rrbracket\) désigne l'intervalle discret délimité par les naturels \(p\) et \(q\) : \(\llbracket p, q \rrbracket=\{k \in \mathbb{N} \mid p \leqslant k \leqslant q\}\).

Présentation du problème¶

Nous nous intéressons au problème suivant, rencontré lors de la conception d'un monnayeur : comment rendre la monnaie, en utilisant le plus petit nombre possible de pièces ?

Formalisons ce problème : soit \(\left(c_{i}\right)_{1 \leqslant i \leqslant m}\) une liste d'entiers non nuls, vérifiant

\[ c_{1}>c_{2}>\ldots>c_{m-1}>c_{m}=1 \]

Nous utiliserons le terme système pour désigner une telle liste. Les \(c_{i}\) sont les valeurs faciales des pièces en service. Par exemple, si nous omettons les pièces de valeur inférieure à \(1\) euro, le système utilisé en France est \((200, 100, 50, 20,10,5,2,1)\).

Pour chaque \(i \in \llbracket 1, m \rrbracket\), nous disposons d'une quantité illimitée de pièces de valeur \(c_{i}\). Soit \(x\) un entier (le montant à rendre). Une représentation de \(x\) dans le système \(c\) est un \(m\)-uplet \(\left(k_{i}\right)_{1 \leqslant i \leqslant m}\) de naturels vérifiant

\[x=\sum_{1 \leqslant i \leqslant m} k_{i} c_{i}\]

\(k_{i}\) est donc le nombre de pièces de valeur \(c_{i}\) que l'on doit rendre.

Pour épargner les poches des clients, nous souhaitons minimiser le poids de cette représentation, c'est-à-dire le nombre \(\|k\|=\sum_{1 \leqslant i \leqslant m} k_{i}\) de pièces rendues.

Nous utiliserons en Caml des listes d'entiers pour représenter aussi bien un système (liste de valeurs de pièces), qu'une représentation d'un montant dans ce système. Par exemple, la liste \([4 ; 1 ; 3]\) est une représentation de 30 dans le système \((6,3,1)\).

Question 6

Rédigez une fonction de signature

est_un_systeme : int list -> bool

spécifiée comme suit : est_un_systeme c indique si la liste c est bien un système.

Par exemple, est_un_systeme [5 ; 2 ; 1] rendra la valeur true, tandis que est_un_systeme [5 ; 7 ; 1] rendra la valeur false, tout comme le fera est_un_systeme [7 ; 5 ; 2].

Représentations de poids minimal¶

Soient \(c=\left(c_{i}\right)_{1 \leqslant i \leqslant m}\) un système et \(x \geqslant 0\). Nous notons \(M_{c}(x)\) (ou même \(M(x)\) lorsqu'aucune ambiguïté n'est à craindre) le plus petit nombre de pièces nécessaires pour représenter \(x\) dans le système \(c\) :

\[ M(x)=\min \left\{\|k\| \mid k \in \mathbb{N}^{m} \text { et } \sum_{i=1}^m k_i c_i=x\right\} \]

Nous nous intéresserons aux représentations de poids minimal de \(x\) : ce sont les représentations \(k\) telles que \(\|k\|=M(x)\). Pour alléger la rédaction, nous parlerons simplement de représentations minimales.

Question 7

Prouvez l'encadrement \(\left\lceil x / c_{1}\right\rceil \leqslant M(x) \leqslant x\).

Question 8

Exhibez un système \(c\) et un nombre \(x>0\) possédant plusieurs représentations minimales dans le système \(c\).

Question 9

Soient \(c\) un système et \(x>0\). Montrez que \(M(x) \leqslant 1+M\left(x-c_{j}\right)\) pour tout indice \(j\) tel que \(c_{j} \leqslant x\).

Question 10

Soient \(c\) un système, \(x>0\) et \(j\) tel que \(c_{j} \leqslant x\). Montrez que \(M(x)=1+M\left(x-c_{j}\right)\) si et seulement s'il existe une représentation minimale de \(x\), faisant intervenir \(c_{j}\) (c'est-à-dire telle que \(k_{j}>0\)).

Question 11

Soit \(x>1\) ; notons \(s\) le plus petit indice \(i\) tel que \(c_{i} \leqslant x\). Nous avons donc \(c_{s} \leqslant x\) ; et, soit \(s=1\), soit \(s>1\) et \(c_{s-1}>x\). Justifiez l'égalité

\[ M(x)=1+\min _{s \leqslant i \leqslant m} M\left(x-c_{i}\right) \]

Question 12

Soit \(x > 0\). Montrez que l'on peut construire la liste des valeurs de \(M(y)\) pour \(y \leqslant x\), pour un coût \(\mathcal{O}(m x)\).

Question 13

Rédigez en Caml une fonction de signature

poids_minimaux : int -> int list -> int list

spécifiée comme suit : poids_minimaux x c construit la liste des valeurs de \(M_{c}(y)\), pour \(1 \leqslant y \leqslant x\). Par exemple, poids_minimaux 5 [5 ; 2 ; 1] rendra la liste [1 ; 1 ; 2 ; 2 ; 1]. Vous utiliserez la formule de la question 11.

Si besoin, vous avez le droit uniquement pour cette question de passer des listes aux tableaux avec

Array.of_list : 'a list -> 'a array
Array.to_list : 'a array -> 'a list

L'algorithme glouton¶

L'algorithme glouton consiste à choisir le plus grand \(c \leqslant x\), puis à rendre le montant \(x-c\). Par exemple, avec le système \((10,5,2,1)\) l'algorithme glouton décomposera le montant 27 en \(27=10+10+5+2\).

Avec le formalisme proposé, \(m=4, c_{1}=10, c_{2}=5, c_{3}=2, c_{4}=1\) ; la solution fournie par l'algorithme glouton est le quadruplet \(\left(k_{1}=2, k_{2}=1, k_{3}=1, k_{4}=0\right)\).

Le fonctionnement de l'algorithme glouton peut être accéléré avec la remarque suivante : notant \(q=\left\lfloor x / c_{1}\right\rfloor\), cet algorithme rend \(q\) pièces de valeur \(c_{1}\), puis rend le montant \(x-q c_{1}\) en utilisant le système \(\left(c_{i}\right)_{2 \leqslant i \leqslant m}\).

Question 14

Rédigez une fonction de signature

glouton : int -> int list -> int list

spécifiée comme suit : glouton x c construit la représentation de \(x\) dans le système \(c\), en appliquant l'algorithme glouton.

Par exemple, glouton 13 [5 ; 2 ; 1] rendra la liste [2 ; 1 ; 1].

Soient \(c=\left(c_{i}\right)_{1 \leqslant i \leqslant m}\) un système et \(x \geqslant 0\). Nous noterons \(\Gamma_{c}(x)\) la représentation gloutonne de \(x\) dans le système \(c\), et \(G_{c}(x)\) (ou même \(G(x)\) lorsqu'aucune ambiguïté n'est à craindre) le nombre de pièces utilisées par l'algorithme glouton : \(G_{c}(x)=\left\|\Gamma_{c}(x)\right\|\).

Nous dirons qu'un système \(c=\left(c_{i}\right)_{1 \leqslant i \leqslant m}\) est canonique si l'algorithme glouton donne toujours une représentation minimale ; on a donc \(M(x)=G(x)\) quel que soit \(x\).

Question 15

Montrez que tout système \(c=\left(c_{1}, c_{2}\right)\) de deux valeurs est canonique.

Question 16

Exhibez un système \(c=\left(c_{1}, c_{2}, c_{3}\right)\) non canonique.

Question 17

Soient \(q\) et \(n\) deux entiers \(\ge 2\). Montrer que le système \((q^n, q^{n-1}, \dots, q, 1)\) est canonique.

Question 18

Montrer que le système Euro \((200, 100, 50, 20, 10, 5, 2, 1)\) est canonique.

On pourra montrer que dans une représentation minimale de \(x\) : \(k = (k_1,\dots,k_8)\), on a \(k_8 \le 1, 2k_7 + k_8 \le 4, 5 k_6 + 2 k_7 + k_8 \le 9, \dots\).

Question 19

Avant la réforme de 1971 (introduisant un système décimal), le Royaume-Uni utilisait le système \((30,24,12,6,3,1)\). Montrez que ce système n'est pas canonique.

L'algorithme de Kozen et Zaks¶

Nous nous proposons de décrire un algorithme efficace permettant de déterminer si un système \(c\) est canonique. Nous dirons qu'un entier \(x\) est un contre-exemple pour \(c\) si \(M(x)<G(x)\). Un système canonique n'admet donc aucun contre-exemple.

Dans la suite, \(m \ge 3\).

Question 20

Soit \(c\) un système non canonique. Montrez qu'il existe un contre-exemple \(x\) vérifiant l'encadrement

\[c_{m-2}+1<x<c_{1}+c_{2}\]

Nous allons montrer que l'intervalle de recherche des contre-exemples ne peut pas être diminué.

Question 21

Soit \(q \geqslant 3\). Montrez que le système \((q+1, q, 1)\) n'est pas canonique. Quel est le plus petit contre-exemple pour ce système ?

Question 22

Soit \(q \geqslant 3\). Déterminez \(\alpha(q)>q\) tel que le système \((\alpha(q), q, 1)\) ne soit pas canonique, et admette \(\alpha(q)+2\) comme plus petit contre-exemple.

Le résultat de la question 20 nous donne un algorithme déterminant si un système est canonique : il suffit de les rechercher dans l'intervalle discret \(\llbracket c_{m-2}+2, c_{1}+c_{2}-1 \rrbracket\). Ceci nécessite la construction des représentations minimales de chacun des éléments de cet intervalle.

Nous allons étudier un algorithme plus efficace, dû à Kozen et Zaks ; leur méthode repose sur la notion de témoin. Nous dirons qu'un entier \(x\) est un témoin pour le système \(c=\left(c_{i}\right)_{1 \leqslant i \leqslant m}\) s'il existe un indice \(i\) tel que \(G\left(x-c_{i}\right)<G(x)-1\).

Question 23

Montrez que tout témoin est un contre-exemple.

Question 24

Montrez que le résultat de la question précédente n'admet pas de réciproque.

On pourra travailler dans le système \((5,4,1)\).

Question 25

Montrez que si le système \(c\) admet des contre-exemples, alors le plus petit d'entre eux est un témoin.

Il résulte de cette étude que, pour savoir si un système est canonique, il suffit de vérifier l'inégalité \(G(x) \leqslant G\left(x-c_{i}\right)+1\) pour tout \(x \in \llbracket c_{m-2}+2, c_{1}+c_{2}-1 \rrbracket\), et tout indice \(i \in \llbracket 1, m \rrbracket\) tel que \(c_{i}<x\). C'est le principe de l'algorithme de Kozen et Zaks.

Question 26

En utilisant l'algorithme de Kozen et Zaks, montrer que les systèmes \((q, 2, 1)\), \((q \ge 3)\) et \((7,4,1)\) sont canoniques, alors que \((6,5,1)\) ne l'est pas.

Question 27

Rédigez en Caml une fonction de signature

kozen_zaks : int list -> bool

spécifiée comme suit : kozen_zaks c indique si la liste \(c\) est canonique.

Par exemple, kozen_zaks [5 ; 2 ; 1] rendra la valeur true, tandis que kozen_zaks [6 ; 5 ; 1] rendra la valeur false. Vous utiliserez l'algorithme de Kozen et Zaks.

Question 28

Montrez que le coût de l'algorithme de Kozen et Zaks peut être exponentiel, par rapport au nombre \(m\) de pièces du système.

On exhibera deux systèmes (l'un canonique, l'autre pas) pour lesquels le coût de l'algorithme est exponentiel en \(m\).