Rendu de monnaie : glouton ou optimal

Saisissez un ensemble de pièces et un montant. La page rend la somme de deux façons : par la méthode gloutonne, qui prend chaque fois la plus grande pièce possible jusqu’à atteindre le montant ou se trouver bloquée, puis avec le plus petit nombre de pièces, déterminé en remplissant un tableau de 0 jusqu’au montant. Sous ce tableau figurent tous les montants jusqu’à la limite de votre choix ; ceux pour lesquels la méthode gloutonne emploie trop de pièces sont signalés.

Exemple résolu — Rendu de monnaie : glouton ou optimal

Méthode gloutonne, plus grande pièce d’abord	3 pièces
Minimum de pièces, d’après le tableau	2 pièces: 2×24
Pièces superflues avec la méthode gloutonne	1

Ce sont les valeurs affichées par le calculateur à l’ouverture de la page. Modifiez une entrée ci-dessus pour les recalculer.

Chargement de la simulation interactive...

Leçon

La théorie — Rendu de monnaie : glouton ou optimal

Le problème du rendu de monnaie consiste à obtenir un montant avec le plus petit nombre de pièces choisies dans un ensemble de valeurs, chaque pièce étant disponible en quantité illimitée. L’algorithme glouton prend chaque fois la plus grande pièce possible. La programmation dynamique donne une solution exacte en résolvant d’abord tous les montants inférieurs : M(0) = 0 et M(a) = 1 + min M(a − c) pour les pièces c ≤ a. Un système dans lequel l’algorithme glouton est optimal pour tout montant est dit canonique.

Ce que signifie chaque symbole

M(a): le plus petit nombre de pièces permettant d’obtenir le montant a ; c’est le nombre inscrit dans la case a du tableau
G(a): le nombre de pièces utilisées par l’algorithme glouton pour a
cₘ, cₘ₋₁: la plus grande et la deuxième plus grande pièce ; s’il existe un premier montant où l’algorithme glouton est sous-optimal, il est inférieur à leur somme

Suppose: Chaque pièce est disponible en quantité illimitée, les valeurs sont des nombres entiers et seul compte le nombre de pièces. Une caisse qui n’a plus de florins pose un autre problème. La borne exige une pièce de 1 ; sans elle, certains montants sont impossibles à rendre, et la méthode gloutonne peut rester en deçà d’un montant que le tableau parvient à former.

Dans l’ancien système britannique, quatre shillings suffisaient à piéger la méthode gloutonne 🖖

Appuyez sur R.-U. avant 1971. Pour rendre 48d, soit quatre shillings, la méthode gloutonne choisit d’abord la plus grande pièce possible : une demi-couronne (30d), puis un shilling (12d) et une pièce de six pence (6d), soit trois pièces. Deux florins de 24d donnent les mêmes 48d avec seulement deux pièces. Ensuite, la méthode est sous-optimale pour six montants sur chaque tranche de trente pence : 48–53d, 78–83d, et ainsi de suite jusqu’à 228–233d. Cela représente 42 des 240 montants d’une livre. À chaque fois, une seule pièce est superflue, d’où la hauteur identique de toutes les barres rouges. Ces six montants laissent un reste de 18 à 23 pence après une ou plusieurs demi-couronnes ; en reprenant une demi-couronne et en rendant 48d avec deux florins, on économise une pièce. Le demi-penny n’y change rien. Saisissez les pièces en demi-pence, 1, 2, 6, 12, 24, 48, 60, puis vérifiez jusqu’à 480 : le premier échec survient à 96 demi-pence, toujours 48d. La méthode est sous-optimale pour 84 des 480 montants, c’est-à-dire les mêmes 42 montants et le demi-penny qui suit chacun d’eux.

Sans la demi-couronne, la méthode gloutonne est toujours optimale 🖖

Appuyez sur Sans la demi-couronne. Il reste les pièces de 1, 3, 6, 12 et 24 pence, et le graphique se vide : la méthode gloutonne n’est sous-optimale pour aucun des 240 montants. Chaque pièce divise la suivante. Dans une telle chaîne, toute poignée de pièces dont la valeur atteint celle de la pièce supérieure peut être remplacée par cette unique pièce ; la méthode gloutonne ne peut donc pas perdre. La demi-couronne rompt cette chaîne. Trente n’est pas un multiple de vingt-quatre, et deux florins valent une demi-couronne plus 18d, reste qui exige un shilling et une pièce de six pence. Tous les échecs du premier graphique proviennent de cet échange. Ajouter une pièce ne résout pas davantage le problème. Saisissez 1, 3, 6, 12, 24, 30, 60 pour rétablir la couronne de cinq shillings : le nombre d’échecs passe de 42 à 24, mais 48d reste le premier, car une couronne ne sert à rien pour un montant inférieur à sa valeur.

La vérification d’un système de pièces est un problème fini 🖖

