Devoir sur les Piles et les files

L'usage de la calculatrice n'est pas autorisé.

Durée : 1 heure et 20 minutes

Exercice 1

SujetCorrigé

Cet exercice utilise des piles qui seront représentées en Python par des listes (type list). On rappelle que l’expression T1 = list(T) fait une copie de T indépendante de T, que l’expression x = T.pop()enlève le sommet de la pile T et le place dans la variable x et, enfin, que l’expression T.append(v) place la valeur v au sommet de la pile T.

Compléter le code Python de la fonction positif ci-dessous qui prend une pile T de nombres entiers en paramètre et qui renvoie la pile des entiers positifs dans le même ordre, sans modifier la variable T.

def positif(T):
    T2 = ...(T)
    T3 = ...
    while T2 != []:
        x = ...
        if ... >= 0:
            T3.append(...)
    T2 = []
    while T3 != ...:
        x = T3.pop()
        ...
    print('T = ',T)
return T2

Exemple :

>>> positif([-1,0,5,-3,4,-6,10,9,-8 ])
T = [-1, 0, 5, -3, 4, -6, 10, 9, -8]
[0, 5, 4, 10, 9]

Il s'agit du sujet 16 de l'épreuve pratique 2022

def positif(T):
    T2 = list(T)
    T3 = []
    while T2 != []:
        x = T2.pop()
        if x >= 0:
            T3.append(x)
    T2 = []
    while T3 != []:
        x = T3.pop()
        T2.append(x)
    print('T = ',T)
    return T2

Exercice 2

SujetCorrigé

Dans un supermarché il y a 5 caisses et une file d’attente commune. Dès qu’une caisse est libre, le client en tête de file y est envoyé. Le temps de passage en caisse est aléatoirement compris entre 3 et 10 minutes. Il y a dix clients dans la file d’attente.

Pour la liste des caisses, vous utiliserez une liste [0,0,0,0,0], premier élément temps caisse 1, ici à 0, puis temps caisse 2 etc.

À l'aide de la classe File vue en classe, réaliser une simulation de leurs passages en caisses et afficher en combien de minutes tous les clients sont passés.

## Création de la file de 10 clients:
Client=File()
for i in range(10):
    Client.enfiler(random.randint(3,10))

## Création d'une liste de booléens qui correspond à la disponibilité des caisses, elle est initialisée à True partout.
Dispocaisses=[True]*5

## Création de la liste des temps aux caisses.
Tempscaisses=[0]*5

## Fonction qui retourne l'indice de la première caisse libre ou -1 si il n'y en a pas.
def Caisselibre(L):
    for i in range(len(L)):
        if L[i]==True:
            return i
    return -1

## Fonction qui met à disponible (False), les caisses qui ont les valeurs de temps les plus petites (sachant que toutes les caisses sont occupées).
def Liberecaisse(T, D):
    minimum=min(T)
    for i in range(len(T)):
        if T[i]==minimum:
            D[i]=True


## Programme principal

while not Client.estvide():
    Caissedispo=Caisselibre(L)
    if Caissedispo>-1:
        Dispocaisses[Caissedispo]=False
        Tempscaisses[Caissedispo]=Tempscaisses[Caissedispo]+Client.defiler()
    else:
        Liberecaisse(Tempscaisses,Dispocaisses)

## On affiche le résultat
print(max(Tempscaisses))

Exercice 3

SujetCorrigé

On considère deux jeux de 54 cartes à jouer. Pour les mélanger, on crée un troisième paquet en empilant les cartes aléatoirement piochées dans un des deux jeux. Quand l’un des deux jeux est vide, on empile le jeu restant sur le troisième paquet. On modélisera les deux jeux de 54 cartes par deux listes contenant respectivement les entiers de 101 à 154 et de 201 à 254.

Écrire une fonction python qui réalise le mélange.

# On crée les 3 piles
P1=Pile()
P2=Pile()
P3=Pile()

# On remplit les deux premières avec les cartes
for i in range(101,155):
    P1.empiler(i)
    P2.empiler(100+i)

# On remplit la pile P3 aléatoirement
def melange(P1,P2):
    while not P1.estvide() and not P2.estvide():
        if random.randint(1,2)==1:
            for i in range(random.randint(0,2)):
                P3.empiler(P1.depiler())
        else:
            for i in range(random.randint(0,2)):
                P3.empiler(P2.depiler())
    if P1.estvide():
        while not P2.estvide():
            P3.empiler(P2.depiler())
    else:
        while not P1.estvide():
            P3.empiler(P1.depiler())
    return P3

Exercice 4

SujetCorrigé

Une pile bornée est une pile dotée à sa création d'une capacité maximale. On propose l'interface suivante:

Fonction	description
creer_pile(c)	crée et renvoie une pile bornée de capacité c
est_vide(p)	renvoie True si la pile est vide et False sinon
est_pleine(p)	renvoie True si la pile est pleine et False sinon
empiler(p,e)	ajoute e au sommet de p si p n'est pas pleine et renvoie une erreur sinon
depiler(p)	retire et renvoie l'élément au sommet de p si p n'est pas vide et renvoie une erreur sinon

On propose de réaliser une telle pile bornée à l'aide d'un tableau dont la taille est fixée à la création et correspond à la capacité. Les éléments de la pile sont stockés consécutivement à partir de l'indice 0 (qui contient l'élément du fond de la pile). On se donne également un entier enregistrant le nombre d'éléments dans la pile, qui permet donc également de désigner l'indice de la prochaine case libre.

Réaliser une telle structure à l'aide d'une classe ayant pour attributs le tableau fixe et le nombre d'éléments dans la pile bornée.

class PileBornee:

    def __init__(self,c):
        self.contenu=[None]*c
        self.nb=0

    def estvide(self):
        return self.nb==0

    def estpleine(self):
        return self.nb==len(self.contenu)

    def empiler(self,e):
        if self.estpleine():
            raise IndexError("La pile est déjà pleine")
        self.contenu[self.nb]=e
        self.nb=self.nb+1

    def depiler(self):
        if self.estvide():
            raise IndexError("La pile est vide")
        self.nb=self.nb-1
        v=self.contenu[self.nb]
        self.contenu[self.neb]=None
        return v