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])

Out[3]:

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)

Out[5]:

[1, 0, 1, 1, 0, 1, 1, 0]

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)

Out[6]:

[2, 1, 0, 2, 0, 0, 1, 0]

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)

Out[8]:

[1, 0, 1, 1, 0, 1, 1, 0]

In [9]:

rendu_glouton(542)

Out[9]:

[2, 1, 0, 2, 0, 0, 1, 0]

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)

Out[11]:

[1, 0, 1, 1, 0, 1, 1, 0]

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)

Out[13]:

[1, 0, 2]

In [14]:

pieces2cents([0, 2, 0])

Out[14]:

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)

Out[18]:

[1, 0, 1, 1, 0, 1, 1, 1]

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)

Out[20]:

[1, 0, 0, 3, 1, 1, 1, 1]

In [21]:

pieces2cents(_)

Out[21]:

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)

---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
<ipython-input-23-c64220e7720f> in <module>
----> 1 rendu_glouton_caisse(190)

<ipython-input-17-75b35bd120c0> in rendu_glouton_caisse(montant)
      9     while m > 0:
     10         i = 0
---> 11         while VALEURS[i] > m or CAISSE[i] == 0:
     12             i += 1
     13         pieces[i] += 1

IndexError: list index out of range

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)

Out[27]:

[1, 0, 1, 1, 0, 1, 1, 0]

In [28]:

CAISSE

Out[28]:

[10, 10, 10, 100, 100, 100, 100, 100]

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)

Out[30]:

[1, 0, 1, 1, 0, 1, 1, 0]

In [31]:

CAISSE

Out[31]:

[9, 10, 49, 99, 100, 99, 99, 0]

In [32]:

rendu_glouton_caisse(278)

In [33]:

CAISSE

Out[33]:

[9, 10, 49, 99, 100, 99, 99, 0]

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)

Out[37]:

[['S8', 0, 1], ['S4', 1, 2], ['S2', 2, 5], ['S5', 5, 6], ['S3', 6, 8]]

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]])

Out[44]:

True

In [45]:

conflit(["S1", 1, 3], [["S2", 4, 6], ["S3", 5, 7]])

Out[45]:

False

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]]])

Out[47]:

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)

Out[51]:

[[['S1', 0, 7]],
 [['S6', 0, 2], ['S2', 2, 5], ['S5', 5, 6], ['S3', 6, 8]],
 [['S8', 0, 1], ['S4', 1, 2], ['S9', 3, 6], ['S12', 6, 8]],
 [['S13', 0, 2], ['S7', 4, 7]],
 [['S10', 1, 3], ['S11', 4, 5], ['S14', 5, 7]],
 [['S15', 1, 4]]]

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.