TP Pile et Files
Exercice 1 : La classe Pile
1. Implémenter en Python à l’aide du type list le TAD Pile.
Le constructeur d’une pile vide (creerPile du TAD) sera constitué de l' attribut _structure qui sera une liste
vide.
On rappelle que le type list en python possède deux méthodes très utiles :
La méthode append qui permet de rajouter un élément en fin de liste et la méthode pop qui permet de retirer
un élément de la liste.
Exercice 2 :
Simuler une gestion de l'historique de navigation internet, en créant une classe Nav qui utilisera une pile.
Attention, il ne faut pas réinventer la classe Pile, mais s'en servir !
Exemple d'utilisation :
>>> n = Nav()
>>> [Link]('[Link]')
page actuelle : [Link]
>>> [Link]('[Link]')
page actuelle : [Link]
>>> [Link]('[Link]')
page actuelle : '[Link]
>>> [Link]()
page quittée : '[Link]
>>> [Link]()
page quittée : [Link]
Exercice 3 :
Écrire une fonction renverse qui a pour argument une pile et qui retourne une pile dont les éléments ont étés
renversés.
Exercice 4 :
Écrire une fonction maxPile qui a pour argument une pile de nombres et qui retourne le plus grand élément
de cette pile.
Exercice 5 : Application – Vérification syntaxique
Lors de la compilation d'un programme, l'une des étapes consiste à vérifier la syntaxe du code. En particulier,
il faut vérifier que les expressions algébriques sont bien parenthésées, c'est-à-dire, de s'assurer que les
éléments parenthèses sont proprement inclus les unes dans les autres.
Par exemple, l'expression (((a+b)×c)+(a+d)×e)/(2×a) est correctement parenthésée.
A l'inverse, les expressions ((a+b) , (a+b)×c) et (a+b))×(c ne le sont pas. En particulier, il ne suffit pas d'avoir le
même nombre de parenthèses fermantes et ouvrantes pour que l'expression soit bien parenthésée.
Ecrire une fonction parenthese, qui a en argument une expression représentée par une chaîne de caractères,
et qui retourne à l'aide de pile, un booléen suivant si l'expression est bien parenthésée ou non.
Exercice 6 : La classe File
Implémenter en Python à l’aide du type list le TAD Pile.
Exercice 7 :
Écrire en PYTHON une fonction renverse_file qui en entrée prend une file et qui en sortie ne renvoie rien
mais utilise une pile pour renverser la file de départ.
Par exemple si F vaut 2 → 3 → 5 → 1 alors renverse_file(F) doit renvoyer 1 → 5 → 3 → 2.
Exercice 8 :
Écrire en PYTHON une fonction max_file qui en entrée prend une file non vide composée d’int positifs et
qui renvoie le maximum de cette file.
Attention la file doit être remise dans l’état initial et aucune autre structure de donnée (pile, file, liste) ne doit
être utilisée.
Par exemple si F vaut 2 → 3 → 5 → 1 alors max_file(F) doit renvoyer 5 et laisser F telle quelle.
Exercice 9 : Implémentation d'une file avec deux piles
Comment créer une file avec 2 piles ?
L'idée est la suivante : on crée une pile d'entrée et une pile de
sortie.
• quand on veut enfiler, on empile sur la pile d'entrée.
• quand on veut défiler, on dépile sur la pile de sortie.
• si celle-ci est vide, on dépile entièrement la pile
d'entrée dans la pile de sortie.
Implémenter en Python à l’aide de la classe Pile le TAD File.
Exercice : Le problème de Josèphe.
On place en cercle les joueurs. On décide d'un joueur point de départ. Puis on compte 7 joueurs en partant du
premier et on élimine le 7ème. On compte ensuite 7 joueurs en partant du suivant et on élimine...etc.
L'objectif du problème est de déterminer le dernier joueur restant.
On illustration avec 5 joueurs et un compte de 3 en 3 :
On compte 3 à Le joueur D est le
On compte 3 à partir On compte 3 à partir On compte 3 à
partir du joueur gagnant.
du joueur A. Et on du joueur D. Et on partir du joueur B.
B. On élimine B.
élimine C. élimine A. Et on élimine E.
Ecrire en python une fonction prenant en paramètres la liste des joueurs et le module (dans l'exemple, le
module est 3) et qui renvoie le gagnant. On utilisera une file.
