Aller au contenu

Exercices pour s'entraîner sur les Piles☘

Prenez l'habitude de revenir vous entraîner régulièrement avec ces exercices tout au long de l'année. Ils sont généralement accompagnés de pistes et de leur solution pour vous permettre de progresser.

Rappels

  • Chaque programme Python doit être sauvegardé sous forme de fichier texte avec l'extension .py.
    Enregistrez ce fichier dans le dossier [A01-Piles_Files] avec le nom donné à l'exercice : ProgA01.52.py, ProgA01.53.py, etc...
  • Pour exécuter ce programme, il suffit de le sauvegarder puis d'appuyer sur la touche [F5].

Préambule☘

Téléchargez le module TAD_Piles.py qui contient une implémentation objet de pile. Placez ce module dans le répertoire de travail [A01-Piles_Files].
L'interface est celle donnée dans le cours :

Méthode/Opérations Description
P = Pile() Initialisation d'une pile vide.
P.est_vide() Renvoie True si la pile P est vide, False sinon.
P.empiler(elt) Empile un nouvel élément au sommet de la pile.
P.depiler() Lorsque la pile P n'est pas vide, supprime le sommet de la pile et renvoie la valeur de ce sommet.

L'affichage de la pile avec la fonction print() est aussi implémenté.

Consignes générales☘

Dans chacun des exercices de cette page, il vous est demandé :

  • d'importer le module ;
  • d'utiliser une (ou plusieurs) piles pour réaliser les programmes demandés.

Les fonctions des programmes A01.52 jusqu'à A01.56 peuvent être programmées dans le même fichier Python.

Il n'est pas utile de chercher à comprendre comment la structure de pile a été implémentée pour réaliser ces programmes.

Exercice A01.51☘

Réalisez un plan de test de l'interface du module TAD_Piles.py.

Une réponse possible
>>> p = Pile()    
>>> p.est_vide()
True

>>> p.empiler(7)    
>>> p.empiler(4)    
>>> p.empiler(3)    
>>> p    
3
4
7

>>> p.depiler()
3

>>> p.empiler(8)    
>>> p    
8
4
7

>>> p.est_vide()
False

ProgA01.52☘

Complétez le code de la fonction pile_alea() qui prend en paramètres trois entiers borne_inf, borne_sup et nb. Cette fonction renvoie une pile contenant nb entiers aléatoires générés entre borne_inf et borne_sup.

1
2
3
4
5
6
7
def pile_alea(borne_inf, borne_sup, nb):
    """
    borne_inf, borne_sup - int, entiers tels que borne_inf < borne_sup
    nb - int, entier strictement positif
    Sortie: Pile - pile constituée de nb entiers aléatoires générés entre borne_inf et borne_sup
    """
    pass

Exemple de tests

>>> p = pile_alea(0, 50, 5)    
>>> p
24
44
4
38
1
Une solution

Il ne faut pas oublier d'importer la fonction randint du module random... 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
from TAD_Piles import *
from random import randint

def pile_alea(borne_inf, borne_sup, nb):
    """
    borne_inf, borne_sup - int, entiers tels que borne_inf < borne_sup
    nb - int, entier strictement positif
    Sortie: Pile - pile constituée de nb entiers aléatoires générés entre borne_inf et borne_sup
    """
    p = Pile()
    for i in range(nb):
        p.empiler(randint(borne_inf, borne_sup))
    return p

ProgA01.53☘

  1. Dans la console, testez les instructions ci-dessous (les réponses de la console ont été volontairement effacées).
    Que pouvez-vous constater ?

    >>> p = pile_alea(0, 50, 5)    
>>> p

>>> k = p    
>>> k

>>> k.depiler()

>>> k

>>> p
    Une solution

    On peut constater que l'affectation « = » a simplement rajouté un alias (une étiquette) supplémentaire à la pile p. L'affectation ne crée donc pas une nouvelle pile et toute modification en utilisant l'alias k entraîne de facto une modification sous l'alias p. 

    >>> p = pile_alea(0, 50, 5)        
>>> p
24
44
4
38
1

>>> k = p        
>>> k
24
44
4
38
1

