Exercice : Tri avec pelle à crêpe

Exercice adapté du sujet 0 de l'épreuve terminale de NSI – Exercice 1

Une pile est une structure de donnée basée sur le principe premier arrivé, dernier sorti. Dans l'exemple ci-contre, 17 est au sommet de la pile.

On munit la structure de données Pile de quatre fonctions primitives définies dans le cadre ci-dessous :

creer_pile_vide : $\varnothing$ → Pile
renvoie une pile vide
est_vide : Pile → Booléen
est_vide(pile) renvoie True si pile est vide, False sinon
empiler : Pile, Élément → $\varnothing$
empiler(pile, element) ajoute element au sommet de pile
depiler : Pile → Élément
depiler(pile) renvoie l’élément au sommet de pile en le retirant de la pile

Question 1

On suppose dans cette question que le contenu de la pile P est donné à droite.

Quel sera le contenu de la pile Q après exécution de la suite d’instructions suivante ?

Q = creer_pile_vide()
while not est_vide(P):
    empiler(Q, depiler(P))

Question 2

On appelle hauteur d'une pile le nombre d’éléments que contient la pile. La fonction hauteur_pile prend en paramètre une pile P et renvoie sa hauteur. Après appel de cette fonction, la pile P doit avoir retrouvé son état d’origine.

Ceci veut dire qu'il est possible que P soit modifiée au cours de la fonction, mais elle doit être revenu à son état d'origine à la fin.

Exemple : si P est la pile de la question 1 : hauteur_pile(P) renvoie 4.

Compléter le programme Python suivant implémentant la fonction hauteur_pile en remplaçant les ??? par les bonnes instructions.

def hauteur_pile(P):
    A = creer_pile_vide()
    n = 0
    while not (est_vide(P)):
        ???
        elem = depiler(P)
        empiler(A, elem)
    while not est_vide(A):
        ???
        empiler (P, elem)
    return ???

Question 3

Créer une fonction max_pile ayant pour paramètres une pile P et un entier i. Cette fonction renvoie la position j de l'élément maximum parmi les i derniers éléments empilés de la pile P.

Après appel de cette fonction, la pile P devra avoir retrouvé son état d’origine.

La position du sommet de la pile est 1.

Exemple : si P est la pile de la question 1, max_pile(P, 3) renvoie 2.

Question 4

Créer une fonction retourner ayant pour paramètres une pile P et un entier j. Cette fonction inverse l’ordre des j derniers éléments empilés et ne renvoie rien. On pourra utiliser deux piles auxiliaires.

Exemple : si P est la pile de la question 1, après l’appel de retourner(P, 3), l’état de la pile P sera celui donné à droite.

Question 5

L'objectif de cette question est de trier une pile de crêpes.

On modélise une pile de crêpes par une pile d’entiers représentant le diamètre de chaque crêpe. On souhaite réordonner les crêpes de la plus grande (placée en bas de la pile) à la plus petite (placée en haut de la pile).

On dispose uniquement d’une spatule que l'on peut insérer dans la pile de crêpes de façon à retourner l’ensemble des crêpes qui sont au-dessus d'elle.

Le principe est le suivant :

On recherche la plus grande crêpe.
On retourne la pile à partir de cette crêpe de façon à mettre cette plus grande crêpe tout en haut de la pile.
On retourne l’ensemble de la pile de façon à ce que cette plus grande crêpe se retrouve tout en bas.
La plus grande crêpe étant à sa place, on recommence le principe avec le reste de la pile.

On illustre cette méthode par la figure ci-dessous. La figure se limite au tri des deux plus grands éléments. Il faudrait poursuivre ainsi jusqu'à avoir trié la totalité de la pile.

Créer la fonction tri_crepes ayant pour paramètre une pile P. Cette fonction trie la pile P selon la méthode du tri crêpes et ne renvoie rien. On utilisera les fonctions créées dans les questions précédentes.