Algorithmes gloutons (1) – rendu de monnaie

« Le rendu de monnaie » :

On considère un système de pièces ou de billets :

# valeurs des pièces
valeurs = [1, 2, 5, 10, 20, 50, 100]

Pour aujourd’hui, il fallait écrire un programme en python qui :

  • demande le prix à payer (42 € par exemple),
  • demande ce que l’acheteur donne (un billet de 50 € par exemple, mince, c’est cher),
  • renvoie une liste de pièces ou billets rendus (par exemple ici pour 50 € donnés et 42 € à payer : un billet de 5€, une pièce de 2 € et une pièce de 1 €.

Correction proposée

La vidéo de la correction :

Le code du corrigé :

# le système de monnaie disponible
valeurs = [1, 2, 5, 10, 20, 50, 100]

def rendu_de_monnaie(somme_a_payer, somme_versee):
    liste = []
    a_rendre = somme_versee - somme_a_payer
    # par exemple 8 €

    # indice « tout à droite »
    indice = len(valeurs) - 1

    while a_rendre > 0: # on sort quand tout payé
        piece = valeurs[indice]
        # Soit la pièce est trop grande
        if piece > a_rendre:
            # on regardera une piece plus petite
            indice -= 1
        # soit on la rend (on rembourse)
        else:
            # on l'ajoute à la liste
            liste.append(piece)
            # on la soustrait de la somme à rendre
            a_rendre -= piece
    # on renvoie la liste
    return liste

# demandes à l'utilisateur 
somme_a_payer = int(input("Somme à payer ? : "))
# exemple 42 €
somme_versee = int(input("Somme versée ? : "))
# exemple 50 €

# Affichage des pièces et billets à rendre
liste_de_pieces = rendu_de_monnaie(somme_a_payer, somme_versee)
print(liste_de_pieces)
# exemple [5, 2, 1]

Certains d’entre vous se sont lancés, et même avec brio, dans la gestion des centimes, ce qui n’est pas sans poser le problème du test d’égalité entre flottants. Bravo ! Je ne le corrige pas ici pour ne pas compliquer outre mesure.

Pourquoi « algorithme glouton » ?

Optimiser un problème, c’est déterminer les conditions dans lesquelles ce problème présente une caractéristique spécifique. Par exemple, déterminer le minimum ou le maximum d’une fonction est un problème d’optimisation.

Les algorithmes gloutons constituent une alternative dont le résultat n’est pas toujours optimal. Plus précisément, ces algorithmes déterminent une solution optimale en effectuant successivement des choix locaux, jamais remis en cause. Au cours de la construction de la solution, l’algorithme résout une partie du problème puis se focalise ensuite sur le sous-problème restant à résoudre.

Le principal avantage des algorithmes gloutons est leur facilité de mise en œuvre.

Pour solutionner le problème du « rendu de monnaie », nous avons bien utilisé un algorithme glouton, la plus grande valeur de pièce étant systématiquement choisie si sa valeur est inférieure à la somme à rendre. Ce choix ne garantit en rien l’optimalité globale de la solution. Le choix fait est considéré comme pertinent et permet d’avancer plus avant dans le calcul.

(Ces lignes sont extraites de ce document d’accompagnement du programme, difficile d’accès.)

N'hésitez-pas à poser une question, ou faire avancer le schmilblick

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l’aide de votre compte WordPress.com. Déconnexion /  Changer )

Photo Google

Vous commentez à l’aide de votre compte Google. Déconnexion /  Changer )

Image Twitter

Vous commentez à l’aide de votre compte Twitter. Déconnexion /  Changer )

Photo Facebook

Vous commentez à l’aide de votre compte Facebook. Déconnexion /  Changer )

Connexion à %s

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur la façon dont les données de vos commentaires sont traitées.