L’échec de la méthode gloutonne à 48d ne dit encore rien de ce qui se passe à 4 800d. Un théorème de Dexter Kozen et Shmuel Zaks, publié en 1994, permet pourtant de trancher pour tous les montants : si le système contient une pièce de 1 et si la méthode gloutonne est parfois sous-optimale, son premier échec se situe strictement entre c₃ + 1 et c_m + c_m−1. Ici, c₃ désigne la troisième plus petite pièce, tandis que c_m et c_m−1 sont les deux plus grandes. Appuyez sur Cents américains. Les deux plus grandes pièces valent 100 et 50 ; aucun montant inférieur à 150 ne met la méthode en défaut, et cette vérification finie couvre donc tous les montants possibles. Pour l’euro, elle va jusqu’à 300. La borne ne peut pas être resserrée. Appuyez sur 1, 3, 4 : entre 5 et 7, la fenêtre ne contient qu’un montant, 6, précisément celui où la méthode gloutonne échoue. La ligne en pointillés du graphique représente la borne. Dès qu’une pièce de 1 figure dans le système, la première barre rouge se trouve toujours à sa gauche.

Problème entièrement résolu

Quelle troisième pièce ajouter à 1 et 5 ? 3 étapes
Un pays possède des pièces de 1 et de 5 et souhaite en créer une troisième, d, comprise entre 6 et 30. Pour quelles valeurs de d la méthode gloutonne sera-t-elle toujours optimale ? La page ne teste qu’un système à la fois, mais la règle de Kozen et Zaks pour trois pièces permet de traiter les 25 possibilités d’un seul coup. Appuyez d’abord sur 1, 3, 4 pour appliquer la règle à un système déjà vérifié par la page.

Ouvrez ce problème dans l'outil
1. Pour des pièces 1 < c < d, la règle est la suivante : écrivez d = qc + r avec 0 ≤ r < c. Le système échoue quelque part si et seulement si 0 < r < c − q. Pour 1, 3, 4, on a d = 4 = 1 × 3 + 1, donc q = 1 et r = 1 ; l’inégalité 0 < 1 < 2 est vérifiée. Le système échoue, et la page situe son premier échec à 6 :
  
  $4 = 1 \times 3 + 1 : q = 1, r = 1, 0 < 1 < 3 - 1 = 2$
2. Prenons maintenant c = 5. On écrit donc d = 5q + r, et le critère devient 0 < r < 5 − q. Plus q augmente, moins il reste de valeurs possibles pour r :
  
  $d = 5 q + r, 0 \leq r < 5 : 0 < r < 5 - q$
3. Pour q = 1 (d de 6 à 9), r peut valoir 1, 2 ou 3 : d = 6, 7 et 8 échouent. Pour q = 2 (10 à 14), r vaut 1 ou 2 : ce sont 11 et 12. Pour q = 3 (15 à 19), seul r = 1 convient : on obtient 16. À partir de q = 4, 5 − q vaut 1 ou moins, et aucun r ne satisfait le critère :
  
  $q = 1 : d \in {6, 7, 8} q = 2 : d \in {11, 12} q = 3 : d = 16 q \geq 4 : 5 - q \leq 1$
Réponse

Six valeurs échouent : 6, 7, 8, 11, 12 et 16. Les dix-neuf autres conviennent, notamment toutes les valeurs de d comprises entre 17 et 30. Saisissez 1, 5, 12 pour observer l’un des six échecs : la méthode gloutonne rend 15 avec 12 + 1 + 1 + 1, soit quatre pièces, alors que trois pièces de cinq suffisent.

$d \in {6, 7, 8, 11, 12, 16} 15 = 12 + 1 + 1 + 1 = 5 + 5 + 5$

Parcours

Pourquoi un algorithme est correct

Références (3)

The bound the page draws as a dashed line and settles every system with: if greedy is ever beaten, the smallest amount where it is beaten lies strictly between c₃ + 1 and cₘ + cₘ₋₁; the three-coin rule the worked problem uses; the {1, 3, 4} example and the US system 1, 5, 10, 25, 50, 100 as canonical: D. Kozen and S. Zaks, "Optimal bounds for the change-making problem." Theoretical Computer Science 123(2), 1994, pp. 377-388. DOI 10.1016/0304-3975(94)90134-1
The pre-decimal coins and their values in pence (threepence, sixpence, shilling of 12d, florin of two shillings, half-crown of two shillings and sixpence, crown of five shillings), and the halfpenny's end as legal tender on 31 July 1969: Wikipedia contributors, "£sd", Wikipedia, The Free Encyclopedia, accessed 3 October 2026.
Which coins made up the circulating set at the end, as the Royal Mint itself issued them in 1970: half-crown, florin, shilling, sixpence, threepence, penny and halfpenny: The Royal Mint, "1970 Pre-Decimal UK Proof Set", product description, accessed 3 October 2026.

Par l’équipe 42Math · Vérifié sur des sources publiées. Corrections bienvenues.