logo

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 :

pieces=(200, 100, 50, 20, 10, 5, 2, 1)

  1. Expliquer le choix d'un tuple pour pieces et pourqoi on utilise des cents et non des euros.
  2. 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.
  3. Ecrire la fonction rendreMonnaie de paramètres : le montant en cents et pieces, qui renvoie le dictionnaire précédent mis à jour.
  4. Ecrire une (des) pré-condition(s) pour cette fonction sur le paramètre montant.
  5. Tester la fonction avec différents montants.

Voir une solution

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)]
  1. 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
  2. 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.
  3. Ecrire une (des) pré-condition(s) pour cette fonction sur le paramètre montant.
  4. Tester la fonction avec différents capacités du sac.

Voir une solution