Rendre la monnaie avec le moins de pièces possible : faut-il toujours prendre la plus grosse pièce ?

Pourquoi cette question : un modèle d'introduction

Le jury attend que vous expliquiez pourquoi vous avez choisi la question. Inspirez-vous de ce modèle, mais racontez votre propre parcours.

En aidant à la caisse d'une fête de lycée, je rendais spontanément la monnaie en commençant par les plus gros billets. En NSI, j'ai appris que c'est un « algorithme glouton ». Le professeur nous a demandé s'il donnait toujours le minimum de pièces, et j'ai été surpris d'apprendre que non. J'ai voulu comprendre quand on peut lui faire confiance.

L'enjeu et les notions du programme

Distinguer une méthode qui semble naturelle d'une méthode prouvée optimale, à l'aide d'un contre-exemple et d'une relation de récurrence.

Le plan de l'exposé en 9,5 min

1. 1. Introduction

   1 min

   Un algorithme glouton fait à chaque étape le choix qui paraît le meilleur sur le moment, sans revenir en arrière. Problématique : pour le rendu de monnaie, ce choix local conduit-il toujours au meilleur résultat global ?

2. 2. Mathématiques : un contre-exemple et une récurrence

   4 min

   Glouton avec les euros (pièces et billets de 1, 2, 5, 10, 20, 50…) : pour 38 €, on prend 20, 10, 5, 2, 1, soit 5 pièces, et c'est le minimum. On démontre que ce système est « canonique » : le glouton y est toujours optimal.

   Mais imaginons des pièces de 1, 3 et 4. Pour rendre 6, le glouton prend 4, puis 1, puis 1 : 3 pièces. Or $3+3=6$3+3=6 n'en utilise que 2. Un seul contre-exemple suffit à prouver que le glouton n'est pas toujours optimal.

   Méthode exacte : notons $m(s)$m(s) le nombre minimal de pièces pour rendre $s$s. On a $m(0)=0$m(0)=0 et $m(s)=1+\min (m(s-1),m(s-3),m(s-4))$m(s)=1+min(m(s-1),m(s-3),m(s-4)) (en ignorant les termes négatifs). On calcule de proche en proche : $m(1)=1$m(1)=1, $m(2)=2$m(2)=2, $m(3)=1$m(3)=1, $m(4)=1$m(4)=1, $m(5)=2$m(5)=2, $m(6)=1+\min (m(5),m(3),m(2))=2$m(6)=1+min(m(5),m(3),m(2))=2.

3. 3. NSI : glouton contre programmation dynamique

   3 min

   Le glouton est très rapide : quelques divisions euclidiennes. La programmation dynamique remplit un tableau des valeurs $m(0),m(1),\dots ,m(s)$m(0),m(1),…,m(s) : pour $k$k types de pièces, environ $k\times s$k× s opérations. Elle mémorise les sous-résultats pour ne jamais les recalculer.

   Une version récursive naïve, sans mémoire, recalculerait sans cesse les mêmes valeurs, avec un coût exponentiel. La mémoïsation (un dictionnaire des résultats déjà connus) suffit à la rendre efficace. Les vrais systèmes monétaires sont conçus canoniques justement pour que les caissiers puissent rendre la monnaie de façon gloutonne.

4. 4. Conclusion

   1,5 min

   Prendre la plus grosse pièce marche avec les euros, mais pas avec tous les systèmes : le contre-exemple 1, 3, 4 le prouve. La programmation dynamique, fondée sur une relation de récurrence, garantit l'optimum. J'ouvre sur le problème du sac à dos, où le glouton échoue aussi.

Ce que j'écris au tableau

Pas de calculatrice ni de support numérique : un calcul clé écrit au tableau rend l'exposé concret et montre la solidité des connaissances.

Conclusion : la réponse à la question

Les questions probables du jury

Pendant les 10 minutesd'échange, le jury vous fait préciser et approfondir, sur tout le programme de vos spécialités en lien avec la question.

Les pièges qui coûtent des points

• Croire qu'une méthode naturelle est forcément optimale.
• Donner un exemple au lieu d'un contre-exemple pour réfuter.
• Oublier le cas de base m(0) = 0.

Revoir les notions

• Suites : récurrence et limites (Terminale spé maths) →
• Algorithmique et Python (Première spé maths) →

Autres questions : algorithmes et complexité

• Pourquoi trier un million de nombres peut-il prendre dix minutes ou un centième de seconde selon l'algorithme ?
• Pourquoi couper un problème en deux permet-il de le résoudre beaucoup plus vite ?
• Peut-on inventer un algorithme de tri encore plus rapide, ou existe-t-il une limite infranchissable ?
• Un ordinateur mille fois plus rapide permet-il de résoudre des problèmes mille fois plus grands ?

Toutes les questions maths-nsi →