Rendu de Monnaie Glouton
Algorithmique classique
Enonce
Rendre la monnaie pour un montant donné en utilisant le minimum de pièces. La liste pieces est triée par ordre décroissant. Approche gloutonne.
Signature attendue
def rendu_monnaie(montant: int, pieces: list) -> list:Exemples
rendu_monnaie(67, [50, 20, 10, 5, 2, 1])→[50, 10, 5, 2]rendu_monnaie(100, [50, 20, 10, 5, 2, 1])→[50, 50]
📖 Rappel de cours
On prend systématiquement la plus grande pièce qui tient dans le montant restant, et on recommence.
⚠ Le piège : Le glouton n'est optimal que sur certains systèmes de pièces. Avec [1, 3, 4] et un montant de 6, il rend 4+1+1 alors que 3+3 fait mieux — c'est la question classique.
← Exercices Python pour la prépa — CPGE scientifique et ECG
Exercices du meme theme
- Parcours en Largeur (BFS)
- Degré des Sommets
- Composantes Connexes
- Sélection d'Activités
- Sac à Dos Fractionnaire
- Couverture d'Intervalles
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.