====== Exercice : Tri avec pelle à crêpe ======

{{ .:exo_pile_tri_pelle_a_crepes.pdf |Version imprimable}}

{{ .:sujet_0_pile_1.png?direct&100|}}

<WRAP info>Exercice adapté du {{ .:sujet_0.pdf |sujet 0}} de l'épreuve terminale de NSI -- Exercice 1</WRAP>


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 :

<WRAP box>
  * ''%%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
</WRAP>

===== Question 1 =====

{{ .:sujet_0_pile_2.png?direct&100|}}

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 ?

<code python linenums>
Q = creer_pile_vide()
while not est_vide(P):
    empiler(Q, depiler(P))
</code>

===== 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.

<WRAP tip>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.</WRAP>

**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.

<code python linenums>
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 ???
</code>

===== 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 =====

{{ .:sujet_0_pile_3.png?direct&100|}}

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.

{{ .:sujet_0_pile_4.png?direct&600 |}}


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.