Rendre la monnaie : un algorithme glouton
À la caisse, on te rend 3,80 €. Quelles pièces choisir pour en donner le moins possible ? Tu connais déjà la méthode sans le savoir : c'est un algorithme glouton.
La stratégie
Naturellement, on commence par la plus grosse pièce possible, puis on continue avec ce qui reste :
- 3,80 € : une pièce de 2 €, il reste 1,80 € ;
- 1,80 € : une pièce de 1 €, il reste 0,80 € ;
- 0,80 € : une pièce de 50 centimes, il reste 0,30 € ;
- 0,30 € : une pièce de 20 centimes, il reste 0,10 € ;
- 0,10 € : une pièce de 10 centimes. Terminé !
À chaque étape, on fait le choix qui semble le meilleur sur le moment, sans revenir en arrière. C'est le principe de tous les algorithmes gloutons.
Travailler en centimes
Pour éviter les calculs avec des virgules, on compte tout en centimes : 3,80 € devient 380.
Combien de pièces de 200 dans 380 ? C'est le quotient entier de la division : arrondi_inferieur(380 / 200) vaut 1. Et ce qui reste à rendre, c'est le reste de la division : 380 mod 200 vaut 180.
restant est un nombre vaut 380
combien est un nombre
combien vaut arrondi_inferieur(restant / 200)
restant vaut restant mod 200
affiche combien + ' pièce de 2 €, il reste ' + restant + ' centimes'
Question : Combien de pièces de 50 centimes peut-on mettre dans 180 centimes, et que reste-t-il ? — 3 pièces, il reste 30. 180 = 3 × 50 + 30 : le quotient entier est 3, le reste est 30.
L'algorithme complet
On range les pièces dans un tableau, de la plus grosse à la plus petite, et on les essaie dans l'ordre :
pieces est un tableau vaut [200, 100, 50, 20, 10, 5, 2, 1]
restant est un nombre
demande 'Somme à rendre, en centimes ? ' dans restant
combien est un nombre
nombrePieces est un nombre vaut 0
pour i de 0 à longueur(pieces) - 1
combien vaut arrondi_inferieur(restant / pieces[i])
si combien > 0 alors
affiche combien + ' x ' + pieces[i] + ' centimes'
nombrePieces ajoute combien
restant vaut restant mod pieces[i]
fin si
fin pour
affiche 'Total : ' + nombrePieces + ' pièces'
Pour 380, le programme rend 5 pièces : 200, 100, 50, 20 et 10. C'est bien le minimum possible.
Le glouton a-t-il toujours raison ?
Avec nos pièces en euros, oui : la stratégie gloutonne donne toujours le plus petit nombre de pièces. Mais ce n'est pas vrai pour n'importe quelles pièces !
Imagine un pays où les pièces valent 4, 3 et 1. Pour rendre 6 :
- le glouton prend d'abord 4, puis 1, puis 1 : trois pièces ;
- alors que 3 + 3 fait l'affaire avec deux pièces seulement.
Vérifions avec le même programme, en changeant juste le tableau :
pieces est un tableau vaut [4, 3, 1]
restant est un nombre vaut 6
combien est un nombre
nombrePieces est un nombre vaut 0
pour i de 0 à longueur(pieces) - 1
combien vaut arrondi_inferieur(restant / pieces[i])
si combien > 0 alors
affiche combien + ' x ' + pieces[i]
nombrePieces ajoute combien
restant vaut restant mod pieces[i]
fin si
fin pour
affiche 'Le glouton utilise ' + nombrePieces + ' pièces, alors que 2 suffisent.'
En prenant la pièce de 4, le glouton s'est fermé la meilleure solution. Un choix excellent sur le moment peut être mauvais pour la suite.
Quand utiliser un algorithme glouton ?
- Il est simple et très rapide : une seule boucle, aucun retour en arrière.
- Il donne souvent une bonne solution, mais pas toujours la meilleure.
- Avant de lui faire confiance, il faut vérifier qu'il convient au problème... ou accepter une solution « assez bonne ».
On retrouve les algorithmes gloutons partout : calcul d'itinéraires, planification, compression de fichiers.
En résumé
- Glouton : à chaque étape, faire le meilleur choix immédiat, sans revenir en arrière.
arrondi_inferieur(a / b) donne le quotient entier, a mod b le reste.- Compter en centimes évite les problèmes de virgule.
- Le glouton est optimal pour les euros, pas pour toutes les monnaies : un algorithme doit être vérifié.
