[PDF] Corrigé des exercices PDF 01.corrige.pdf

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 la pile b à

Ecrire un algorithme pour déplacer les entiers de P1 dans une pile P2 de fa`a§on 2 Files Exercice 4 5 Evaluer `a l'aide des primitives du type abstrait File de

[PDF] SUJET + CORRIGE

16 déc 2011 · UE : Algorithmes et structures de données Épreuve : Examen Exercice 1 (Files à l'aide de Piles (8 points)) Nous avons vu en cours une

[PDF] TD – Piles et files - PanaMaths

TD – Piles et files Corrigé Piles Exercice N°1 – Copie d'une pile Ecrire une Illustrons le principe général de l'algorithme à partir de l'exemple fourni dans

[PDF] Travaux Dirigés dalgorithmique no4

Exercice 1 problèmes suivants ; donner la complexité de chaque algorithme 1 Calculer le nombre Une pile est une structure de donnée qui enregistre des informations selon le mode dernier entré (Implantation d'une file par tableau)

[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 la pile b à

[PDF] Exercice 1 : Exercice sur la structure de données Pile Exercice 2

En supposant que les piles ont été implantées au moyen des listes python, On va dans cet exercice surtout implanter différents algorithmes classiques de tris Pour cela on a besoin d'une file contenant les vélos en cours de déplacement

[PDF] TD 5 & 6 : Structures de données abstraites

´Ecrire un algorithme récursif (et itératif) qui permet de fusionner deux listes Définir une structure pile `a l'aide d'un tableau d'éléments (de type element t) de element t defiler(file t file); qui retourne le premier élément apr`es l'avoir retiré de

[PDF] TP9: Listes chainées, files dattente, piles

Exercice 3 : Liste et pile ou comment gérer sa vaisselle sale ? 2 But listes chainées, vous devez être capable de gérer les structures de file et de pile Exercice 1 : file (2) Écrivez un algorithme permettant d'ajouter une pile d' assiettes

[PDF] Chapitre 4 : Piles et Files

Les piles et files ne sont pas de nouveaux types de données mais plutôt une manière de gérer un ensemble Dans les exercices avec piles et files il est suffit de faire appel aux sous algorithmes de base définis vous voulez les faire corriger

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):quotesdbs_dbs2.pdfusesText_3

[PDF] [PDF] Corrigé des exercices

[PDF] Algorithmique et Structures de données 1 Piles - LaBRI