Algorithme glouton : rendu de monnaie
Stratégie gloutonne et contre-exemples
Enonce
Implémenter l'algorithme glouton de rendu de monnaie. Retourner la liste des pièces utilisées. Tester sur le système euro et sur un contre-exemple.
Signature attendue
def rendu_monnaie(montant: int, pieces: list) -> list:Exemples
rendu_monnaie(37, [200, 100, 50, 20, 10, 5, 2, 1])→[20, 10, 5, 2]rendu_monnaie(6, [4, 3, 1])→[4, 1, 1]rendu_monnaie(99, [200, 100, 50, 20, 10, 5, 2, 1])→[50, 20, 20, 5, 2, 2]
📖 Rappel de cours
Un algorithme glouton fait à chaque étape le choix localement optimal, sans revenir en arrière.
Principe pour le rendu de monnaie :
Toujours prendre la plus grande pièce possible.
Optimalité :
Optimal pour le système euro/dollar : $\{1, 2, 5, 10, 20, 50, 100, 200\}$.
Contre-exemple : pièces $\{1, 3, 4\}$, montant 6. Glouton : $4+1+1=3$ pièces. Optimal : $3+3=2$ pièces.
← Exercices d'algorithmique en Python — tris, dichotomie, récursivité
Exercices du meme theme
- Pile et File
- Évaluation d'Expressions Postfixées
- Algorithme de Boyer-Moore simplifié
- Sac à dos (Programmation Dynamique)
- Plus Longue Sous-séquence Commune (LCS)
- Détection de Cycle (Floyd)
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.