Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

corrige pdf Chapitre informatique commune Corrigé des exercices ? Exercice ? Lorsqu ? on dé ?nit 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 q class P

Chapitre informatique commune Corrigé des exercices ? Exercice ? Lorsqu ? on dé ?nit 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 q class Pile dé ?nition d'une pile à l'aide d'un tableau def init self n self lst None n self size n self q def empty self return self q def full self return self q self size def push self x if self full raise ValueError pile pleine self lst self q x self q def pop self if self empty raise ValueError pile vide self q ?? return self lst self q ? Exercice ? La première pile la pile a reçoit les éléments qu ? on ajoute à la ?le Lorsqu ? on veut supprimer un élément de la ?le celui-ci est extrait de la pile b à moins que celle-ci ne soit vide auquel cas les éléments de la pile a sont tout d ? abord transférés dans la pile b class File Dé ?nition d'une ?le à l'aide de deux piles def init self self a Pile self b Pile def empty self return self a empty and self b empty def add self x self a push x def take self if self empty raise ValueError ?le vide Jean-Pierre Becirspahic C informatique commune if self b empty while not self a empty self b push self a pop return self b pop Puisque la méthode add revient à appliquer la méthode push à la pile a sont coût est un O En revanche le coût de la méthode take dépend de l ? état de la pile b si celle-ci n ? est pas vide le coût est un O si elle est vide le coût est un O n coût du transfert de la pile a vers la pile b Cependant on peut observer que le coût amorti de la méthode take est un O car chaque élément de la ?le ne subit que trois opérations toutes de coût constant ajout dans la pile a transfert vers la pile b suppression de la pile b ? Exercice ? On empile les éléments dans celle des deux ?les qui est non vide ou n ? importe laquelle si les deux sont vides appelons-la a Lorsqu ? on veut dépiler un élément on transfère les éléments de la ?le a vers la ?le b à l ? exception du dernier élément qui est renvoyé class Pile dé ?nition d'une pile à l'aide de deux ?les def init self self a File self b File def empty self return self a empty and self b empty def push self x if self b empty self a add x else self b add x def pop self if self empty raise ValueError liste vide if self b empty x self a take while not self a empty self b add x x self a