Les algorithmes gloutons
Exercice 1 : le rendu de monnaie
L'objectif de cet exercice est d'écrire un programme constitué de plusieurs fonctions permettant de rendre la monnaie à partir d'une liste de pièces.
On dispose de pièces de :
- 2€
- 1€
- 50 cents
- 20 cents
- 10 cents
- 5 cents
- 2 cents
- 1 cent
pieces=(200, 100, 50, 20, 10, 5, 2, 1)
- Expliquer le choix d'un tuple pour
pieces
et pourqoi on utilise des cents et non des euros.
- Ecrire une fonction
dico_monnaie
qui a pour paramètre pieces
et qui renvoie un dictionnaire avec comme clé le montant des pièces et comme valeur, leur nombre.
- Ecrire la fonction
rendreMonnaie
de paramètres : le montant en cents et pieces
, qui renvoie le dictionnaire précédent mis à jour.
- Ecrire une (des) pré-condition(s) pour cette fonction sur le paramètre
montant
.
- Tester la fonction avec différents montants.
Voir une solution
Voir le code :
pieces=(200, 100, 50, 20, 10, 5, 2, 1)
def dico_monnaie(pieces):
dicomonnaie={}
for piece in pieces:
dicomonnaie[piece]=0
return dicomonnaie
def rendreMonnaie(montant,pieces):
assert(type(montant)==int),("il faut saisir un entier")
assert(montant > 0),("il faut saisir un entier positif")
dicomonnaie=dico_monnaie(pieces)
for piece in dicomonnaie.keys():
while piece <= montant:
montant=montant-piece
dicomonnaie[piece]=dicomonnaie[piece]+1
return dicomonnaie
Masquer
Exercice 2 : le sac à dos
Un cambrioleur possède un sac à dos d'une contenance maximum de 50 Kg. Au cours d'un de ses cambriolages, il a la possibilité
de dérober des objets A, B, C et D. Il y a suffisamment d'objets de chaque sorte pour remplir le sac. Voici un tableau qui résume les caractéristiques de ces objets :
caractéristiques des objets
objet |
A |
B |
C |
D |
masse |
17 Kg |
12 Kg |
8 Kg |
10 Kg |
valeur marchande |
650 € |
450 € |
280 € |
360 € |
Objectif de cet exercice sera de remplir le sac avec une valeur marchande maximale en utilisant un algorithme glouton;
objets = [("A", 17, 650), ("B", 12, 450), ("C", 8, 280), ("D", 10, 360)]
- Ecrire une fonction
dico_objet
qui a pour paramètre objets
et qui renvoie un dictionnaire avec comme clé le nom de l'objet et comme valeur, le tuple (le rapport de la valeur marchande par la masse , la masse). Ce dictionnaire devra être trié par dans l'ordre décroissant des rapports valleur/masse
- Ecrire la fonction
remplirSac
de paramètres : la masse pouvant être contenue par le sac et objets
, qui renvoie un dictionnaire ayant comme clé le nom de l'objet, et pour valeur le nombre d'objets dans le sac.
- Ecrire une (des) pré-condition(s) pour cette fonction sur le paramètre
montant
.
- Tester la fonction avec différents capacités du sac.
Voir une solution
Voir le code :
objets = [("A", 17, 650), ("B", 12, 450), ("C", 8, 280), ("D", 10, 360)]
def dico_objet(objets):
liste_objets=[]
for objet in objets:
liste=[objet[0], objet[1],objet[2]/objet[1]]
liste_objets.append(liste)
liste_objets=sorted(liste_objets, key=lambda x: x[2], reverse=True)
dico={}
for objet in liste_objets:
dico[objet[0]]=(objet[2],objet[1])
return dico
def remplirSac(sac,objets):
assert(type(sac)==float or type(sac)==int),("il faut saisir un nombre")
assert(sac > 0),("il faut saisir un entier positif")
dico=dico_objet(objets)
dico_sac={}
for objet in dico.keys():
dico_sac[objet]=0
while dico[objet][1] <= sac:
sac=sac-dico[objet][1]
dico_sac[objet]=dico_sac[objet]+1
return dico_sac
Masquer