La caissière rend la monnaie
Tu achètes un livre à 63 euros. Tu donnes un billet de 100. La caissière doit te rendre 37 euros.
Elle ne réfléchit pas longtemps. Elle prend le plus gros billet qui entre : 20. Puis encore le plus gros qui entre dans ce qui reste : 10. Et ainsi de suite.
Cette façon de faire s'appelle un algorithme glouton.
Mots-clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Glouton | Un algorithme qui prend, à chaque pas, le meilleur choix du moment. | Le plus gros billet qui entre |
| Rendu de monnaie | Trouver quels billets et quelles pièces rendre. | 37 euros : 20, 10, 5 et 2 |
| Reste | Ce qui reste à rendre après chaque choix. | 37 - 20 = 17 |
| Capacité | Ce qu'un sac peut porter au maximum. | Un sac de 10 kilos |
| Choix | Ce que l'algorithme décide à un pas. | Prendre le billet de 20 |
| Solution | Le résultat que l'algorithme donne à la fin. | La liste des billets rendus |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
À toi : rends la monnaie
À toi de jouer
À toi : rends la monnaie
3 questionsTes réponses sont corrigées ici et ne sont pas conservées. Un compte garde tes résultats.
L'idée du glouton
On avance par étapes. À chaque étape, on prend ce qui paraît le mieux maintenant. On ne revient jamais en arrière.
Pour le rendu de monnaie, le meilleur choix est la plus grosse pièce qui n'est pas plus grande que le reste. On s'arrête quand le reste vaut 0.
Exemple travaillé : rendre 37 euros
| Étape | Reste avant | Choix | Reste après |
|---|---|---|---|
| 1 | 37 | 20 | 17 |
| 2 | 17 | 10 | 7 |
| 3 | 7 | 5 | 2 |
| 4 | 2 | 2 | 0 |
| Total | - | 4 billets et pièces : 20, 10, 5, 2 | - |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
À toi : rendre la monnaie en Python
def rendre_monnaie(montant, pieces):
reste = montant
rendu = []
for piece in pieces: # de la plus grosse à la plus petite
while reste >= piece:
rendu.append(piece)
reste = reste - piece
return rendu
euros = [20, 10, 5, 2, 1]
print("Rendre 37 euros :", rendre_monnaie(37, euros))
print("Rendre 63 euros :", rendre_monnaie(63, euros))
# Essaie 99, puis 8. Compte les pièces à la main pour vérifier.
À toi : l'état après l'étape 3
À toi de jouer
À toi : l'état après l'étape 3
3 questionsTes réponses sont corrigées ici et ne sont pas conservées. Un compte garde tes résultats.