Un algorithme glouton (parfois appelé aussi algorithmes gourmand, ou goulu) est un algorithme qui suit le principe de faire, étape par étape, un choix optimum local, dans l’espoir d’obtenir un résultat optimum global.
exercice consigne:
Le problème du rendu de monnaie est un problème d’algorithmique qui s’énonce de la façon suivante : étant donné un système de monnaie, comment rendre une somme donnée de façon optimale, c’est-à-dire avec le nombre minimal de pièces et billets ?
Dans la zone euro, le système en vigueur, en mettant de côté les centimes d’euros, met à disposition des pièces ou billets de : 1€, 2€, 5€, 10€, 20€, 50€, 100€, 200€, 500€.
On suppose que nous avons à notre disposition un nombre illimité de ces pièces ou billets.
Tentative:
system_euro = [500,200,100,50,20,10,5,2,1]
system = system_euro
def rendu(somme , system):
liste_piece=[]
for val in system:
if somme >= system[0]:
liste_piece = system [0]
else liste_piece
return liste_piece
rendu(600,system)
Correction:
system_euro=[500,200,100,50,20,10,5,2,1]
def rendu_monnaie(somme,systeme):
liste_pieces=[]
for valeur in systeme:
while somme>=valeur:
liste_pieces.append(valeur)
somme=somme-valeur
return liste_pieces
rendu_monnaie(888,system)
Lien collab pour voir les essaies:
https://colab.research.google.com/drive/1X0dvaCywrAgfUuBO00yNntzQkRd5encs?usp=sharing
Aucune réponse