informatique (tronc commun des prépas scientifiques) · Chapitre 7 · Application directe du cours

Rendus de monnaie, à la main et à la machine

Algorithmes gloutons · niveau 1 (application)

Énoncé

Déterminer le rendu glouton de la somme $263$ centimes dans le système euro complet $[200, 100, 50, 20, 10, 5, 2, 1]$ . Ce résultat est-il optimal ?

Le glouton effectue les étapes suivantes :

$263 \geq 200 ⟹$ rendu de $200$ , reste $63$
$63 \geq 50 ⟹$ rendu de $50$ , reste $13$
$13 \geq 10 ⟹$ rendu de $10$ , reste $3$
$3 \geq 2 ⟹$ rendu de $2$ , reste $1$
$1 \geq 1 ⟹$ rendu de $1$ , reste $0$ . La liste renvoyée est [200, 50, 10, 2, 1], soit $5$ pièces. Le système euro étant canonique, ce résultat de 5 pièces est garanti optimal.