TD3. Les Piles Et Les Files: Exercices 1

Algorithmique avancée et SD ING1 GSI AU 2023/2024
TD3. Les Piles et Les Files

- Dans les exercices avec piles et files il suffit de faire appel aux sous algorithmes de base définis dans le cours.
Exercices 1:
Soit l’algorithme principale suivant :
ALGORITHME Principal
TYPE element = STRUCTURE

Info : ENTIER
Suivant : *Element
FIN STRUCTURE
TYPE Pile = STRUCTURE
sommet: *Element
nbrelt: entier
FIN STRUCTURE
VAR
P : PILE
Val1,val2 :ENTIER
DEBUT
/* Remplir la pile*/
PSaisie_pile (P)
Val1<-18
/* Afficher les 2 premières valeurs de la pile*/
POUR i DE 1 A 2 FAIRE
Dépiler(P,val2)
ECRIRE("La première valeur est: ", val2)
FINPOUR
/* Ajouter une valeur à la pile*/

Empiler(P,val1)
FIN
1.1. Compléter l’algorithme avec les cas possibles.
1.2. Exécuter cet algorithme sur l’exemple suivant et donner l’état de la Pile après chaque modification.
Sommet
@11
11 20 40
@20 @40 NIL
Exercices 2:
2.1. Ecrire une procédure PSaisie_pile (P) qui remplie une pile avec des mots saisis par l’utilisateur.
2.2. Ecrire une procédure PAfficher_pile (P) qui affiche tous les éléments d’une pile de mots.
2.3. Ecrire une fonction Fnbr_val_pile(P, val) qui cherche le nombre de valeur donnée dans une pile.
2.4. Ecrire une Fonction FChercher_val_pile (P,mot) qui cherche un mot dans une pile et retourne vrai si le mot est
trouvé, faux sinon.
Exercices 3:
Soit une pile P1 contenant des entiers positifs. Ecrire une procédure pour déplacer les entiers de P1 dans une pile P2 de
façon à avoir dans P2 tous les nombres pairs en dessus des nombres impairs en gardant l’ordre d’apparition des nombre
pairs et en inversant l’ordre d’apparition des nombres impairs.
Exercices 4 :
© O.Lamouchi -1-
Soit la fonction fpalindrome ci-dessous qui va vérifier si un mot donnée est un palindrome ou pas.
Le principe du palindrome est très simple. Ce sont des lettres qui, peu importe qu’elles soient lues de gauche à droite ou
de droite à gauche, donnent le même mot ou même groupe de mots.
Exemples : pop, tôt, radar… Ainsi ces mots peuvent se lires dans les deux sens.
4.1. Compléter la fonction fpalindrome qui va vérifier si une chaine de caractère est palindrome ou pas.
(Remarque : les types PILE et LISTE sont conformes aux définitions vues en cours.)
FONCTION fpalindrome (Lmot:LISTE):BOOLEAN
VAR
Pmot : PILE
vpalind : BOOLEEN
:
DEBUT
/* Copier la liste dans une pile*/
Pmot<-copier_L(Lmot)
/*Vérifier si le mot est palindrome ou pas en utilisant la pile Pmot*/
RETOURNER(vpalind)
FIN
© O.Lamouchi -2-
Exercices 5:
Soit l’algorithme principale suivant :
ALGORITHME Principal
TYPE element = STRUCTURE

Info : entier
Suivant : *Element
FIN STRUCTURE
TYPE File = STRUCTURE
Debut: *Element
Queue: *Element
nbrelt: entier
FIN STRUCTURE
VAR
F : FILE
Val1,val2 :ENTIER
DEBUT
Val1<-20
/* Remplir la File*/
FSaisie_file (F)
/* Afficher la première valeur de la File*/
val2<-Defiler(F)
ECRIRE("La première valeur est: ", val2)
/* Ajouter des valeurs à la File*/
Enfiler(F,val1)
Enfiler(F,val1*val2)
FIN
5.1. Exécuter cet algorithme sur l’exemple suivant et donner l’état de la File après chaque modification.
Début Queue
@13 @45
13 19 45
@19 @45 NIL
Exercices 6:
6.1. Ecrire une procédure FSaisie_file (F) qui remplie une file avec des entiers saisis par l’utilisateur.
6.2. Ecrire une procédure FAfficher_file (F) qui affiche tous les éléments d’une file.
6.3. Ecrire une fonction Fnbr_val_file(F, val) qui cherche le nombre d’une valeur donnéé, dans une file.
6.4. Ecrire une Fonction FChercher_val_file (F,val) qui cherche une valeur dans une file et retourne vrai si la valeur est
trouvée, faux sinon.
Exercices 7:
Ecrire une procédure PInverser_pile (P) qui inverse une pile de réels.
7.1. Doit-on utiliser une pile ou une file?
7.2. Que faire si l’utilisation des files était interdite?
© O.Lamouchi -3-
Exercices 8:
On cherche à exécuter les opérations primitives d’une file (enfiler et défiler) en utilisant seulement les opérations
primitives d’une pile (empiler et dépiler).
Exercices 9:
On veut informatiser le processus de prise de commandes dans un restaurant. Chaque table est identifiée par un code et
son nombre de place maximum. Les données concernant ces tables sont sauvegardées dans une liste chainée triée.
- On veut avoir l’ordre des commandes passées pour chaque table.
- On veut avoir, aussi, pour chaque table l’ensemble des plats commandés. Les plats sont identifiés par un codePlat.
L’objectif est d’afficher au cuisinier les commandes en ordre et l’ensemble des plats à préparer pour chacune de ces
commandes.
La solution demandée doit utiliser :
- Une file pour avoir l’ordre des commandes passées, la première table qui a passé une commande c’est la
première qui doit être servie.
- Une pile pour avoir les plats commandés pour chaque table.
Travail à faire :
1- Définir l’ensemble des structures à utiliser.
2- Ecrire la procédure Commande_Table (E/S Ftable : File) qui va afficher au cuisinier l’ensemble des plats
commandés pour la commande première commande dans la file.
© O.Lamouchi -4-

TD3. Les Piles Et Les Files: Exercices 1

Transféré par

Droits d'auteur :

Formats disponibles

TD3. Les Piles Et Les Files: Exercices 1

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

TD3. Les Piles Et Les Files: Exercices 1

Transféré par

Droits d'auteur :

Formats disponibles

Algorithmique avancée et SD ING1 GSI AU 2023/2024

TD3. Les Piles et Les Files

Soit l’algorithme principale suivant :

TYPE element = STRUCTURE

/* Ajouter une valeur à la pile*/

FONCTION fpalindrome (Lmot:LISTE):BOOLEAN

/Vérifier si le mot est palindrome ou pas en utilisant la pile Pmot/

Soit l’algorithme principale suivant :

TYPE element = STRUCTURE

/* Afficher la première valeur de la File*/

/* Ajouter des valeurs à la File*/

Vous aimerez peut-être aussi