Tri d'une pile
D'après 2022, Polynésie, J1, Ex. 4
La classe Pile
utilisée dans cet exercice est implémentée en utilisant des listes Python et propose quatre éléments d'interface :
- Un constructeur qui permet de créer une pile vide, représentée par
[]
; - La méthode
est_vide()
qui renvoieTrue
si l'objet est une pile ne contenant aucun élément, etFalse
sinon ; - La méthode
empiler
qui prend un objet quelconque en paramètre et ajoute cet objet au sommet de la pile. Dans la représentation de la pile dans la console, cet objet apparait à droite des autres éléments de la pile ; - La méthode
depiler
qui renvoie l'objet présent au sommet de la pile et le retire de la pile.
Exemples :
>>> ma_pile = Pile()
>>> ma_pile.empiler(2)
>>> ma_pile
[2]
>>> ma_pile.empiler(3)
>>> ma_pile.empiler(50)
>>> ma_pile
[2, 3, 50]
>>> ma_pile.depiler()
50
>>> ma_pile
[2, 3]
La méthode est_triee
ci-dessous renvoie True
si, en dépilant tous les éléments, ils sont traités dans l'ordre croissant, et False
sinon.
🐍 Script Python | |
---|---|
1 2 3 4 5 6 7 8 9 |
|
1. Recopier sur la copie les lignes 6 et 8 en complétant les points de suspension.
Réponse
🐍 Script Python | |
---|---|
1 2 3 4 5 6 7 8 9 |
|
On crée dans la console la pile A
représentée par [1, 2, 3, 4]
.
2.a. Donner la valeur renvoyée par l'appel A.est_triee()
.
Réponse
La valeur \(4\) est d'abord dépilée, puis \(3\). L'ordre n'est pas croissant, ainsi A.est_triee()
renvoie False
.
2.b. Donner le contenu de la pile A
après l'exécution de cette instruction.
Réponse
A
sera représenté par [1, 2]
.
On souhaite maintenant écrire le code d'une méthode depile_max
d'une pile non vide ne contenant que des nombres entiers et renvoyant le plus grand élément de cette pile en le retirant de la pile.
Après l'exécution de p.depile_max()
, le nombre d'éléments de la pile p
diminue donc de 1.
🐍 Script Python | |
---|---|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
3. Recopier sur la copie les lignes 9 et 11 en complétant les points de suspension.
Réponse
🐍 Script Python | |
---|---|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
On crée la pile B
représentée par [9, -7, 8, 12, 4]
et on effectue l'appel B.depile_max()
.
4.a. Donner le contenu des piles B
et q
à la fin de chaque itération de la boucle while
de la ligne 5.
Réponse
B
contient[9, -7, 8, 12]
;q
est vide ;maxi
est égal à4
.
Juste avant le premier tour de boucle
B
contient[9, -7, 8]
;q
contient[4]
;maxi
est égal à12
.
B
contient[9, -7]
;q
contient[4, 8]
;maxi
est égal à12
.
B
contient[9]
;q
contient[4, 8, -7]
;maxi
est égal à12
.
B
est vide ;q
contient[4, 8, -7, 9]
;maxi
est égal à12
.
4.b. Donner le contenu des piles B
et q
avant l'exécution de la ligne 14.
Réponse
La dernière boucle renverse la pile q
dans la pile B
, ainsi, à la ligne 14 :
q
est vide ;B
contient[9, -7, 8, 4]
.
4.c. Donner un exemple de pile qui montre que l'ordre des éléments restants n'est pas préservé après l'exécution de depile_max
.
Réponse
Avec une pile B
qui contient [3, 1, 2]
B
contient[3, 1]
;q
est vide ;maxi
est égal à2
.
Juste avant le premier tour de boucle
B
contient[3]
;q
contient[1]
;maxi
est égal à2
.
B
est vide ;q
contient[1, 2]
;maxi
est égal à3
.
La dernière boucle renverse la pile q
dans la pile B
, ainsi, à la ligne 14 :
q
est vide ;B
contient[2, 1]
.
Sans 3
dans la pile B
initiale, on a dans l'ordre [1, 2]
ce qui est différent de [2, 1]
obtenu ici avec depile_max
.
On a ainsi un exemple où l'ordre des éléments restants n'est pas préservé après l'exécution de depile_max
.
On donne le code de la fonction traiter
:
🐍 Script Python | |
---|---|
1 2 3 4 5 6 |
|
5.a. Donner les contenus successifs des piles B
et q
- avant la ligne 3,
- avant la ligne 5,
- à la fin de l'exécution de la fonction
traiter
lorsque la fonctiontraiter
est appelée avec la pileB
contenant[1, 6, 4, 3, 7, 2]
.
Réponse
Avec B = [1, 6, 4, 3, 7, 2]
, un appel B.traiter()
conduit successivement à :
- Avant la ligne 3,
B
contient[1, 6, 4, 3, 7, 2]
;q
est vide.
- Avant la ligne 5,
B
est vide ;q
contient[7, 6, 4, 3, 2, 1]
- À la fin,
B
contient[1, 2, 3, 4, 6, 7]
q
est vide.
5.b. Expliquer le traitement effectué par cette méthode.
Réponse
Ce traitement est un tri de la pile. On construit d'abord q
comme la pile des éléments de self
dans l'ordre décroissant. On renverse ensuite la pile, qui se retrouve comme si on avait empilé les éléments de self
dans l'ordre croissant.
Attention, il s'agit de l'ordre inverse de celui proposé par la fonction est_triee
vu à la question 1. ici, si on dépile les éléments, ils sont désormais dans l'ordre décroissant.