Corrigé des exercices PDF Exercice 2. La première

SUJET + CORRIGE

16 déc. 2011 Exercice 1 (Files à l'aide de Piles (8 points)). Nous avons vu en cours une implémentation d'un pile par un tableau borné. CreerPileVide (N){.

Algorithmique et Structures de données 1 Piles

Feuille 4 : Piles et Files. Dans les exercices suivants on consid`ere les types abstraits : type_Pile = Pile de objet;. type_File = File de objet; définis en

Pile renversée Exercice 2: suppression dun élément Exercice 3

(Indication: il est légèrement plus simple d'utiliser des piles à capacité illimitée on n'a pas à s'occuper de leur capacité). • Le corrigé utilise les piles à

Langage C : énoncé et corrigé des exercices IUP GéniE

Langage C : énoncé et corrigé des exercices. 1.5. P ILE E T FILE. Ce s exercice 4 - Affi c h age par éc h ange de pointeurs d 'une pile implémentée en liste c ...

Corrigé de la série de TD N 03 de Structures de Données

Supprimer toutes les villes ayant plus de 10.000 habitants. Exercice n. ◦. 02: Piles Correction de l'exercice n. ◦. 5. On dispose d'une pile de nombres ...

TP 9 : LISTES CHAINÉES FILES DATTENTE

http://hebergement.u-psud.fr/mkowalski/doc/L3_IST_306_TP9.pdf

PILES ET FILES

Inversion d'une File en utilisant une Pile. Le but de cet exercice est d'écrire en Python une procédure qui inverse une file d'éléments qui lui est passée en.

Exercice 1 : piles et files

Exercices dirigés séance n°9 - corrigé. Exercice 1 : piles et files. Un système muti-tâches peut exécuter n tâches en quasi parallélisme. Chaque tâche est

SUJET + CORRIGE

16 déc. 2011 Exercice 1 (Files à l'aide de Piles (8 points)). Nous avons vu en cours une implémentation d'un pile par un tableau borné.

Algorithmique et Structures de données 1 Piles

type_File = File de objet; définis en cours. 1 Piles. Exercice 4.1. Evaluer `a l'aide des primitives du type abstrait Pile de objet la fonction suivante et.

TD – Piles et files - Corrigé

TD – Piles et files. Corrigé. Piles. Exercice N°1 – Copie d'une pile. Ecrire une fonction stack_copy(s) recevant une pile (s) comme argument et renvoyant.

Untitled

Exercice 6: Résolution d'un labyrinthe. Corrigé. Annexe. Correction du programme de parenthésage. Enoncé. Correction. PC - Lycée Thiers. TD 5: Les piles.

Corrigé de la série de TD N 03 de Structures de Données

Soit P une Pile représentée par une liste chaînée des villes de Boumerdès

Langage C : énoncé et corrigé des exercices IUP GéniE

1.5 PILEET FILE . Les exercices 1 à 1 6 20 à 2 5

Exercice 1 : piles et files

séance n°9 - corrigé. Exercice 1 : piles et files. Un système muti-tâches peut exécuter n o empiler une tâche (ajouter une tâche au sommet de la pile).

TD1.6 Simulation mutuelle : file pile

https://algo.gricad-pages.univ-grenoble-alpes.fr/L3I-S5-algo/TD1-6-corrige.pdf

Corrigé des exercices

Exercice 2. La première pile (la pile a) reçoit les éléments qu'on ajoute à la file. Lorsqu'on veut supprimer un élément de la file celui-ci est extrait de

2020 12 08 - DE EFREI 2A SDD P2024 Corrigé et consignes sujets

et fonctions pour manipuler des listes piles

Chapitre 1informatique commune

Corrigé des exercices

Exercice 1Lorsqu"on définit une pile à l"aide d"un tableau statique, on maintient un pointeur vers le première

case disponible du tableau, qui représente le sommet de la pile :123456 q classPile: définition d "unepile à l "aided "untableau """ def__init__(self, n): self.lst = [None]*n self.size = n self.q = 0 defempty(self): returnself.q == 0 deffull(self): returnself.q == self.size defpush(self, x): ifself.full(): raiseValueError("pilepleine ") self.lst[self.q] = x self.q += 1 defpop(self): ifself.empty(): raiseValueError("pilevide ") self.q= 1 returnself.lst[self.q]

Exercice 2

La première pile (la pilea) reçoit les éléments qu"on ajoute à la file. Lorsqu"on veut supprimer un

élément de la file, celui-ci est extrait de la pilebà moins que celle-ci ne soit vide, auquel cas les éléments de la

pileasont tout d"abord transférés dans la pileb.classFile:

Définition

d "unefile à l "aidede deux piles """ def__init__(self): self.a = Pile() self.b = Pile() defempty(self): returnself.a.empty()andself.b.empty() defadd(self, x): self.a.push(x) deftake(self): ifself.empty(): raiseValueError("filevide ")Jean-Pierre Becirspahic

1.2informatique communeifself.b.empty():

while not self.a.empty(): self.b.push(self.a.pop())

returnself.b.pop()Puisque la méthodeaddrevient à appliquer la méthodepushà la pilea, sont coût est unO(1). En revanche, le

coût de la méthodetakedépend de l"état de la pileb: si celle-ci n"est pas vide le coût est unO(1), si elle est

vide le coût est unO(n)(coût du transfert de la pileavers la pileb). Cependant on peut observer que le coût

amortide la méthodetakeest unO(1), car chaque élément de la file ne subit que trois opérations, toutes de

coût constant : ajout dans la pilea, transfert vers la pileb, suppression de la pileb.

Exercice 3

On empile les éléments dans celle des deux files qui est non vide (ou n"importe laquelle si les

deux sont vides); appelons-laa. Lorsqu"on veut dépiler un élément, on transfère les éléments de la fileavers la

fileb, à l"exception du dernier élément, qui est renvoyé.classPile: définition d "unepile à l "aidede deux files """ def__init__(self): self.a = File() self.b = File() defempty(self): returnself.a.empty()andself.b.empty() defpush(self, x): ifself.b.empty(): self.a.add(x) else: self.b.add(x) defpop(self): ifself.empty(): raiseValueError("listevide ") ifself.b.empty(): x = self.a.take() while not self.a.empty(): self.b.add(x) x = self.a.take() else: x = self.b.take() while not self.b.empty(): self.a.add(x) x = self.b.take() returnx

Le coût de la méthodepushest à l"évidence unO(1): on se contente d"insérer l"élément dans une des deux files.

En revanche, le coût de la méthodepopest systématiquement un(n), correspondant au transfert d"une file

vers l"autre. Exercice 4Commençons par définir le notion de cellule :classCell: définition d "unecellule avec deux pointeurs """ def__init__(self, x): self.val = x self.next = None self.pred = None

Les opérations d"ajout et de suppression dans une file doivent tenir compte du cas particulier de la file vide

(pour l"ajout) et de la file à un seul élément (pour la suppression).

Corrigé des exercices1.3classFile:

définition d "unefile par liste doublement chaînée """ def__init__(self): self.queue = None self.tete = None defempty(self): returnself.teteisNone defadd(self, x): c = Cell(x) ifself.empty(): self.tete = c else: c.next = self.queue self.queue.pred = c self.queue = c deftake(self): ifself.empty(): raiseValueError("filevide ") c = self.tete ifc.predisNone: self.tete = None self.queue = None else: self.tete = c.pred

returnc.valPour ajouter un élément, on crée une nouvelle cellule puis on modifie les pointeurs nécessaires pour préserver

la structure de liste doublement chaînée.

Pour supprimer un élément, on récupère la cellule en tête de liste puis là encore on modifie les pointeurs

nécessaires pour préserver la structure de liste doublement chaînée. Exercice 5Nous allons avoir besoin de la classeCelldéjà définie en cours :classCell: définition d "unecellule avec pointeur """ def__init__(self, x): self.val = x self.next= None

Une file est représentée par une liste circulaire dans laquelle chaque élément de la file pointe vers l"élément qui

le suit dans la file; quant à celle-ci, elle pointe vers son dernier élément. Par exemple, la filef= (1;2;3;4;5;6;7;8)

sera représentée en mémoire par le schema suivant :12 3 4 5 678f

Pour insérer un élément dans la file, il faut distinguer le cas où celle-ci est vide (il faut alors créer une cellule

qui pointe vers elle-même) ou non vide (il faut insérer une nouvelle cellule vers laquelle pointerafet modifier

certains pointeurs).

Jean-Pierre Becirspahic

1.4informatique communePour supprimer un élément de la file, il faut distinguer le cas où la file ne contient qu"un élément (elle deviendra

vide) et le cas où la file en contient plus d"un, auquel cas la cellule qui suit celle pointée parfsera supprimée et

un pointeur modifié.classFile: définition d "unefile par liste circulaire """ def__init__(self): self.lst = None defempty(self): returnself.lstisNone defadd(self, x): c = Cell(x) ifself.empty(): c.next= c else: c.next= self.lst.next self.lst.next= c self.lst = c deftake(self): ifself.empty(): raiseValueError("filevide ") ifself.lst.nextis self.lst: c = self.lst self.lst = None else: c = self.lst.next self.lst.next= c.next returnc.val

Exercice 6La fonction qui suit ne détecte pas d"éventuelles erreurs de syntaxe :defevalue(lst):

p = Pile() fortinlst: iftinop_bin: y = p.pop() x = p.pop() p.push(op_bin[t](x, y)) eliftinop_uni: x = p.pop() p.push(op_uni[t](x)) else: p.push(t) returnp.pop()

Nous allons maintenant détecter deux types d"erreurs de syntaxe : le cas où on cherche à dépiler une pile vide

(s"il manque d"opérande pour un opérateur unaire ou binaire) et le cas où à la fin de l"évaluation la pile contient

plus d"un élément. Ne seront pas détectées les erreurs liées à un opérateur de nom inconnu ou les erreurs

mathématiques (division par 0 par exemple).

Corrigé des exercices1.5defevalue2(lst):

p = Pile() fortinlst: iftinop_bin: ifp.empty(): raiseValueError("expressionincorrecte ") y = p.pop() ifp.empty(): raiseValueError("expressionincorrecte ") x = p.pop() p.push(op_bin[t](x, y)) eliftinop_uni: ifp.empty(): raiseValueError("expressionincorrecte ") x = p.pop() p.push(op_uni[t](x)) else: p.push(t) s = p.pop()quotesdbs_dbs20.pdfusesText_26

[PDF] Corrigé des exercices Exercice 2. La première

Chapitre 1informatique commune

Corrigé des exercices

Exercice 2

Définition

1.2informatique communeifself.b.empty():

Exercice 3

Corrigé des exercices1.3classFile:

Jean-Pierre Becirspahic

1.4informatique communePour supprimer un élément de la file, il faut distinguer le cas où la file ne contient qu"un élément (elle deviendra

Corrigé des exercices1.5defevalue2(lst):