>>> k.depiler()
24

>>> k
44
4
38
1

>>> p
44
4
38
1
    Il faut donc créer une fonction de copie de Pile pour éviter cet inconvénient...

  2. Complétez le code de la fonction copie_pile() qui prend en paramètre une pile p et qui renvoie une autre pile contenant les mêmes éléments que p dans le même ordre. 

    1
2
3
4
5
6
    def copie_pile(p):
    """
    p - Pile
    Sortie: Pile - pile constituée des mêmes éléments que p, dans le même ordre et sans modifier p
    """
    pass

    Exemple de tests

    >>> p = pile_alea(0, 50, 5)        
>>> p
24
44
4
38
1

>>> p2 = copie_pile(p)        
>>> p2
24
44
4
38
1

>>> p2.depiler()
24

>>> p2
44
4
38
1

>>> p
24
44
4
38
1

    Attention

    La pile p ne doit pas être modifiée par effet de bord.

    Une piste

    Utilisez une pile temporaire.

    Une autre piste

    Empilez les éléments de la pile d'origine dans la pile temporaire puis dépilez la pile temporaire pour remplir la pile d'origine et la pile « copie ».

    Une solution
    def copie_pile(p):
    """
    p - Pile
    Sortie: Pile - pile constituée des mêmes éléments que p,
            dans le même ordre et sans modifier p
    """
    temp = Pile()
    resultat = Pile()
    while not p.est_vide():
        element = p.depiler()
        temp.empiler(element)

    while not temp.est_vide():
        element = temp.depiler()
        p.empiler(element)
        resultat.empiler(element)

    return resultat

ProgA01.54☘

Complétez le code de la fonction hauteur_pile() qui prend en paramètre une pile et qui renvoie le nombre d'éléments de cette pile.

1
2
3
4
5
6
def hauteur_pile(p):
    """
    p - Pile
    Sortie: int - nombre d'éléments de la pile p, sans modifier cette pile
    """
    pass

Exemple de tests

>>> p = pile_alea(0, 50, 5)    
>>> hauteur_pile(p)
5

Attention

Cette pile ne doit pas être modifiée par effet de bord.

Une piste

La même que celle de l'exercice précédent.

Une solution
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def hauteur_pile(p):
    """
    p - Pile
    Sortie: int - nombre d'éléments de la pile p, sans modifier cette pile
    """
    temp = Pile()
    hauteur = 0
    while not p.est_vide():
        element = p.depiler()
        temp.empiler(element)
        hauteur += 1

    while not temp.est_vide():
        element = temp.depiler()
        p.empiler(element)

    return hauteur

ProgA01.55☘

  1. Complétez le code de la fonction inverser_pile() qui prend en paramètre une pile et qui inverse cette pile par effet de bord : le premier élément (le sommet) passe au fond, le deuxième au-dessus, etc...

    1
2
3
4
5
6
    def inverser_pile(p):
    """
    p - Pile
    Sortie: None - les éléments de la pile p sont inversés (effet de bord)
    """
    pass

    Exemple de tests

    >>> p = Pile()
>>> for i in range(5):
...    p.empiler(i)

>>> p
4
3
2
1
0

>>> inverser_pile(p)
>>> p
0
1
2
3
4
    Une piste

    Pour cette fonction, utilisez deux piles temporaires.

    Une solution
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
    def inverser_pile(p):
    """
    p - Pile
    Sortie: None - les éléments de la pile p sont inversés (effet de bord)
    """
    t_pile = Pile()
    td_pile = Pile()

    while not(p.est_vide()):
        elt = p.depiler()
        t_pile.empiler(elt)

    while not(t_pile.est_vide()):
        elt = t_pile.depiler()
        td_pile.empiler(elt)

    while not(td_pile.est_vide()):
        elt = td_pile.depiler()
        p.empiler(elt)

  2. Complétez le code de la fonction echange_sommet_fond() qui prend en paramètre une pile et qui échange, par effet de bord, le premier élément (le sommet) et le dernier élément (le fond) de cette pile.

    1
