Les structures de pile et de file permettent toutes deux de stocker des ensembles d'objets et fournissent des opérations permettant d'ajouter ou de retirer des objets un à un.
Les éléments retirés ne sont cependant, ni dans une structure ni dans l'autre, retirés dans un ordre arbitraire, et chacune de ces structures à sa règle.
Dans une pile (en anglais stack), chaque opération de retrait retire l'élément arrivé le plus récemment.
On associe cette structure à l'image d'une pile d'assiettes, dans laquelle chaque nouvelle assiette est ajoutée au-dessus des précédentes, et où l'assiette retirée est systématiquement celle du sommet.
![\"pile_file.png](\"https://sciencesappliquees.com/images/nsi/pile_file.png\")
Cette discipline est nommée dernier entré, premier sorti (DEPS), ou plus couramment en anglais LIFO (last in, first out).
Dans une structure de file en revanche (en anglais queue), chaque opération de retrait retire l'élément qui avait été ajouté le premier.
On associe cette structure à l'image d'une file d'attente, dans laquelle des personnes arrivent à tour de rôle, patientent, et sont servies dans leur ordre d'arrivée.
![\"pile_file1.png](\"https://sciencesappliquees.com/images/nsi/pile_file1.png\")
Cette discipline est nommée premier entré, premier sorti (PEPS), ou plus couramment en anglais FIFO (first in, first out).
Classiquement, chacune de ces deux structures à une interface proposant au minimum les quatre opérations suivantes :
- créer une structure initialement vide,
- tester si une structure est vide,
- ajouter un élément à une structure,
- retirer et obtenir un élément d'une structure.
De même qu'on la déjà préconisé pour les tableaux et les listes chaînées, on s'attend à ce que les piles ct les files soient des structures homogènes, c'est-à-dire que tous les éléments stockés aient le même type.
Et évidemment, l'opération de retrait suit la discipline correspondant à la structure concernée.
Le plus souvent, les structures de pile et de file sont également considérées mutables : chaque opération
d'ajout ou de retrait d'un élément modifie la pile ou la file à laquelle elle s'applique.
Enfin, sauf mention contraire explicite, il n'y a pas de limite de principe au nombre d'éléments qui peuvent être accueillis dans une pile ou une file :
il est toujours possible d'en ajouter un nouveau.
En plus des opérations minimales déjà citées, les interfaces des piles ou des files ajoutent souvent d'autres opérations facilitant leur manipulation.
Par exemple :
- connaître le nombre d'éléments contenus dans une structure,
- vider une structure,
- consulter un élément d'une structure (celui qu'on aurait obtenu avec l'opération de retrait) sans le retirer,
- etc.
Dans ce chapitre, nous allons voir dans un premier temps les interfaces des structures de pile et de file et des exemples d'utilisation.
Ensuite, nous détaillerons plusieurs manières de réaliser ces structures.
Pour exprimer l'interface des piles, nous notons Pile[T] le type des piles contenant des éléments de type T.
L'opération est_vide, qui prend en paramètre une pile et renvoie un booléen indiquant la vacuité de la pile, a
donc le type suivant.
est_vide(Pile[T]) -> bool
À l'inverse, l'opération creer_pile de création d'une pile vide ne prend aucun paramètre et renvoie une nouvelle pile.
creer_pile() -> Pile[T]
On remarque que le type T des éléments de la pile ainsi créée ne peut pas être déduit des paramètres inexistants. Il faut simplement comprendre de cette définition que l'opération de création peut fournir une pile accueillant des éléments de n'importe quel type T.
Notez que cela ne signifie pas que chaque élément puisse avoir n'importe quel type.
En effet, ce type T, bien qu'arbitraire, reste valable pour toute la pile.
L'opération d'ajout d'un élément au sommet d'une pile est traditionnellement appelée empiler (ou push en anglais).
Elle prend en paramètres une pile et l'élément à ajouter, d'un type homogène avec celui des éléments de la pile.
Cette opération ne produit pas de résultat.
empiler(PilefTi, T) -> None
Inversement, l'opération de retrait de l'élément au sommet d'une pile est appelée depiler (ou pop en anglais). Elle prend en paramètre la pile et renvoie l'élément qui en a été retiré.
depiler(Pile[T}) -> T
Cette dernière opération suppose que la pile est non vide et lèvera une exception dans le cas contraire.
| fonction | description |
| Pile[T] "}\" style=\"border-width: 1px; border-style: solid; border-color: rgb(204, 204, 204) rgb(0, 0, 0) rgb(0, 0, 0); border-image: initial; overflow: hidden; padding: 2px 3px; vertical-align: bottom; font-family: Roboto; font-size: 12pt; text-align: center;\">creer_pile() -> Pile[T] | crée une pile vide |
| bool "}\" style=\"border-width: 1px; border-style: solid; border-color: rgb(204, 204, 204) rgb(0, 0, 0) rgb(0, 0, 0); border-image: initial; overflow: hidden; padding: 2px 3px; vertical-align: bottom; font-family: Roboto; font-size: 12pt; text-align: center;\">est_vide(p: Pile[T]) -> bool | renvoie True si p est vide et False sinon |
| None"}\" style=\"border-width: 1px; border-style: solid; border-color: rgb(204, 204, 204) rgb(0, 0, 0) rgb(0, 0, 0); border-image: initial; overflow: hidden; padding: 2px 3px; vertical-align: bottom; font-family: Roboto; font-size: 12pt; text-align: center;\">empiler(p: Pile[T], e: T) -> None | ajoute e au sommet de p |
| T "}\" style=\"border-width: 1px; border-style: solid; border-color: rgb(204, 204, 204) rgb(0, 0, 0) rgb(0, 0, 0); border-image: initial; overflow: hidden; padding: 2px 3px; vertical-align: bottom; font-family: Roboto; font-size: 12pt; text-align: center;\">depiler(p: Pile[T]) ->T | retire et renvoie l'élément au sommet de p |
Notez que dans la suite nous montrerons des utilisations de cette interface où les opérations sont réalisées par des fonctions ordinaires, mais aussi des
utilisations supposant que la structure de pile est réalisée par une classe dont les opérations est_vide, empiler et depiler sont des méthodes.
L'ajout de l'élément e au sommet de la pile p s'écrira donc empiler(p, e) dans le premier cas et p.empiler(e) dans le second.
Mettre le résultat ici (code et figure).
Considérons un navigateur web dans lequel on s'intéresse à deux opérations : aller à une nouvelle page et revenir à la page précédente.
On veut que le bouton de retour en arrière permette de remonter une à une les pages précédentes, et ce jusqu'au début de la navigation.
En plus de l'adresse courante, qui peut être stockée dans une variable à part, il nous faut donc conserver l'ensemble des pages précédentes auxquelles il est possible de revenir.
Puisque le retour en arrière se fait vers la dernière
page qui a été quittée, la discipline « dernier entré, premier sorti » des piles est exactement ce dont nous avons besoin pour cet ensemble.
adresse_courante = “\"
adresses_precedentes = creer_pile()
Ainsi, lorsque l'on navigue vers une nouvelle page, l'adresse de la page courante peut être ajoutée au sommet de la pile des pages précédentes avec l'opération empiler.
l'adresse cible donnée en paramètre peut alors être
enregistrée comme nouvelle adresse courante.
def aller_a(adresse_ cible):
empiler(adresses_precedentes , adresse_courante)
adresse_courante = adresse_cible
Lorsque l'on veut revenir en arrière, il suffit alors de revenir à la dernière page enregistrée sur la pile.
Ici, en outre, on vérifie au préalable qu'il existe bien une page précédente et on ne fait rien si ce n'est pas le cas.
def retour():
if not est_vide(adresses_precedentes):
adresse_courante = depiler(adresses_precedentes)
Le programme ci-dessous redonne l'ensemble de cet exemple, en utilisant cette fois la notation des classes et des appels de méthodes.
Attention, il faut importer le module modPile.py et le mettre où se trouve votre programme.
Programme — Navigation
from modPile import Pile
class Navigation:
\"\"\"Gere la navigation du navigateur\"\"\"
def __init__(self):
self.adresse_courante = \"\"
self.adresses_precedentes = Pile()
def aller_a(self,adresse_cible):
self.adresses_precedentes.empiler(self.adresse_courante)
self.adresse_courante = adresse_cible
def retour(self):
if not self.adresses_precedentes.est_vide():
self.adresse_courante = self.adresses_precedentes.depiler()
def naviguer(self):
while True :
adresse = input(\"Adresse ou < :\")
if adresse == \"<\" :
self.retour()
else :
self.aller_a(adresse)
print(\"Page :\",self.adresse_courante)
Tester avec :
#Lancer la navigation
nav = Navigation()
#lancer la navigation
nav.naviguer()
On a parlé dans certaines séquences d'une « pile d'appels » existant à tout moment de l'exécution d'un programme et contenant, à chaque instant, les informations relatives à tous les appels de fonctions emboîtés en cours d'exécution.
Ce nom correspond bien à la structure d'une pile au sens que nous décrivons dans cette séquence.
En effet, lorsqu'une exécution d'une fonction f déclenche elle-même un appel à une autre fonction g (ou récursivement à la même fonction), la progression dans le code de f est suspendue jusqu'à obtention du
résultat de l'appel à g.
L'appel à f ne peut donc se conclure et disparaître
de la pile d'appels qu'après que l'appel à g est lui-même terminé. Dit autrement, le premier appel à quitter la pile d'appels est le dernier qui y est entré.
Ceci tient à la propriété des appels de fonctions d'être bien emboîtés.
Pour exprimer l'interface des files, nous notons File[T] le type des files contenant des éléments de type T.
Ceci étant fixé, l'interface des files, donnée par l'interface 2, est similaire à celle des piles.
L'opération d'ajout sera simplement appelée ajouter (elle est parfois appelée enfiler, ou en anglais enqueue) et l'opération de retrait retirer (parfois défiler, ou en anglais dequeue).
Interface 3 — File d'étéments de type T
| fonction | description |
| Pile[T] "}\" style=\"padding: 2px 3px; border-width: 1px; border-style: solid; border-color: rgb(204, 204, 204) rgb(0, 0, 0) rgb(0, 0, 0); border-image: initial; overflow: hidden; vertical-align: bottom; font-family: Roboto; font-size: 12pt; text-align: center;\">creer_file() -> File[T] | crée une file vide |
| bool "}\" style=\"padding: 2px 3px; border-width: 1px; border-style: solid; border-color: rgb(204, 204, 204) rgb(0, 0, 0) rgb(0, 0, 0); border-image: initial; overflow: hidden; vertical-align: bottom; font-family: Roboto; font-size: 12pt; text-align: center;\">est_vide(f: File[T]) -> bool | renvoie True si f est vide et False sinon |
| None"}\" style=\"padding: 2px 3px; border-width: 1px; border-style: solid; border-color: rgb(204, 204, 204) rgb(0, 0, 0) rgb(0, 0, 0); border-image: initial; overflow: hidden; vertical-align: bottom; font-family: Roboto; font-size: 12pt; text-align: center;\">ajouter(f: File[T], e: T) -> None | ajoute e à l'arrière de f |
| T "}\" style=\"padding: 2px 3px; border-width: 1px; border-style: solid; border-color: rgb(204, 204, 204) rgb(0, 0, 0) rgb(0, 0, 0); border-image: initial; overflow: hidden; vertical-align: bottom; font-family: Roboto; font-size: 12pt; text-align: center;\">retirer(f: File[T]) ->T | retire et renvoie l'élément à l'avant de f |
Considérons le jeu de cartes de la bataille. Chaque joueur possède un paquet de cartes et pose à chaque manche la carte prise sur le dessus du paquet.
Le vainqueur de la manche récupère alors les cartes posées, pour les placer au-dessous de son paquet.
En plus des cartes posées au centre de la table, dont on discutera le traitement plus bas, nous avons besoin de conserver en mémoire le paquet de cartes de chaque joueur. Puisque les cartes sont remises dans un paquet à une extrémité et prélevées à l'autre, la discipline « premier entré, premier sorti » des files est exactement ce dont nous avons besoin pour chacun de
ces ensembles.
En supposant que les joueurs s'appellent Alice et Basile, nous pouvons donc créer ainsi deux paquets de cartes.
paquet_alice = File()
paquet_basile = File()
Une opération de distribution des cartes peut ensuite placer dans ces deux paquets les cartes de départ de chacun des joueurs.
#crée le jeu de 52 cartes
cartes = [i for i in range(0,52)]
#melange les cartes
random.shuffle(cartes)
#distribue les cartes aux 2 joueurs
for i in range(len(cartes)//2) :
paquet_alice.ajouter(cartes.pop())
paquet_basile.ajouter(cartes.pop())
Regardons maintenant quelques aspects de la réalisation d'un tour de jeu. Au moment de démarrer un tour, un joueur perd s'il n'a plus de cartes dans son paquet.
def tour():
global en_cours
if paquet_alice.est_vide():
print(\"Alice perd\")
en_cours = False
elif paquet_basile.est_vide():
print(\"Basile perd\")
en_cours = False
else :
tirer()
Si Ia partie n'est pas terminée, le jeu demande alors à chaque joueur de tirer sa première carte. Il s'agit de prélever la première carte du paquet de chaque joueur, avec l'opération defiler.
def joue():
a = paquet_alice.retirer()
b = paquet_basile.retirer()
valeura = a%13
valeurb = b%13
Remarque : modulo 13 (%13), car il y 13 cartes par couleur (pique, carreau, trèfle, coeur).
Si l'un des joueurs gagne ce tour, on peut alors remettre ces deux cartes au fond de son paquet, c'est-à-dire à l'arrière de sa file de carte, avec l'opération
enfiler.
print(\"Alice\",valeura,valeurb,\"Basile\")
#le programme ne gere pas l'égalité
if valeura > valeurb :
paquet_alice.ajouter(a)
paquet_alice.ajouter(b)
elif valeura < valeurb :
paquet_basile.ajouter(b)
paquet_basile.ajouter(a)
Sans présumer de la manière dont sont représentées les cartes, on suppose ici disposer d'une fonction valeur permettant une comparaison.
Vous terminerez en exercice ce jeu. Vous aurez à gérer d'une part la valeur des cartes et d'autre part les cas d'égalités.
Le programme partiel du jeu de bataille est le suivant :
from modFile import File
import random
paquet_alice = File()
paquet_basile = File()
#crée le jeu de 52 cartes
cartes = [i for i in range(0,52)]
#melange les cartes
random.shuffle(cartes)
#distribue les cartes aux 2 joueurs
for i in range(len(cartes)//2) :
paquet_alice.ajouter(cartes.pop())
paquet_basile.ajouter(cartes.pop())
#Gestion d'un tour de jeu
def tour():
global en_cours
if paquet_alice.est_vide():
print(\"Alice perd\")
en_cours = False
elif paquet_basile.est_vide():
print(\"Basile perd\")
en_cours = False
else :
tirer()
#Si la partie n'est pas terminée, tirage d'une carte
def tirer():
a = paquet_alice.retirer()
b = paquet_basile.retirer()
valeura = a%13
valeurb = b%13
print(\"Alice\",valeura,valeurb,\"Basile\")
#le programme ne gere pas l'égalité
if valeura > valeurb :
paquet_alice.ajouter(a)
paquet_alice.ajouter(b)
elif valeura < valeurb :
paquet_basile.ajouter(b)
paquet_basile.ajouter(a)
#démarrage du jeu
en_cours = True
nb_tours = 0
while en_cours :#not paquet_alice.est_vide() and not paquet_basile.est_vide() :
tour()
nb_tours+=1
print(\"Partie en \",nb_tours,\" tours\")
Importer le module modFile.py :
https://sciencesappliquees.com/images/nsi/modFile.py
et tester le jeu de carte de la bataille.
Conclure sur le role de la classe File.
Mettre le résultat ici.
La structure de liste chaînée donne une manière élémentaire de réaliser une pile.
Empiler un nouvel élément revient à ajouter une nouvelle cellule en tête de liste, tandis que dépiler un élément revient à supprimer la cellule de tête.
Où peut ainsi construire une classe Pile définie par un unique attribut contenu associé à l'ensemble des éléments de la pile, stockés sous la forme d'une liste chaînée.
class Pile:
Le constructeur Pile(), défini par la méthode __init__ (self), construit une pile vide en définissant contenu comme la liste vide.
On rappelle que la liste chaînée vide est simplement représentée par la valeur None.
def __init__(self):
self.contenu = None
Ainsi, tester la vacuité d'une pile revient simplement à tester si son contenu
est la liste vide.
def est_vide(self):
return self.contenu is None
On empile un nouvel élément en ajoutant une nouvelle cellule devant celles que contient déjà notre liste chaînée. On peut réaliser cela en construisant
une nouvelle liste chaînée dont la première cellule contient :
- comme valeur l'élément que l'on souhaite empiler,
- comme cellule suivante la première cellule de la liste d'origine, c'est-à- dire self.contenu.
On écrit donc :
def empiler(self, v):
c = Cellule(v, self.contenu)
Ne reste alors qu'à définir cette nouvelle liste chaînée comme le nouveau contenu de notre pile.
self.contenu = c
Récupérer la valeur au sommet de la pile consiste alors à consulter la valeur de la première cellule, en supposant que cette première cellule existe, autrement dit en supposant que la pile n'est pas vide.
def depiler(self):
if self.est_vide():
raise IndexError(\"depiler sur une pile vide\")
v = self.contenu.valeur
On complète l'opération de dépilement en retirant le premier élément, c'est-à-dire en redéfinissant le contenu de notre pile comme la liste d'origine
privée de sa première cellule. Autrement dit, la nouvelle cellule de tête est la cellule suivante de la cellule supprimée.
Après cette mise à jour, on peut renvoyer la valeur qui avait été prélevée dans la cellule de tête d'origine.
self.contenu = self.contenu.suivante
return v
Le programme ci-dessous regroupe tous ces éléments pour donner une mise en œuvre complète de la structure de pile à l'aide d'une liste chaînée.
Programme — Réalisation d'une pile avec une liste chaînée
class Cellule:
\"\"\"une cellule d'une liste chaînée\"\"\"
def __init__(self, v, s):
self.valeur = v
self.suivante = s
class Pile:
\"\"\"structure de pite\"\"\"
def __init__(self):
self.contenu = None
def est_vide(self):
return self.contenu is None
def empiler(self, v):
self.contenu = Cellule(v, self.contenu)
def depiler(self):
if self.est_vide():
raise IndexError(\"depiler sur une pile vide\")
v = self.contenu.valeur
self.contenu = self.contenu.suivante
return v
def creer_pile():
return Pile()
Tester la création d'une pile avec les instructions suivantes :
p = Pile()
#ou p = creer_pile()
print(\"p est vide?\",p.est_vide())
p.empiler(1)
p.empiler(2)
p.empiler(3)
p.empiler(4)
print(\"p est vide ?\",p.est_vide())
print(\"retire le 1er element :\",p.depiler())
Décrire les instructions ci-dessous et dessiner la pile à la fin des instructions.
Mettre le résultat ici (code et figure).
. Les tableaux de Python réalisent également
directement une structure de pile, avec leurs opérations append et pop.
On pourrait donc donner une définition en apparence très simple à une autre version de la classe Pile.
class PileTab:
\"\"\"structure de pile avec tableau\"\"\"
def __init__(self):
self.contenu = []
def est_vide(self):
return len(self.contenu) == 0
def empiler(self, v):
self.contenu.append(v)
def depiler(self):
if self.est_vide():
raise IndexError(\"depiler sur une pile vide\")
return self.contenu.pop()
Dans le cadre d'un programme Python, cette réalisation est raisonnable et efficace, les opérations append et pop s'exécutant en moyenne en temps constant. Cette solution, cependant, ne s'exporte pas directement
à n'importe quel autre langage, puisqu'elle cache la richesse de la structure de tableau redimensionnable utilisée par les tableaux de Python.
Tester PileTab avec les instruction suivante et conclure par rapport au Pile précédent :
p = PileTab()
print(\"p est vide?\",p.est_vide())
p.empiler(1)
p.empiler(2)
p.empiler(3)
p.empiler(4)
print(\"p est vide ?\",p.est_vide())
print(\"affiche 1er element :\",p.depiler())
Mettre le résultat ici (code et figure).
La structure de liste chaînée donne également une manière de réaliser une file, à condition de considérer la variante des listes chaînées mutables.
Comme dans la réalisation d'une pile, on peut retirer l'élément de tête en retirant la cellule de tête.
En revanche, l'ajout d'un nouvel élément à l'arrière de la file revient à ajouter une nouvelle cellule en queue de liste.
Une mutation intervient à cet endroit :
alors que la cellule qui était la dernière de la liste chaînée avant l'ajout n'avait pas de suivante définie, elle a comme suivante après l'ajout la nouvelle cellule créée pour le nouvel élément.
Autre différence avec la réalisation d'une pile, nous avons maintenant besoin de savoir accéder à la dernière cellule et plus seulement à la première. Il est possible, mais pas raisonnable, de trouver la dernière cellule en parcourant toute la liste chaînée à partir de la première cellule.
Il est plus intéressant de conserver dans notre structure
de données un attribut permettant d'accéder directement à cette dernière cellule.
On peut ainsi construire une classe File dont le constructeur définit deux attributs, l'un appelé tete et l'autre appelé queue, et désignant respectivement la première cellule et la dernière cellule de la liste chaînée utilisée pour stocker les éléments.
class File:
def __init__(self):
self.tete = None
self.queue = None
La file vide est caractérisée par le fait qu'elle ne contient aucune cellule.
En conséquence, sa tête et sa queue sont indéfinies.
En outre, l'une comme l'autre ne peut valoir None que dans ce cas. Pour tester la vacuité de la file, il suffit donc de consulter l'un des deux attributs.
def est_vide(self):
return self.tete îs None
L'ajout d'un nouvel élément à l'arrière de la file demande de créer une nouvelle cellule. Cette cellule prend la dernière place, et n'a donc pas de cellule
suivante :
def ajouter(self, x):
c = Cellule(x, None)
Cette cellule est alors définie comme suivant la cellule de queue actuelle. On a cependant besoin de traiter le cas particulier où il n'existe pas de cellule de queue, qui correspond à une file initialement vide.
Dans ce cas la nouvelle cellule devient l'unique cellule de la file, et donc sa cellule de tête.
if self.est_vide():
self.tete = c
else:
self.queue.suivante = c
Dans tous les cas, notre nouvelle cellule devient en outre la nouvelle cellule de queue de la file .
self.queue = c
Pour retirer un élément il s'agit de supprimer la première cellule de la file, exactement comme il avait été fait lors de l'utilisation d'une liste chaînée pour réaliser une pile.
Cependant, si la cellule retirée est la dernière, on doit également redéfinir l'attribut self.queue à None, afin de maintenir notre invariant qu'une file vide à ses deux attributs qui valent None.
Le programme ci-dessous montre l'intégralité du code de la classe File que nous venons de décrire.
Programme — Réalisation d'une file avec une tiste chaînée mutable
class File:
\"\"\"structure de file\"\"\"
def __init__(self):
self.tete = None
self.queue = None
def est_vide(self):
return self.tete is None
def ajouter(self, x):
c = Cellule(x, None)
if self.est_vide():
self.tete = c
else:
self.queue.suivante = c
self.queue = c
def retirer(self):
if self.est_vide():
raise IndexError(\"retirer sur une file vide\")
v = self.tete.valeur
self.tete = self.tete.suivante
if self.tete is None:
self.queue = None
return v
Tester la création d'une file avec les instructions suivantes :
f = File()
print(\"f est vide?\",f.est_vide())
f.ajouter(1)
f.ajouter(2)
f.ajouter(3)
f.ajouter(4)
print(\"f est vide ?\",f.est_vide())
print(\"retire 1er element :\",f.retirer())
Décrire les instructions ci-dessous et dessiner la file à la fin des instructions.
Mettre le résultat ici (code et figure).
La réalisation d'une file donnée par le programme précédent impose une représentation unique de la file
vide, où les deux attributs se1f.tete et self .queue valent None.
Cela peut simplifier la réflexion sur la structure, mais impose de prendre des précautions en programmant, notamment en incluant les deux lignes
if self.tete fs None:
self.queue = None
dans la fonction retirer pour s'assurer que lorsque l'on rend la file vide, les deux attributs sont bien annulés.
On peut cependant s'autoriser un peu plus de souplesse, et décider que n'importe quelle file dont l'attribut self.tete vaut None est une file vide, sans tenir compte de la valeur de self.queue.
Cela simplifie l'écriture de toute fonction susceptible de vider la file, et on pourra par exemple simplifier le code de retirer de la manière suivante.
def retirer(self):
if self.est_vide():
raise IndexError(\"retirer sur une file vide\")
v = self.tete.valeur
self.tete = self.tete.suivante
return v
En revanche cela pose aussi de nouvelles contraintes :
le test de vacuité
ne doit être fait qu'en fonction de l'attribut self.tete, et surtout il ne faut jamais travailler avec l'attribut self.queue d'une file dont la tête vaudrait None, car la valeur de la queue n'a aucune signification dans ce cas.
","title":"Représentation plus souple de la file vide"},{"edit":"Une réalisation radicalement différente de cette même structure de file consiste à utiliser deux piles, ou directement deux listes chaînées immuables.
On prend pour cela modèle sur un jeu de cartes où l'on disposerait d'une pioche, au sommet de laquelle on prend des cartes (disposées face cachée), et d'une défausse, au sommet de laquelle on en repose (disposées face visible)
Chacun de ces deux paquets de cartes est une pile, et ces deux paquets forment ensemble la réserve de cartes.
On a ensuite la discipline suivante :
- toute carte prise dans la réserve est retirée dans l'une de ces piles (la pioche),
- toute carte remise dans la réserve est ajoutée à l'autre pile (la défausse)
S'ajoute un mécanisme liant les deux paquets : une fois la pioche vide on retourne la défausse pour en faire une nouvelle pioche, laissant à la place une défausse vide.
Cette gestion des cartes correspond à une structure de file : une fois la pioche initiale vidée, les cartes seront piochées précisément dans l'ordre dans lequel elles ont été défaussées.
La première défaussée sera la première piochée (FIFO).
On peut donc définir une nouvelle version de la classe File utilisant ce principe.
Une file réalisée ainsi est caractérisée par deux attributs entree et sortie, le premier contenant une pile dans laquelle on ajoute les nouveaux éléments et le second une pile d'où l'on prend les éléments retirés.
class File:
def __init__ (self):
self.entree = creer _pile()
self.sortie = creer _pile()
Une file est vide lorsque ces deux piles sont toutes deux vides.
def est_vide(self):
return self.entree.est_vide() \\
and self.sortie.est_vide()
Ajouter un nouvel élément consiste simplement à empiler cet élément sur la pile d'entrée.
def ajouter(self, x):
self .entree .empiler(x)
Retirer un élément est l'opération la plus délicate. Dans le cas simple où la pile de sortie n'est pas vide, il suffit de dépiler son premier élément.
Dans le cas où la pile de sortie est vide, en revanche, il faut au préalable retourner la pile d'entrée pour la mettre à la place de la pile de sortie.
On peut réaliser cette opération intermédiaire en transférant un à un tous les éléments de la pile d'entrée sur la pile de sortie.
En effet, le premier élément prélevé sur la pile d'entrée est le dernier entrant (discipline FIFO de la pile utilisée), c'est-à-dire celui qui devra sortir de la file après tous les autres (discipline FIFO de la file que l'on veut réaliser}, et il sortira bien le dernier puisqu'il sera
ajouté le premier sur la pile de sortie (discipline FIFO de la pile utilisée).
def retirer(self):
if self .sortie.est_vide():
while not self.entree.est_vide():
self.sortie.empiler(self.entree.depiler())
On peut alors maintenant dépiler le premier élément de la nouvelle pile de sortie, qui, s'il y a eu retournement, était auparavant le dernier élément de la pile d'entrée, à moins que cette pile soit encore vide (ce qui signifierait
que les deux piles étaient vide, et donc la file également).
if self.sortie.est_vide():
raise IndexError(\"retirer sur une file vide\")
return self.sortie.depiler()
Le programme ci-dessous contient l'intégralité de cette nouvelle réalisation des fles.
Programme — Réalisation d'une file avec deux piles
class File2Piles:
\"\"\"structure de fite\"\"\"
def __init__(self):
self.entree = creer_pile()
self.sortie = creer_pile()
def est_vide(self):
return self.entree.est_vide() \\
and self.sortie.est_vide()
def ajouter(self, x):
self.entree.empiler(x)
def retirer(self):
if self.sortie.est_vide():
while not self.entree.est_vide():
self.sortie.empiler(self.entree.depiler())
if self.sortie.est_vide():
raise IndexError(\"retirer sur une file vide\")
return self.sortie.depiler()
Tester la création d'une file avec les instructions suivantes :
f = File2Piles()
print(\"f est vide?\",f.est_vide())
f.ajouter(1)
f.ajouter(2)
f.ajouter(3)
f.ajouter(4)
print(\"f est vide ?\",f.est_vide())
print(\"retire 1er element :\",f.retirer())
Décrire les instructions ci-dessous et dessiner la file à la fin des instructions.
Mettre le résultat ici (code et figure).
La pile est une structure de données de type « dernier entré, premier sorti ». Elle peut être réalisée avec une
liste chaînée ou avec un tableau Python.
La file est une structure de données de type « premier entré, premier sorti ». Elle peut être réalisée avec une liste chaînée mutable ou encore avec deux piles.
","title":"Conclusion","tagtitle":"h1"},{"edit":"Compléter la classe Pile avec les trois méthodes suivantes :
- consulter : retourne la valeur de l'élement en haut de la pile;
- taille : donne le nombre d'éléments dans la pile.
- vider : vide la pilz.
class Cellule:
\"\"\"une cellule d'une liste chaînée\"\"\"
def __init__(self, v, s):
self.valeur = v
self.suivante = s
class Pile:
\"\"\"structure de pite\"\"\"
def __init__(self):
self.contenu = None
def est_vide(self):
return self.contenu is None
def empiler(self, v):
self.contenu = Cellule(v, self.contenu)
def depiler(self):
if self.est_vide():
raise IndexError(\"depiler sur une pile vide\")
v = self.contenu.valeur
self.contenu = self.contenu.suivante
return v
Quel est l'ordre de grandeur du nombre d'opérations effectuées par la fonction taille ?
Tester avec :
p = Pile()
p.empiler(1)
p.empiler(2)
print(p.consulter())
p.empiler(3)
p.empiler(4)
p.empiler(5)
p.empiler(6)
print(p.taille())
p.vider()
print(p.consulter())
print(p.taille())
Résultat :
2
6
La pile est vide
0
Mettre le résultat ici (code et figure).
La consultation de l’élément au sommet est similaire
à l'opération depiler, mais ne modifie pas le contenu.
def consulter(self):
if self.est_vide():
return \"La pile est vide\"
#raise IndexError(\"consulter sur une pile vide\")
return self.contenu.valeur
On peut vider la pile en redéfinissant le contenu comme la liste vide.
def vider(self):
self.contenu = None
Le calcul de la taille peut se faire à l’aide d’une fonction calculant la longueur d’une liste.
Le coût de cette opération est proportionnel à la longueur de la liste, c’est-à-dire ici au nombre d'éléments que contient la pile.
def taille(self):
return self.longueur(self.contenu)
def longueur(self,liste) :
if liste is None :
return 0
elif liste.suivante is None :
return 1
else :
return 1 + self.longueur(liste.suivante)
On souhaite compléter le programme navigation pour avoir également une fonction retour_avant dont le comportement est le suivant :
- chaque appel à la fonction retour place la page quittée au sommet d'une deuxième pile adresses_suivantes,
- un appel à la fonction retour_avant amène à la page enregistrée au sommet de la pile adresses_suivantes, et met à jour les deux piles de manière adaptée,
- toute nouvelle navigation avec aller_a annule les adresses suivantes.
Programme — Navigation
class Navigation:
\"\"\"Gere la navigation du navigateur\"\"\"
def __init__(self):
self.adresse_courante = \"\"
self.adresses_precedentes = Pile()
def aller_a(self,adresse_cible):
self.adresses_precedentes.empiler(self.adresse_courante)
self.adresse_courante = adresse_cible
def retour(self):
if not self.adresses_precedentes.est_vide():
self.adresse_courante = self.adresses_precedentes.depiler()
def naviguer(self):
while True :
adresse = input(\"Adresse ou < :\")
if adresse == \"<\" :
self.retour()
else :
self.aller_a(adresse)
print(\"Page :\",self.adresse_courante)
#Lancer la navigation
nav = Navigation()
#lancer la navigation
nav.naviguer()
Modifier et compléter le programme pour définir cette nouvelle fonction.
Remarque : On utilisera la touche \">\" pour naviquer vers l'avant.
","title":"Exercice","tagtitle":"h1"},{"edit":"Mettre le résultat ici (code et figure).
L'initialisation demande de créer une nouvelle pile, vide à l’origine.
def __init__(self):
self.adresse_courante = \"\"
self.adresses_precedentes = Pile()
self.adresses_suivantes = Pile()
La fonction de navigation principale annule les adresses suivantes en vidant la pile correspondante.
def aller_a(self,adresse_cible):
self.adresses_suivantes.vider()
self.adresses_precedentes.empiler(self.adresse_courante)
self.adresse_courante = adresse_cible
Chaque retour en arrière ajoute l’adresse courante à la pile des adresses suivantes, avant de revenir effectivement à la dernière adresse précédente connue.
def retour(self):
if not self.adresses_precedentes.est_vide():
self.adresses_suivantes.empiler(self.adresse_courante)
self.adresse_courante = self.adresses_precedentes.depiler()
Symétriquement, retour_avant va à la première adresse suivante, après avoir remis la page courante sur la pile des adresses précédentes.
def retour_avant(self):
if not self.adresses_suivantes.est_vide():
self.adresses_precedentes.empiler(self.adresse_courante)
self.adresse_courante = self.adresses_suivantes.depiler()
def naviguer(self):
while True :
adresse = input(\"Adresse , < ou > :\")
if adresse == \"<\" :
self.retour()
elif adresse == \">\" :
self.retour_avant()
else :
self.aller_a(adresse)
print(\"Page :\",self.adresse_courante)
Pour éviter le problème du calcul de taille à l'exercice sur la pile, on propose de revisiter la classe Pile en lui ajoutant un attribut taille, indiquant à tout moment la taille de la pile.
Quelles méthodes doivent être modifiées, et comment?
Programme - La classe pile
class Pile:
\"\"\"structure de pite\"\"\"
def __init__(self):
self.contenu = None
def est_vide(self):
return self.contenu is None
def empiler(self, v):
self.contenu = Cellule(v, self.contenu)
def depiler(self):
if self.est_vide():
raise IndexError(\"depiler sur une pile vide\")
v = self.contenu.valeur
self.contenu = self.contenu.suivante
return v
def consulter(self):
if self.est_vide():
return \"La pile est vide\"
#raise IndexError(\"consulter sur une pile vide\")
return self.contenu.valeur
def vider(self):
self.contenu = None
def taille(self):
return self.longueur(self.contenu)
def longueur(self,liste) :
if liste is None :
return 0
elif liste.suivante is None :
return 1
else :
return 1 + self.longueur(liste.suivante)
Tester avec :
p = Pile()
p.empiler(1)
p.empiler(2)
print(p.consulter())
p.empiler(3)
p.empiler(4)
p.empiler(5)
p.empiler(6)
print(p.taille)
p.vider()
print(p.consulter())
print(p.taille)
Résultat :
2
6
La pile est vide
0
Mettre le résultat ici (code et figure).
On modifie le constructeur pour initialiser ce nouvel
attribut _taille à zéro, puis les deux opérations empiler et depiler pour que chacune mette à jour cet attribut en lui ajoutant ou retirant un.
Ainsi la valeur reste en permanence à jour
class Pile:
\"\"\"structure de pite\"\"\"
def __init__(self):
self.contenu = None
self.taille = 0
def est_vide(self):
return self.contenu is None
def empiler(self, v):
self.contenu = Cellule(v, self.contenu)
self.taille += 1
def depiler(self):
if self.est_vide():
raise IndexError(\"depiler sur une pile vide\")
v = self.contenu.valeur
self.contenu = self.contenu.suivante
self.taille -= 1
return v
def consulter(self):
if self.est_vide():
return \"La pile est vide\"
#raise IndexError(\"consulter sur une pile vide\")
return self.contenu.valeur
def vider(self):
self.contenu = None
self.taille = 0
On pourrait également modifier la définition de est_vide pour utiliser une comparaison entre taille et 0, mais cela n’apporterait rien de particulier.
Calculatrice polonaise inverse à pile L'écriture polonaise inverse des expressions arithmétiques place l'opérateur après ses opérandes.
Cette notation ne nécessite aucune parenthèse ni aucune règle de priorité.
Ains l'expression polonaise inverse décrite par la chaîne de caractères
'1 2 3 x + 4 x'
désigne l'expression traditionnellement notée
(1+2 x 3) x 4.
La valeur d'une telle expression peut être calculée facilement en utilisant une pile pour stocker les résultats intermédiaires.
Pour cela, on observe un à un les éléments de l'expression et on effectue les actions suivantes :
- si on voit un nombre, on le place sur la pile:
- si on voit un opérateur binaire, on récupère les deux nombres au sommet de la pile, on leur applique l'opérateur, et on replace le résultat sur la pile.
Si l'expression était bien écrite, il y a bien toujours deux nombres sur la pile lorsque l'on voit un opérateur, et à la fin du processus il reste exactement un nombre sur la pile, qui est le résultat.
Écrire une fonction prenant en paramètre une chaîne de caractères représentant une expression en notation polonaise inverse composée d'additions et de multiplications de nombres entiers et renvoyant la valeur de cette expression.
On supposera que les éléments de lexpression sont séparés par des espaces.
Attention : cette fonction ne doit pas renvoyer de résultat si l'expression est mal écrite.
Tester avec :
exp_polo = '1 2 3 x + 4 x'
res_calcul = eval_polonaise_inverse(exp_polo)
print(res_calcul)
Résultat :
28
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
On itère sur les éléments obtenus en découpant la
chaîne au niveau des espaces. On isole d’abord les cas des opérateurs qui
sont les plus faciles à identifier et on suppose que tout ce qui n’est pas \"+\"
où \"*' est un entier (cette branche échouera si on trouve encore autre chose
dans l’expression). À la fin, on dépile le dernier élément et on vérifie que la
pile est bien vide avant de renvoyer ce résultat. Si à un moment il n’était
pas possible de dépiler, le programme échoue de toute façon.
def eval_polonaise_inverse(s):
pile = Pile()
for e in s.split(\" \"):
if e == \"+\" or e == \"x\":
x = pile.depiler()
y = pile.depiler()
if e == \"+\" :
z=x+y
else :
z = x * y
pile.empiler (z)
else:
pile.empiler(int(e))
res = pile.depiler()
assert pile.est_vide()
return res
exp_polo = '1 2 3 x + 4 x'
res_calcul = eval_polonaise_inverse(exp_polo)
print(res_calcul)
Parenthèse associée
On dit qu'une chaîne de caractères comprenant, entre autres choses, des parenthèses ( et ) est bien parenthésée lorsque chaque parenthèse ouvrante est associée à une unique fermante, et réciproquement.
Écrire une fonction prenant en paramètres une chaîne bien parenthésée s , et qui renvoie l'indice de la parenthèse ouvrante associée.
Tester avec :
exp = \"(2*(2+4*(3+1)))\"
print(ouvrante_associee(exp))
exp = \"(2*(2+4*(3+1))\"
print(ouvrante_associee(exp))
exp = \"(2*(2+4*(3+1))))\"
print(ouvrante_associee(exp))
Résultat :
0
1
Index error
Mettre le résultat ici (code et figure).
La première parenthèse fermée est la dernière qui a été ouverte. On utilise donc une pile pour suivre les associations. En l’occurrence, notre pile va enregistrer les indices des parenthèses ouvrantes qui n’ont pas encore été associées à des parenthèses fermantes.
def ouvrante_associee(s):
pile = Pile()
for c in s:
if c == \"(\":
pile.empiler(\"(\")
elif c == \")\":
pile.depiler()
return pile.taille
Chaînes bien parenthésées
On considère une chaîne de carac-
tères incluant à la fois des parenthèses rondes ( et ) et des parenthèses
carrées [ et 1. La chaîne est bien parenthésée si chaque ouvrante est asso-
ciée à une unique fermante de même forme, et réciproquement.
Écrire une fonction prenant en paramètre une chaîne de caractères conte-
nant, entre autres, les parenthèses décrites et qui renvoie True si la chaîne
est bien parenthésée et False sinon.
Mettre le résultat ici (code et figure).
On utilise une pile pour stocker toutes les parenthèses ouvrantes qui n’ont pas encore trouvé de fermante associée. Chaque fermante étant censée être associée à la dernière ouvrante non encore associée, on vérifie à chaque fermentante rencontrée que la parenthèse ouvrante associé est la bonne forme.
On échoue si l’ouvrante associée n’a pas la bonne forme, ou s’il n’y a pas d’ouvrante associée, ou encore si la pile n’est pas vide à la fin du processus (ce qui signifierait qu’au moins une ouvrante n’a pas été fermée).
def bonnes_parentheses(s):
assoc = { \")\": \"(\" , \"]\": \"[\" }
pile = Pile()
for c in s :
if c == \"(\" or c == \"[\":
pile.empiler(c)
elif c == \")\" or c == \"]\":
if pile.est_vide() or pile.depiler() != assoc[c]:
return False
return pile.est_vide()
Pile bornée
Une pile bornée est une pile dotée à sa création d'une capacité maximale. On propose l'interface suivante :
| fonction | description |
| creer_pile(p). | crée et renvoie une pile bornée de capacité c |
| est_vide(p) | renvoie True si p est vide et False sinon |
| est_pleine(p) | renvoie True si la pile est pleine et False sinon |
| empiler(f, e) | ajoute e au sommet de p si p n'est pas pleine, et lève une exception IndexError sinon |
| depiler(f) | retire et renvoie l'élément au sommet de p si p n'est pas vide, et lève une exception IndexError sinon |
On propose de réaliser une telle pile bornée à l'aide d'un tableau dont la taille est fixée à la création et correspond à la capacité c.
Les éléments de la pile sont stockés consécutivement à partir de l'indice 0 (qui contient l'élément du fond de la pile).
On se donne également un entier enregistrant le nombre d'éléments dans la pile, qui permet donc également de désigner l'indice de la prochaine case libre.
Ainsi dans le schéma ci-dessous, les éléments sont ajoutés et retirés du côté droit de la pile.
0 nb
| |
| a | b | .... | z | None | ... | None |
Réaliser une telle structure à l'aide d'une classe ayant pour attributs le
tableau fixe et le nombre d'éléments dans la pile bornée.
Tester avec :
p = PileBornee(5)
print(p.est_vide())
p.empiler(1)
p.empiler(2)
p.empiler(3)
p.empiler(4)
p.empiler(5)
print(p.est_pleine())
print(p.depiler())
print(p.depiler())
print(p.est_vide())
print(p.est_pleine())
Résultat :
True
True
5
4
False
False
Mettre le résultat ici (code et figure).
À la création d’une pile bornée on définit son contenu comme un tableau de taille donnée par la capacité passée en paramètre, dont toutes cases contiennent None. La pile vide est caractérisée par un nombre d’éléments nb nul et la pile pleine par un nombre d'éléments égal à
la capacité.
class PileBornee:
\"\"\"pile à capacité bornée\"\"\"
def __init__(self, cap):
self.contenu = [None] * cap
self.nb = 0
def est_vide(self):
return self.nb == 0
def est_pleine(self):
return self.nb == len(self.contenu)
Les méthodes empiler et depiler vérifient l’une et l’autre qu’elles sont applicables, et mettent à jour le nombre d’éléments nb. Lorsque dépiler retire un élément, on a choisi de remplacer cet élément dans le tableau par
None.
La pile est aussi bien réalisée avec ou sans ce détail, puisque tous les éventuels éléments aux indices nb et suivants sont inaccessibles en utilisant
linterface de la pile. Cependant un élément présent dans le tableau, même
à un indice normalement inaccessible, ne pourrait plus être désalloué par le gestionnaire de mémoire. On évite donc en les supprimant d'éventuelles fuites de mémoire.
def empiler(self, v):
if self.est_pleine():
raise IndexError(\"empiler sur une pile pleine\")
self.contenu[self.nb] = v
self.nb += 1
def depiler(self):
if self.est_vide():
raise IndexError(\"depiler sur une pile vide\")
self.nb -= 1
v = self.contenu[self.nb]
self.contenu[self.nb] = None
return v
File bornée
Une file bornée est unc file dotée à sa création d'une capacité maximale.
On propose l'interface suivante.
| fonction | description |
| creer_file(f). | crée et renvoie une file bornée de capacité c |
| est_vide(f) | renvoie True si f est vide et False sinon |
| est_pleine(f) | renvoie True si la file est pleine et False sinon |
| ajouter(f, e) | ajoute e à l'arrière de f si f n'est pas pleine, et lève une exception IndexError sinon |
| retirer(f) | retire et renvoie l'élément à l'avant de f si f n'est pas vide, et lève une exception IndexError sinon |
Comme pour la pile bornée, on propose dc réaliser une telle file bornée à l'aide d'un tableau dont la taille est fixée à la création et correspond à la capacité.
Les éléments de la file sont stockés consécutivement à partir d'un indice premier correspondant à l'avant de la file, et le tableau est considéré comme circulaire :
après la dernière case, les éléments reviennent à la première.
Dans les schémas ci-dessous, un élément retiré l'est au niveau de l'indice premier, et un élément ajouté l'est à l'autre extrémité.
premier premier+nb
| |
| None | ... | None | a | b | .... | z | None | ... | None |
(premier+nb)%cap premier
| |
| k | l | .... | z | None | ... | None | a | .... | j |
Réaliser une telle structure à l'aide d'une classe ayant pour attributs le tableau fixe, le nombre d'éléments dans la file bornée et l'indice du premier élément.
Tester avec :
f = FileBornee(5)
print(f.est_vide())
f.ajouter(1)
f.ajouter(2)
f.ajouter(3)
f.ajouter(4)
f.ajouter(5)
print(f.est_pleine())
print(f.retirer())
print(f.retirer())
print(f.est_vide())
print(f.est_pleine())
Résultat:
True
True
1
2
False
False
Mettre le résultat ici (code et figure).
L'initialisation est comme celle des piles bornées, et ajoute un attribut premier a la valeur 0 :
à l’origine, les éléments sont placés au début du tableau.
class FileBornee:
\"\"\"UWfile à capacité bornée\"\"\"
def __init__(self, cap):
self.contenu = [None] * cap
self.premier = 0
self.nb = 0
# invariant O <= premier < len(contenu)
# invariant O <= nb <= len(contenu)
def est_vide(self):
return self.nb == 0
def est_pleine(self):
return self.nb == len(self.contenu)
Les éléments sont ajoutés à la fin de la file. L'opération incrémente nb.
def ajouter(self, v):
if self.est_pleine():
raise IndexError(\"ajouter sur une file pleine\")
i = (self.premier + self.nb) % len(self.contenu)
self.contenu[i] = v
self.nb += 1
def retirer(self):
if self.est_vide():
raise IndexError(\"retirer sur une file vide\")
v = self.contenu[self.premier]
self.contenu[self.premier] = None
self.nb -= 1
self.premier = (self.premier + 1) % len(self.contenu)
return v
On a pris soin d’écrire None à la place de v (pour ne pas conserver inutilement
un pointeur vers v à l’intérieur de la structure, ce qui empêcherait le GC de
Python de la récupérer lorsqu'elle ne sera plus accessible par ailleurs).
Dans cet exercice, on se propose d'évaluer le temps d'attente de clients à des guichets, en comparant la solution d'une unique file d'attente et la solution d'une file d'attente par guichet.
Pour cela, on modélise le temps par une variable globale, qui est incrémenté à chaque tour de boucle.
Lorsqu'un nouveau client arrive, il est placé dans une file sous la forme d'un entier égal à la valeur de l'horloge, c'est-à-dire égal à son heure d'arrivée.
Lorsqu'un client est servi, c'est-à-dire lorsqu'il sort de sa file d'attente, on obtient son temps d'attente en faisant la soustraction de la valeur courante de l'horloge et de la valeur qui vient d'être retirée de la file.
L'idée est de faire tourner une telle simulation relativement longtemps, tout en totalisant le nombre de clients servis et le temps d'attente cumulé sur tous les clients.
Le rapport de ces deux quantités nous donne le temps d'attente moyen. On peut alors comparer plusieurs stratégies (une ou plusieurs files, choix d'une file au hasard quand il y en à plusieurs, choix de la file où il y a le moins de clients, ete.).
On se donne un nombre N de guichets (par exemple, N=5). Pour simuler la disponibilité d'un guichet, on peut se donner un tableau d'entiers dispo de taille N.
La valeur de dispo[i] indique le nombre de tours d'horloge où le guichet i sera occupé.
En particulier, lorsque cette valeur vaut 0, cela veut dire que le guichet est libre et peut donc servir un nouveau client.
Lorsqu'un client est servi par le guichet à, on choisit un temps de traitement pour ce client, au hasard entre 0 et N, et on l'affecte à dispo[i].
À chaque tour d'horloge, on réalise deux opérations :
- on fait apparaître un nouveau client ;
- pour chaque guichet i,
- s'il est disponible, il sert un nouveau client (pris dans sa propre file ou dans l'unique file, selon le modèle}, le cas échéant ;
- sinon, on décrémente dispo[i].
Écrire un programme qui effectue une telle simulation, sur 100000 tours d'horloge, et affiche au final le temps d'attente moyen.
Comparer avec différentes stratégies.
Mettre le résultat ici (code et figure).
On se donne quelques variables globales :
from random import randint
ng = 5 # nb de guichets
tick = 0 # horloge
dispo = [0] * ng
unique = File()
total = 0 # temps d’attente total
servis = 0 # nb de clients servis
On suppose ici une unique file, réalisée ici avec le programme 27. Lorsqu'un
nouveau client arrive, on ajoute son heure d’arrivée dans la file.
def nouveau_client():
unique.ajouter(tick)
On définit une fonction servir pour que le guichet g serve un client.
def servir(g):
global total, servis
if not unique.est_vide():
t = unique.retirer()
total += tick - t
servis += 1
dispo[g] = randint(0, ng)
Enfin, le programme principal est constitué de la boucle suivante.
or __ in range(100000):
tick += 1
nouveau_client()
for g in range(ng):
if dispo[g] == 0:
servir(g)
else:
dispo[g] -= 1
print(total / servis)
Avec ce code, on obtient un temps d’attente moyen quasi nul (0,017). Mais
si on modélise maintenant une file par guichet, en modifiant les fonctions
nouveau_client et servir en conséquence, alors ce temps moyen passe à
1,92 si un nouveau client choisit systématiquement la file contenant le moins de clients et à 3.88 si un client choisit une file au hasard.
Compléter le programme ci-dessous du jeu de la bataille.
Vous aurez à gérer d'une part la valeur des cartes et d'autre part les cas d'égalités.
Indice : il faut créer une file égalité.
Le programme partiel du jeu de bataille :
from modFile import File
import random
paquet_alice = File()
paquet_basile = File()
#crée le jeu de 52 cartes
cartes = [i for i in range(0,52)]
#melange les cartes
random.shuffle(cartes)
#distribue les cartes aux 2 joueurs
for i in range(len(cartes)//2) :
paquet_alice.ajouter(cartes.pop())
paquet_basile.ajouter(cartes.pop())
#Gestion d'un tour de jeu
def tour():
global en_cours
if paquet_alice.est_vide():
print(\"Alice perd\")
en_cours = False
elif paquet_basile.est_vide():
print(\"Basile perd\")
en_cours = False
else :
tirer()
#Si la partie n'est pas terminée, tirage d'une carte
def tirer():
a = paquet_alice.retirer()
b = paquet_basile.retirer()
valeura = a%13
valeurb = b%13
print(\"Alice\",valeura,valeurb,\"Basile\")
#le programme ne gere pas l'égalité
if valeura > valeurb :
paquet_alice.ajouter(a)
paquet_alice.ajouter(b)
elif valeura < valeurb :
paquet_basile.ajouter(b)
paquet_basile.ajouter(a)
#démarrage du jeu
en_cours = True
nb_tours = 0
while en_cours :#not paquet_alice.est_vide() and not paquet_basile.est_vide() :
tour()
nb_tours+=1
print(\"Partie en \",nb_tours,\" tours\")
Importer le module modFile.py :
https://sciencesappliquees.com/images/nsi/modFile.py
et tester le jeu de carte de la bataille.
Une fois terminé les modifications, vous transformerez le programme bataille en classe Bataille avec toutes les fonctions encapsulé dans cette-ci.
Mettre le résultat ici (code et figure).
def affiche(valeur) :
couleur = [\"Ca\",\"Pi\",\"Co\",\"Tr\"]
numero = [\"2\",\"3\",\"4\",\"5\",\"6\",\"7\",\"8\",\"9\",\"10\",\"Va\",\"Da\",\"Ro\",\"1\"]
return (couleur[valeur//13],numero[valeur%13])
Le programme de la bataille modifié :
from modFile import File
import random
paquet_alice = File()
paquet_basile = File()
paquet_egalite = File()
#crée le jeu de 52 cartes
cartes = [i for i in range(0,52)]
#melange les cartes
random.shuffle(cartes)
#distribue les cartes aux 2 joueurs
for i in range(len(cartes)//2) :
paquet_alice.ajouter(cartes.pop())
paquet_basile.ajouter(cartes.pop())
#Gestion d'un tour de jeu
def tour():
global en_cours
if paquet_alice.est_vide():
print(\"Alice perd\")
en_cours = False
elif paquet_basile.est_vide():
print(\"Basile perd\")
en_cours = False
else :
tirer()
def affiche(valeur) :
couleur = [\"Ca\",\"Pi\",\"Co\",\"Tr\"]
numero = [\"2\",\"3\",\"4\",\"5\",\"6\",\"7\",\"8\",\"9\",\"10\",\"Va\",\"Da\",\"Ro\",\"1\"]
return (couleur[valeur//13],numero[valeur%13])
def tirer():
a = paquet_alice.retirer()
b = paquet_basile.retirer()
valeura = a%13
valeurb = b%13
print(\"Alice\",affiche(a),affiche(b),\"Basile\")
#le programme ne gere pas l'égalité
if valeura > valeurb :
paquet_alice.ajouter(a)
paquet_alice.ajouter(b)
while not paquet_egalite.est_vide() :
paquet_alice.ajouter(paquet_egalite.retirer())
elif valeura < valeurb :
paquet_basile.ajouter(b)
paquet_basile.ajouter(a)
while not paquet_egalite.est_vide() :
paquet_alice.ajouter(paquet_egalite.retirer())
else : #gerer l'egalité
print(\"Egalité\")
paquet_egalite.ajouter(b)
paquet_egalite.ajouter(a)
#carte à l'envers
if not paquet_alice.est_vide() :
paquet_egalite.ajouter(paquet_alice.retirer())
if not paquet_basile.est_vide() :
paquet_egalite.ajouter(paquet_basile.retirer())
#démarrage du jeu
en_cours = True
nb_tours = 0
while en_cours :#not paquet_alice.est_vide() and not paquet_basile.est_vide() :
tour()
nb_tours+=1
print(\"Partie en \",nb_tours,\" tours\")