Aller au contenu

01d Fiche méthode - Algorithme glouton

💰 Le principe

⚓︎

On souhaite écrire une fonction renduMonnaie(somme, pieces) qui détermine automatiquement quelles pièces utiliser pour rendre une somme donnée.

🎯 Exemple :
Comment rendre 780 centimes (soit 7,80 €) avec les pièces disponibles ?

Illustration

L'idée de l'algorithme glouton est simple :
👉 On prend à chaque étape la plus grosse pièce possible, autant de fois que possible.

⚙️ L’algorithme glouton

⚓︎

🔁 Version avec boucle et soustraction répétée

⚓︎
🐍 Script Python
def renduMonnaie(somme, pieces):
    # Initialiser le dictionnaire des pièces utilisées
    choisies = {p: 0 for p in pieces}
    for p in pieces:
        while somme >= p:
            somme -= p
            choisies[p] += 1
    return choisies

📌 Test dans la console :

🐍 Script Python
# Pièces disponibles (en centimes)
pieces = [500, 200, 100, 50, 20, 10, 5, 2, 1]
somme = 780

print("Les pièces choisies sont :", renduMonnaie(somme, pieces))
❓Tester ce qui est proposé

###

🔄 Version optimisée : une seule boucle

⚓︎

⏱️ Optimisation avec divisions entières

⚓︎
🐍 Script Python
def renduMonnaie(somme, pieces):
    # Initialiser le dictionnaire des pièces utilisées
    choisies = {p: 0 for p in pieces}
    for p in pieces:
        nb = somme // p      # combien de pièces de cette valeur ?
        choisies[p] = nb
        somme -= nb * p      # mettre à jour la somme restante
    return choisies

✅ Cette version est plus rapide : on évite les boucles while imbriquées.

💡 Remarque importante : système canonique

⚓︎

Un système de pièces est dit canonique si l’algorithme glouton donne toujours la solution optimale, c’est-à-dire avec le plus petit nombre de pièces possible.

🪙 Le système monétaire en euros est canonique. Mais ce n’est pas toujours le cas ! Certains ensembles de pièces non classiques peuvent piéger l’algorithme glouton.

Pour s'entrainer par ordre de dificulté croissante :