TP2 - Pile/File programmation Objet

Objectifs

1. Représenter des structures de données en objet ;
2. Créer un ensemble de méthodes manipulant ces objets.

Au préalable

1. Se créer un dossier Terminale NSI sur votre ordinateur ou clé USB
2. Dans ce dossier, créer un dossier Structures Linéaires

Sur EduPython ou autre instance python, faire :

1. Créer un nouveau fichier en cliquant sur l'icône 📄, ou en appuyant sur CTRL+N
2. Enregistrer le fichier sous le nom TP2_Pile_File_POO en cliquant sur l'icône 💾, ou en appuyant sur CTRL+S

TP

L'ensemble des exercices se fait sur python.
Dans ce TP, les piles et les files contiennent toutes les 2 des attributs :

• tete : None ou valeur passée en paramètre ;
• reste : None s’il n’y en a pas, une Pile/File s’il y en a un, passé en paramètre.

Files

Soit le code suivant :

class File :
    def __init__(self, ..., ...):
    ...
    def estVide(self):
    ...
    def enfiler(self, ...):
    ...
    def defiler(self):
    ...
    def taille(self):
    ...
    def affichage(self):
    ...

Exercice 1

En vous aidant des méthodes que vous avez défini lors du TP dernier, compléter la classe ainsi que ses méthodes.
L’élément en tête de file est le premier à partir, enfiler rajoute à chaque fois un élément à la fin.

Exercice 2

Écrire une méthode passerPremier(self, i) dans la classe, qui va placer l’élément à la i-ème place en première place.
Vous pourrez vous aider d’un schéma pour comprendre le fonctionnement de la méthode.

Exercice 3

Écrire une méthode changerPlace(self, i, j) dans la classe, qui va échanger de place l'élément à la i-ème place avec celui à la j-ème place.
Vous pourrez vous aider d’un schéma pour comprendre le fonctionnement de la méthode.

Exercice 4

TESTER la classe et les méthodes associées.

Piles

Soit le code suivant :

class Pile :
    def __init__(self, ..., ...):
    ...
    def estVide(self):
    ...
    def empiler(self, ...):
    ...
    def depiler(self):
    ...
    def taille(self):
    ...
    def affichage(self):
    ...

Exercice 1

En vous aidant des méthodes que vous avez défini lors du TP dernier, compléter la classe ainsi que ses méthodes.
L’élément en tête de pile est le premier à partir, empiler rajoute à chaque fois un élément au début de la pile.

Exercice 2

Écrire une méthode recherche(self,x) qui vérifie si l’élément x est bien présent dans la pile.
Vous pourrez vous aider d’un schéma pour comprendre le fonctionnement de la méthode.

Exercice 3

TESTER la classe et les méthodes associées.

Aller plus loin

Exercice 1 : max Pile

Créer une fonction maxPile(P, i) ayant pour paramètres une pile P et un entier i. Cette fonction renvoie la position du plus grand élément parmi les i premiers é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.

Exercice 2 : Retourner

Créer une fonction retourner(P,j) ayant pour paramètres une pile P et un entier j. Cette fonction inverse l’ordre des j premiers éléments empilés, et ne renvoie rien.
On pourra utiliser deux piles temporaires.
Faire un schéma pour comprendre le fonctionnement.

Exercice 3 : Crêpier psychorigide

On souhaite modéliser une pile de crêpes, chacune représentée par un numéro modélisant leur taille. Ainsi la "crêpe 1" sera plus petite que la "crêpe 2", elle-même plus petite que la "crêpe 3" et ainsi de suite.

Le but : on souhaite trier les crêpes par ordre croissant, c’est-à-dire que la plus grosse crêpe soit tout en dessous de la pile, la plus petite tout en haut.

On définit l’algorithme 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.

Créer la fonction tri_crepes(P) 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.
Vous pourrez faire un schéma pour expliciter le fonctionnement du tri crêpe.