2
3
4
5
6
    def echange_sommet_fond(p):
    """
    p - Pile
    Sortie: None - Le premier et le dernier élément de la pile sont échangés (effet de bord)
    """
    pass

    Exemple de tests

    >>> p = Pile()
>>> for i in range(5):
...    p.empiler(i)

>>> p
4
3
2
1
0

>>> echange_sommet_fond(p)
>>> p
0
3
2
1
4

>>> p = Pile()
>>> p.empiler(3)
>>> echange_sommet_fond(p)
>>> p
3
    Une piste

    Plusieurs méthodes sont possibles, par exemple en faisant appel aux fonctions hauteur_pile() ou inverser_pile().

    Une première solution
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
    def echange_sommet_fond(p):
    """
    p - Pile
    Sortie: None - Le premier et le dernier élément de la pile sont échangés (effet de bord)
    """
    first_out = p.depiler()

    inverser_pile(p)

    last_out = p.depiler()

    p.empiler(first_out)

    inverser_pile(p)

    p.empiler(last_out )
    Une deuxième solution
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
    def echange_sommet_fond(p):
    """
    p - Pile
    Sortie: None - Le premier et le dernier élément de la pile sont échangés (effet de bord)
    """
    inverser_pile(p)

    first_out = p.depiler()

    temp_pile = Pile()

    for i in range(hauteur_pile(p)-1):
        elt = p.depiler()
        temp_pile.empiler(elt)

    inverser_pile(temp_pile)

    while not(temp_pile.est_vide()):
        elt = temp_pile.depiler()
        p.empiler(elt)

    p.empiler(first_out)

ProgA01.56*☘

Complétez la définition de la fonction tri_selection_pile() qui prend en paramètre une pile d'entiers p et renvoie une pile constituée des éléments de p triés par ordre croissant (Le plus petit élément au sommet). 

1
2
3
4
5
6
7
8
def tri_selection_pile(p):
    """
    p - Pile d'entiers
    Sortie: Pile - pile constituée des éléments de p triés par ordre croissant
            (le sommet est le plus petit).
            La pile p est vidée.
    """
    pass

Exemple de tests

>>> p = pile_alea(0, 50, 5)    
>>> p
24
44
4
38
1

>>> p1 = tri_selection_pile(p)    
>>> p1
1
4
24
38
44

>>> p

Attention

Dans cet exercice, la pile p va être modifiée par effet de bord.

Une piste

Utilisez une pile temporaire et une pile résultat.

Une autre piste

Un algorithme possible :

Tant que la pile d'origine n'est pas vide :

  1. On dépile son sommet qu'on suppose être le maximum
  2. Tant que la pile d'origine n'est pas vide :
    1. On dépile son sommet
    2. Ou bien ce sommet est plus petit que le maximum, alors on l'empile dans la pile temporaire
    3. Ou bien ce sommet est plus grand que le maximum, alors on empile ce maximum dans la pile temporaire et le sommet dépilé devient le nouveau maximum
  3. On empile le maximum dans la pile resultat
  4. Si la pile temporaire n'est pas vide :
    1. On dépile son sommet qui devient le maximum
    2. Tant que la pile temporaire n'est pas vide, on dépile son sommet, on le comparer au maximum et on empile soit ce sommet, soit le maximum dans la pile d'origine.
    3. Le maximum est enfin empilé dans la pile resultat
  5. On renvoie la pile résultat
Une solution
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def tri_selection_pile(p):
    """
    p - Pile d'entiers
    Sortie: Pile - pile constituée des éléments de p triés par ordre croissant
            (le sommet est le plus petit).
            La pile p est vidée.
    """
    if p.est_vide():
        return Pile()

    temp = Pile()
    resultat = Pile()
    while not p.est_vide():
        maxi = p.depiler()
        while not p.est_vide():
            element = p.depiler()
            if element < maxi:
                temp.empiler(element)
            else:
                temp.empiler(maxi)
                maxi = element
        resultat.empiler(maxi)

        if not temp.est_vide():
            maxi = temp.depiler()
            while  not temp.est_vide():
                element = temp.depiler()
                if element < maxi:
                    p.empiler(element)
                else:
                    p.empiler(maxi)
                    maxi = element
            resultat.empiler(maxi)

    return resultat