Ceci est une ancienne révision du document !
L'algorithme Glouton
est une méthode d'optimisation qui consiste à prendre la meilleure solution à chaque étape du programme ou autre.
Voici un exemple de l'algorithme Glouton avec le problème du rendu de monnaie, ce code renvoie quelle(s) billet(s)/pièce(s) a été utilisé et combien de fois il l'a utilisé :
#initialisation des variables prix = float(input("Prix: ")) client = float(input("Argent donné: ")) somme_a_rendre = client-prix #Pour éviter une erreur de conversion en binaire somme_a_rendre = round(somme_a_rendre, 2) monnaie = {1 : [100, 0], 2 : [50, 0], 3 : [20, 0], 4 : [10, 0], 5 : [5, 0], 6 : [2, 0], 7 : [1, 0], 8 : [0.5, 0], 9 : [0.2, 0], 10 : [0.1, 0], 11 : [0.05, 0], 12 : [0.02, 0], 13 : [0.01, 0] } """ Ce programme peut rencontrer des problèmes de calculs avec les décimaux, car la fonction round arrondie au-dessus. """ def rendu_monnaie(monnaie, somme_a_rendre): x = 1 monnaie_used =[] if somme_a_rendre > 0: while somme_a_rendre > 0: #Pour éviter une erreur de conversion en binaire somme_a_rendre=round(somme_a_rendre, 2) if monnaie[x][0] > somme_a_rendre: x += 1 else: somme_a_rendre -= monnaie[x][0] monnaie[x][1] += 1 for i in range(1, 13): if monnaie[i][1] >= 1: monnaie_used.append(monnaie[i]) print("") return monnaie_used else: return "Le prix de l'objet est plus grand que l'argent donnée" print(rendu_monnaie(monnaie, somme_a_rendre))
Le programme crée deux variables avec des input, et demande à l'utilisateur le prix de l'objet et l'argent donnée. Puis le programme fait la différence et arrondie au centième :
prix = float(input("Prix: ")) client = float(input("Argent donné: ")) somme_a_rendre = client-prix #Pour éviter une erreur de conversion en binaire somme_a_rendre = round(somme_a_rendre, 2)
Ensuite, la variable monnaie est un dictionnaire avec les clefs et leurs variables associées, soit la pièce ou le billet et son nombre d'utilisation (pour plus d'information sur les dictionnaires : Listes, piles, files : structures linéaires. Dictionnaires, index et clé).
monnaie = {1 : [100, 0], 2 : [50, 0], 3 : [20, 0], 4 : [10, 0], 5 : [5, 0], 6 : [2, 0], 7 : [1, 0], 8 : [0.5, 0], 9 : [0.2, 0], 10 : [0.1, 0], 11 : [0.05, 0], 12 : [0.02, 0], 13 : [0.01, 0] }
Après avoir initialisée ces variables, le programme crée la fonction rendu_monnaie
et initialise des variables locales, x
étant la clef du dictionnaire et monnaie_used
les valeurs des pièces/ billets utilisés :
def rendu_monnaie(monnaie, somme_a_rendre): x = 1 monnaie_used =[]
Le programme vient ensuite vérifier si la variable somme_a_rendre
est supérieur à 0 pour éviter une erreur. Ensuite une boucle basique, même chose qu'à l'initialisation initiale, un round
pour arrondir au centième.
if somme_a_rendre > 0: while somme_a_rendre > 0: #Pour éviter une erreur de conversion en binaire somme_a_rendre=round(somme_a_rendre, 2)
Le programme vérifie le fait que la valeur de la pièce/billet correspondent à la clef soit supérieur à somme_a_rendre
pour éviter que somme_a_rendre
devienne négatif. Sinon le programme soustrait la pièce/billet correspondent à la clef à somme_a_rendre
puis ajoute à monnaie
l'utilisation de la pièce/billet encore une fois avec la clef correspondent.
if monnaie[x][0] > somme_a_rendre: x += 1 else: somme_a_rendre -= monnaie[x][0] monnaie[x][1] += 1