#!/usr/bin/env python
# coding: utf-8
#
#
TP n°10 (algorithmes gloutons) : Éléments de correction
# ## II. Problème du rendu de monnaie
# In[1]:
VALEURS = [200, 100, 50, 20, 10, 5, 2, 1] # variable globale
#
# Exercice 1
#
# Il s'agit d'adapter l'algorithme de calcul d'une somme que vous avez déjà codé :
# In[2]:
def pieces2cents(pieces: [int])->int:
"""
Entrée : liste de nombres (de type int) de pièces
Sortie : valeur totale de cette liste en cents (de type int)
"""
s = 0 # initialisation de la somme totale
for i in range(len(pieces)):
s += pieces[i] * VALEURS[i]
return s
# In[3]:
pieces2cents([0, 0, 5, 0, 2, 1, 0, 2])
#
# Exercice 2
#
# On cherche à chaque étape la pièce de plus grande valeur à rendre.
# In[4]:
def rendu_glouton(montant):
"""
Entrée : un montant exprimé en cents (de type int)
Sortie : la liste des pièces à rendre au format défini dans l'énoncé
"""
p = len(VALEURS)
pieces = [0 for i in range(p)]
while montant > 0:
i = 0
while VALEURS[i] > montant:
i += 1
pieces[i] += 1
montant -= VALEURS[i]
return pieces
# In[5]:
rendu_glouton(277)
# On rend donc, sur un montant de 2€77 :
#
# - une pièce de 2€
# - une pièce de 50 cents
# - une pièce de 20 cents
# - une pièce de 5 cents
# - une pièce de 2 cents.
# In[6]:
rendu_glouton(542)
# On rend donc, sur un montant de 5€42 :
#
# - deux pièces de 2€
# - une pièce de 1€
# - deux pièces de 20 cents
# - une pièce de 2 cents.
# **Remarque :**
# > On peut en rendre plusieurs pièces de même valeur en une seule étape ; leur nombre provient d'une division euclidienne :
# In[7]:
def rendu_glouton(montant):
"""
Entrée : un montant exprimé en cents (de type int)
Sortie : la liste des pièces à rendre au format défini dans l'énoncé
"""
p = len(VALEURS)
pieces = [0 for i in range(p)]
for i in range(p):
pieces[i] = montant // VALEURS[i] # nombre de pièces à rendre
montant = montant % VALEURS[i] # mise à jour du montant restant à rendre
return pieces
# In[8]:
rendu_glouton(277)
# In[9]:
rendu_glouton(542)
# On peut également gérer la liste à rendre au fur et à mesure de la façon suivante :
# In[10]:
def rendu_glouton(montant):
"""
Entrée : un montant exprimé en cents (de type int)
Sortie : la liste des pièces à rendre au format défini dans l'énoncé
"""
p = len(VALEURS)
pieces = []
for i in range(p):
nb = montant // VALEURS[i] # nombre de pièces à rendre
pieces.append(nb)
montant = montant % VALEURS[i] # mise à jour du montant restant à rendre
return pieces
# In[11]:
rendu_glouton(277)
#
# Exercice 3
#
# Pour rendre $6$ peanuts, l'algorithme glouton fournira une pièce de $4$ peanuts et deux pièces de $1$ peanut, soit $3$ pièces en tout.
#
# Ce n'est pas optimal, puisque l'on peut ne rendre que deux pièces de $3$ peanuts. Ce système n'est donc pas canonique.
# In[12]:
VALEURS = [4, 3, 1]
# In[13]:
rendu_glouton(6)
# In[14]:
pieces2cents([0, 2, 0])
# In[15]:
VALEURS = [200, 100, 50, 20, 10, 5, 2, 1] # on remet la vraie liste pour la suite du TP
#
# Exercice 4
#
# On définit le fond de caisse disponible comme une variable globale :
# In[16]:
CAISSE = [10, 10, 50, 100, 100, 100, 100, 100] # variable globale
# In[17]:
def rendu_glouton_caisse(montant):
"""
Entrée : un montant exprimé en cents (de type int)
Sortie : la liste des pièces à rendre au format défini dans l'énoncé
"""
m = montant
p = len(VALEURS)
pieces = [0 for i in range(p)]
while m > 0:
i = 0
while VALEURS[i] > m or CAISSE[i] == 0:
i += 1
pieces[i] += 1
m -= VALEURS[i]
CAISSE[i] -= 1
return pieces
# In[18]:
rendu_glouton_caisse(278)
# Si on change la caisse :
# In[19]:
CAISSE = [10, 10, 0, 100, 100, 100, 100, 100] # il n'y a plus de pièce de 50 cents
# In[20]:
rendu_glouton_caisse(278)
# In[21]:
pieces2cents(_)
# Si on change la caisse :
# In[22]:
CAISSE = [5, 0, 0, 0, 10, 10, 10, 10]
# On ne peut plus rendre 1€90 :
# In[23]:
rendu_glouton_caisse(190)
# On peut écrire une fonction qui travaille avec les quotients / restes comme avant, et qui évite de renvoyer un message d'erreur :
# In[24]:
def rendu_glouton_caisse(montant):
"""
Entrée : un montant en cents (de type int)
Sortie : le rendu de monnaie (si possible) sous forme de liste au format défini dans l'énoncé
(si impossible, on renvoie None)
"""
p = len(VALEURS)
pieces = [0 for i in range(p)]
for i in range(p):
theorie = montant // VALEURS[i]
if theorie > CAISSE[i]:
pieces[i] = CAISSE[i]
montant = montant - CAISSE[i] * VALEURS[i]
else:
pieces[i] = theorie
montant = montant % VALEURS[i]
if montant == 0:
return pieces
else:
return None # on ne retourne rien
# In[25]:
rendu_glouton_caisse(190)
#
# Exercice 5
#
# La variable globale ```CAISSE``` n'est jamais changée par un appel à la fonction ```rendu_glouton_caisse```.
# In[26]:
CAISSE = [10, 10, 10, 100, 100, 100, 100, 100]
# In[27]:
rendu_glouton_caisse(277)
# In[28]:
CAISSE
# Pour remédier à ce problème, une solution consisterait à rajouter une ligne pour gérer l'évolution de la caisse.
#
# Attention à créer une copie de ```CAISSE```, puisque la caisse demeure inchangée si l'on ne peut pas rendre la monnaie :
# In[29]:
def rendu_glouton_caisse(montant):
"""
Entrée : un montant en cents (de type int)
Sortie : le rendu de monnaie (si possible) sous forme de liste au format défini dans l'énoncé
(si impossible, on renvoie None)
"""
global CAISSE # obligatoire car la variable globale CAISSE est affectée durant la fonction
COPIE = CAISSE.copy() # copie de la caisse
p = len(VALEURS)
pieces = [0 for i in range(p)]
for i in range(p):
theorie = montant // VALEURS[i]
if theorie > CAISSE[i]:
pieces[i] = CAISSE[i]
montant = montant - CAISSE[i] * VALEURS[i]
else:
pieces[i] = theorie
montant = montant % VALEURS[i]
COPIE[i] -= pieces[i] # évolution de la caisse
if montant == 0:
CAISSE = COPIE # mise à jour de la caisse
return pieces
else:
return None # on ne retourne rien (et CAISSE est inchangée)
# In[30]:
CAISSE = [10, 10, 50, 100, 100, 100, 100, 0] # il n'y a plus de pièce de 1 cent
rendu_glouton_caisse(277)
# In[31]:
CAISSE
# In[32]:
rendu_glouton_caisse(278)
# In[33]:
CAISSE
# ## III. Problème de sélection d'activité
#
# Exercice 6
#
# On trie les sites par ordre croissant d'heures de fin (la relation d'ordre est notée $\preccurlyeq$, mais cela importe peu) :
#
# $$
# S_8 \preccurlyeq S_4 \preccurlyeq S_6 \preccurlyeq S_{13} \preccurlyeq S_{10} \preccurlyeq S_{15} \preccurlyeq S_2 \preccurlyeq S_{11} \preccurlyeq S_5 \preccurlyeq S_9 \preccurlyeq S_1 \preccurlyeq S_7 \preccurlyeq S_{14} \preccurlyeq S_3 \preccurlyeq S_{12}
# $$
#
# **Remarque :**
# > Il y a plusieurs façons de faire : $S_4$, $S_6$ et $S_{13}$ ont la même heure de fin.
# On peut maintenant construire progressivement le planning $\mathscr P$ :
#
# - Le premier site est $S_8$ $\phantom{compalibll avec aplllla}$$\quad\leadsto \mathscr P=[S_8]$.
# - Le 1er site suivant compatible avec $S_8$ est $S_4$ $\quad\leadsto\mathscr P=[S_8, S_4]$.
# - Le 1er site suivant compatible avec $S_4$ est $S_2$ $\quad\leadsto\mathscr P=[S_8, S_4, S_2]$.
# - Le 1er site suivant compatible avec $S_2$ est $S_5$ $\quad\leadsto\mathscr P=[S_8, S_4, S_2, S_5]$.
# - Le 1er site suivant compatible avec $S_5$ est $S_3$ $\quad\leadsto\mathscr P=[S_8, S_4, S_2, S_5, S_3]$.
#
# Ce qui mène au planning final suivant :
# $$
# \fbox{$\mathscr P_{\text{final}}=[S_8, S_4, S_2, S_5, S_3]$}
# $$
#
# Exercice 7
#
# In[34]:
def planning(S):
"""
Entrée : une liste de sites au format défini dans l'énoncé
Sortie : un planning optimal au format défini dans l'énoncé
"""
S.sort(key=lambda x: x[2]) # tri des sites selon l'heure de fin croissante
plan = [S[0]] # initialisation du planning
for i in range(1, len(S)):
if S[i][1] >= plan[-1][2]:
# si l'heure de début de Si >= l'heure de fin du dernier ajouté dans le planning
plan.append(S[i]) # on place Si dans le planning
return plan
# On peut également gérer la boucle ```for``` sans avoir recours à l'indice ```i``` :
# In[35]:
def planning(S):
"""
Entrée : une liste de sites au format défini dans l'énoncé
Sortie : un planning optimal au format défini dans l'énoncé
"""
S.sort(key=lambda x: x[2]) # tri des sites selon l'heure de fin croissante
plan = [S[0]] # initialisation du planning
for s in S[1:]:
if s[1] >= plan[-1][2]:
# si l'heure de début de s >= l'heure de fin du dernier ajouté dans le planning
plan.append(s) # on place Si dans le planning
return plan
# In[36]:
S = [["S1", 0, 7], ["S2", 2, 5], ["S3", 6, 8], ["S4", 1, 2], ["S5", 5, 6],
["S6", 0, 2], ["S7", 4, 7], ["S8", 0, 1], ["S9", 3, 6], ["S10", 1, 3],
["S11", 4, 5], ["S12", 6, 8], ["S13", 0, 2], ["S14", 5, 7], ["S15", 1, 4]]
# In[37]:
planning(S)
# ## IV. Allocation de ressources
#
# Exercice 8
#
# In[43]:
def conflit(S, modules):
"""
Entrée : un site S et une liste de modules
Sortie : True s'il existe un conflit entre S et un des modules, False sinon.
"""
for M in modules:
if not (S[2] <= M[1] or M[2] <= S[1]): # il y a un conflit entre S et M
return True
return False # seulement si on est sorti de la boucle for
# In[44]:
conflit(["S1", 1, 3], [["S2", 2, 5], ["S3", 4, 6]])
# In[45]:
conflit(["S1", 1, 3], [["S2", 4, 6], ["S3", 5, 7]])
#
# Exercice 9
#
# In[46]:
def choisir_module(S, modules):
"""
Entrée : un site S et une liste des modules au format défini dans l'énoncé
Sortie : indice d'un module disponible pour S (ou None si aucun n'est disponible)
"""
for k in range(len(modules)):
if not conflit(S, modules[k]):
return k
return None
# In[47]:
choisir_module(["S1", 7, 10], [[["S3", 9, 11]], [["S5", 12, 15]]])
# In[48]:
choisir_module(["S1", 7, 10], [[["S3", 8, 10]], [["S5", 9, 12]]])
#
# Exercice 10
#
# In[49]:
def allocation_modules(sites):
"""
Entrée : une liste de sites au format défini par l'énoncé
Sortie : une liste des listes de sites regroupés par module.
"""
sites.sort(key=lambda x: x[1]) # on trie les sites par ordre de début croissant
modules = []
for S in sites: # parcours des sites
k = choisir_module(S, modules)
if k == None:
modules.append([S]) # on affecte un nouveau module
else:
modules[k].append(S) # on ajoute le site S au module n°k
return modules
# On reprend l'exemple de l'exercice 6 :
# In[50]:
S = [["S1", 0, 7], ["S2", 2, 5], ["S3", 6, 8], ["S4", 1, 2], ["S5", 5, 6],
["S6", 0, 2], ["S7", 4, 7], ["S8", 0, 1], ["S9", 3, 6], ["S10", 1, 3],
["S11", 4, 5], ["S12", 6, 8], ["S13", 0, 2], ["S14", 5, 7], ["S15", 1, 4]]
# In[51]:
allocation_modules(S)
# **Conclusion :**
# > Pour observer tous les sites, il est nécessaire (et optimal) d'utiliser $6$ modules différents, et un planning possible pour chacun d'eux est donné ci-dessus.