Actualité

[[{"text":"

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$

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$

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.

","title":"Piles et files","posi":19},{"edit":"

"}],[{"text":"

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.

","title":"Interface et utilisation d'une pile"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

$\"pile_file.png$

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()

","title":"Utilisation d'une pile : bouton de retour en arrière","tagtitle":"h1"},{"edit":"

"}],[{"text":"

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.

","title":"Pile d'appels"},{"edit":"

"}],[{"text":"

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

","title":"Interface et utilisation d'une file"},{"edit":"

"}],[{"text":"

$\"pile_file1.png$

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.

","title":"Utilisation d'une file : jouer à la bataille"},{"edit":"

Mettre le résultat ici.

"}],[{"text":"

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.

","title":"Réaliser une pile avec une liste chaînée","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

. 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())

","title":"Piles et tableaux Python"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

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

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.

","title":"Réaliser une file avec une liste chaînée mutable"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

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":"

"}],[{"text":"

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.

","title":"Réaliser une file avec deux piles"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

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":"

"}],[{"text":"

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 :

La pile est vide

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

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)

"}],[{"text":"

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).

"},{"solution":"

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)

"}],[{"text":"

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 :

La pile est vide

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

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.

"}],[{"text":"

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 :

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

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)

"}],[{"text":"

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 :

Index error

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

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

"}],[{"text":"

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.

","title":"Exercice","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

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()

"}],[{"text":"

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

| |

....

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.est_vide())

print(p.est_pleine())

Résultat :

True

False

","title":"Exercice","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

À 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

"}],[{"text":"

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

....

None

...

None

(premier+nb)%cap premier

| |

....

None

...

None

....

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.est_vide())

print(f.est_pleine())

Résultat:

True

False

","title":"Exercice","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

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).

"}],[{"text":"

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.

","title":"Exercice","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

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.

"}],[{"text":"

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.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"Pour afficher la valeur de la carte, on utilise 2 tableau :

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\")

"}]]

Détails: Écrit par : Richard GAUTHIER; Création : 16 Octobre 2020; Mis à jour : 21 Octobre 2020; Clics : 1890

[[{"title":"Listes chaînées","posi":0},{"text":"

La structure de tableau permet de stocker des séquences d'éléments mais n'est pas adaptée à toutes les opérations que l'on pourrait vouloir effectuer

sur des séquences. Les tableaux de Python permettent par exemple d'insérer ou de supprimer efficacement des éléments à la fin d'un tableau, avec les opérations append et pop, mais se prêtent mal à l'insertion ou la suppression d'un élément à une autre position.

En effet, les éléments d'un tableau étant contigus et ordonnés en mémoire, insérer un élément dans une séquence demande de déplacer tous les éléments qui le suivent pour lui laisser une

place.

Si par exemple on veut insérer une valeur v à la première position d'un tableau

il faut d'une façon où d'une autre construire le nouveau tableau

dans lequel la case d'indice 0 contient maintenant la valeur v.

On peut le faire en utilisant l'opération insert des tableaux de Python.

t = [1,1,2,3,5,8,13]

v = 4

print(\"t =\",t)

t.insert(v,0)

print(\"t =\",t)

Cette opération est cependant très coûteuse, car elle déplace tous les éléments du tableau d'une case vers la droite après avoir agrandi le tableau.

C'est exactement comme si nous avions écrit les lignes suivantes :

t = [1,1,2,3,5,8,13]

v = 4

print(\"t =\",t)

t.append(None)

for i in range(len(t) - 1, 0, -1):

t[i] = t[i - 1]

t[0] = v

print(\"t =\",t)

Avec une telle opération on commence donc par agrandir le tableau, en ajoutant un nouvel élément à la fin avec append.

None

Puis on décale tous les éléments d'une case vers la droite, en prenant soin de commencer par le dernier et de terminer par le premier.

Enfin, on écrit la valeur v dans la première case du tableau.

Au total, on a réalisé un nombre d'opérations proportionnel à la taille du tableau. Si par exemple le tableau contient un million d'éléments, on fera un

million d'opérations pour ajouter un premier élément.

En outre, supprimer le premier élément serait tout aussi coûteux, pour les mêmes raisons.

Dans cette séquence nous étudions une structure de données, la liste chaînée, qui d'une part apporte une meilleure solution au problème de l'insertion et de la suppression au début d'une séquence d'éléments, et d'autre part servira de brique de base à plusieurs autres structures dans les prochaines séquences.

"},{"text":""}],[{"text":"*****

Une liste chaînée permet avant tout de représenter une liste, c'est-à-dire une séquence finie de valeurs, par exemple des entiers.

Comme le nom le suggère sa structure est en outre caractérisée par le fait que les éléments sont chaînés entre eux, permettant le passage d'un élément à l'élément suivant.

Ainsi, chaque élément est stocké dans un petit bloc alloué quelque part dans la mémoire, que l'on pourra appeler maillon ou cellule, et y est accompagné d'une deuxième information : l'adresse mémoire où se trouve la cellule contenant l'élément suivant de la liste.

$\"\"$

Ici, on illustré une liste contenant trois éléments, respectivement 1, 2 et 3.

Programme — Cellule d'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

*****

contenant d'une part sa valeur (dans la case de gauche} et d'autre part l'adresse mémoire de la valeur suivante (dans la case de droite). Dans le cas

du dernier élément, qui ne possède pas de valeur suivante, on utilise une valeur spéciale désignée ici par le symbole ⊥ et marquant la fin de la liste.

Une façon traditionnelle de représenter une liste chaînée en Python consiste à utiliser une classe décrivant les cellules de la liste, de sorte que chaque élément de la liste est matérialisé par un objet de cette classe.

Cette classe est appelée ici Cellule et est donnée dans le programme ci-dessus. Tout objet de cette classe contient deux attributs : un attribut valeur pour la valeur

de l'élément (l'entier, dans notre exemple) et un attribut suivante pour la cellule suivante de la liste.

Lorsqu'il n'y à pas de cellule suivante, c'est-à-dire lorsque l'on considère la dernière cellule de la liste, on donne à l'attribut suivante la valeur None.

Dit autrement, None est notre représentation du

symbole ⊥.

Pour construire une liste, il suffit d'appliquer le constructeur de la classe Cellule autant de fois qu'il y a d'éléments dans la liste.

lst = Cellule(1, Cellule(2, Cellule(3, None)))

Ainsi, l'instruction construit la liste 1,2,3 donnée en exemple plus haut et la stocke dans une variable lst.

Plus précisément, on a ici créé trois objets de la classe Cellule, que l'on peut visualiser comme suit.

print(lst)

La valeur contenue dans la variable lst est l'adresse mémoire de l'objet contenant la valeur 1, qui lui-même contient dans son attribut suivante l'adresse mémoire de l'objet contenant la valeur 2, qui enfin contient dans

son attribut suivante l'adresse mémoire de l'objet contenant la valeur 3.

Ce dernier contient la valeur None dans son attribut suivante, marquant ainsi la fin de la liste.

Par la suite, on s'autorisera un dessin simplifié, de la

manière suivante.

Dans ce dessin, il faut interpréter chaque élément de la liste comme un objet de la classe Cellule.

","title":"Structure de liste chaînée"},{"edit":"

Mettre ici les résultats.

"}],[{"text":"

. Comme on le voit, une liste est soit la valeur None, soit un objet de la classe Cellule dout l'attribut suivante contient une liste. C'est là une définition récursive de la notion de liste.

","title":"Définition récursive des listes chaînées"},{"edit":"

Mettre le résultat ici.

"}],[{"text":"

Représentations alternatives. D'autres représentations des listes chaînées sont possibles. Plutôt qu'un objet de la classe Cellule, on pourrait

utiliser un couple, et dans ce cas écrire (1, (2, (3,None))), ou encore un tableau à deux éléments, et dans ce cas écrire [1, [2, [3,None]]]. Cependant, l'utilisation d'une valeur structurée avec des champs nominés

(ici les attributs valeur et suivante) est idiomatique, y compris dans un langage comme Python.

Variantes des listes chaînées. Il existe de nombreuses variantes de la structure de liste chaînée, dont la liste cyclique, où le dernier élément est lié au premier,

ou la liste doublement chaînée, où chaque élément est lié à l'élément suivant et à l'élément précédent dans la liste,

ou encore la liste cyclique doublement chaînée qui combine ces deux variantes.

Dans tout cette séquence, on ne manipule que des listes simplement chaînées et ne contenant pas de cycles.

Homogénéité. Bien que nous illustrions cette séquence avec des listes d'entiers, les listes chaînées, au même titre que les tableaux Python, peuvent

contenir des valeurs de n'importe quel type.

Ainsi, on peut imaginer des listes de chaînes de caractères, de couples, etc. Comme pour les tableaux, nous recommandons une utilisation homogène des listes chaînées, où tous les éléments de la liste sont du même type.

","title":""},{"edit":"

"}],[{"text":"

Dans cette section, nous allons programmer quelques opérations fondamentales sur les listes.

D'autres opérations sont proposées en exercices.

","title":"Opérations sur les listes"},{"edit":""}],[{"text":"

****

La première opération que nous allons programmer consiste à calculer la longueur d'une liste chaînée, c'est-à-dire le nombre de cellules qu'elle contient.

Il s'agit donc de parcourir la liste, de la première cellule jusqu'à la dernière, en suivant les liens qui relient les cellules entre elles.

On peut réaliser ce parcours, au choix, avec une fonction récursive ou avec une boucle.

Nous allons faire les deux. Dans les deux cas, on écrit une fonction longueur qui reçoit une liste lst en argument et renvoie sa longueur.

def longueur (lst):

\"\"\"renvoie La longueur de la Liste lst\"\"\"

Commençons par la version récursive. Elle consiste à distinguer le cas de base, c'est-à-dire une liste vide ne contenant aucune cellule, du cas général, c'est-à-dire une liste contenant au moins une cellule.

Dans le premier cas, il suffit de renvoyer 0 :

if lst is None:

return 0

Ici, on a testé si la liste lst est égale à None avec l'opération is de Python mais on aurait tout aussi bien pu utiliser ==, c'est-à-dire écrire lst == None.

Dans le second cas, il faut renvoyer 1, pour la première cellule, plus la longueur du reste de la liste, c'est-à-dire la longueur de la liste lst suivante, que l'on peut calculer récursivement :

else:

return 1 + longueur (lst.suivante)

On se persuade facilement que cette fonction termine, car le nombre de cellules de Ia liste passée en argument à la fonction longueur décroît strictement à chaque appel.

Écrivons maintenant la fonction longueur différemment, cette fois avec une boucle. On commence par se donner deux variables : une variable n contenant la longueur que l'on calcule et une variable c contenant la cellule courante du parcours de la liste.

def longueur (lst) :

\"\"\"renvoie la longueur de la liste lst\"\"\"

n = 0

c = lst

Initialement, n vaut 0 et c prend la valeur de lst, c'est-à-dire None si la liste est vide et la première cellule sinon.

Le parcours est ensuite réalisé avec une boucle while, qui exécute autant d'itérations qu'il y a de cellules dans

la liste.

while c is not None:

L'opération is not est, comme on le devine, la négation de l'opération is.

On exécuter donc cette boucic tant que c n'est pas égale à None.

À chaque étape, c'est-à-dire pour chaque cellule de la liste, on incrémente le compteur n et on passe à la cellule suivante en donnant à c la valeur de c.suivante.

n += 1

c = c.suivante

Une fois que l'on sort de la boucle, il suffit de renvoyer la valeur de n.

return n

Il est important de comprendre que, dans cette version itérative, seule la variable c est modifiée, pour désigner successivement les différentes cellules de la liste :

L'affectation c = c.suivante ne modifie pas le contenu ou la structure de la liste, seulement le contenu de la variable c, qui est l'adresse d'une cellule de ta liste.

Le code complet de ces deux fonctions Longueur est donné ci-dessous.

Programme — Calcul de la longueur d'une liste

class Cellule:

\"\"\"une cellule d'une Liste chaînée\"\"\"

def __init__(self, v, s):

self.valeur = v

self.suivante = s

lst = Cellule(1, Cellule(2, Cellule(3, None)))

# avec une fonction récursive

def longueurR(lst):

\"\"\"renvoie la Longueur de La liste lst\"\"\"

if lst is None :

return 0

else:

return 1 + longueurR(lst.suivante)

# avec une boucle

def longueurB(lst):

\"\"\"renvoie la longueur de la Liste lst\"\"\"

n = 0

c = lst

while c is not None:

n += 1

c = c.suivante

return n

print(longueurB(lst))

print(longueurR(lst))

Complexité. Il est clair que la complexité du calcul de la longueur est directement proportionnelle à la longueur elle-même, puisqu'on réalise un

*******

22 aatbete Je 12 dise A

nremhss nnmabtans Anune liste Lst de mille

cellules, longueur (lst) va effectuer mille tests, mille

appels récursifs et mille additions dans sa version récursive, et mille tests, mille additions et deux mille affectations dans sa version itérative.

","title":"Longueur d'une liste"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Comparaison avec None. À priori, il n'y à pas de différence entre écrire lst is None et lst == None.

Les deux opérations ne sont pas exactement les mêmes : l'opération is est une égalité physique {être identiquement le même objet, au même endroit dans la mémoire) et l'opération == est une égalité structurelle (être la même valeur, après une comparaison

en profondeur).

Mais dans le cas particulier de la valeur None, ces deux

égalités coïncident, car l'objet qui représente None est unique.

On teste donc bien si la valeur de lst est None dans les deux cas.

Cependant, une classe peut redéfinir l'égalité représentée par l'opération == et, dans ce cas, potentiellement modifier le résultat d'une comparaison avec None. Pour cette raison, il est d'usage de tester l'égalité à None avec is plutôt qu'avec ==. Bien évidemment, dans le cas précis de notre propre classe Cellule, nous savons qu'elle ne redéfinit pas l'opération ==, Néanmoins, nous choisissons de nous conformer à cette bonne pratique.

"}],[{"text":"

Comme deuxième opération sur les listes, écrivons une fonction qui renvoie le n-ième élément d'une liste chaînée.

On prend la convention que le premier élément est désigné par n = 0, comme pour les tableaux.

On cherche donc à écrire une fonction de la forme suivante.

def nieme_element(n, lst):

\"\"\"renvoie Le n-ième élément de la liste lst

Les éléments sont numérotés à partir de 9\"\"\"

Comme pour la fonction Longueur, nous avons le choix entre écrire la fonction nieme_element comme une fonction récursive ou avec une boucle.

Nous faisons ici le choix d'une fonction récursive.

Comme pour le calcul de la longueur, nous commençons par traiter le cas d'une liste qui ne contient aucun élément. Dans ce cas, on choisit de lever une exception, en l'occurrence la même exception IndexError que celle levée par Python lorsque l'on tente d'accéder à un indice invalide d'un tableau.

if lst is None:

raise IndexError (\"indice invalide\")

La chaîne de caractères passée en argument de l'exception est arbitraire.

Si en revanche la liste lst n'est pas vide, il y à deux cas de figure à considérer. Si n = 0, c'est que l'on demande le premier élément de la liste et il est alors renvoyé.

if n == 0:

return Ist.vaieur

Sinon, il faut continuer la recherche dans le reste de la liste. Pour cela, on fait un appel récursif à nieme_element en diminuant de un la valeur de n.

else:

return nieme_element(n - 1, lst.suivante)

Attention à ne pas oublier ici l'instruction return, car il faut renvoyer le résultat de l'appel récursif et non pas se contenter de faire un appel récursif.

Ceci achève le code de la fonction nieme_element. Le code complet est

Programme — N-ième élément d'une liste

lst = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", None))))

def nieme_element(n, lst):

\"\"\"renvote le n-ième élément de La liste lst

les éléments sont numérotés à partir de O\"\"\"

if lst is None:

raise IndexError(\"indice invalide\")

if n == 0 :

return lst.valeur

else:

return nieme_element(n - 1, lst.suivante)

print(nieme_element(2,lst))

Complexité. La complexité de la fonction nieme_element est un peu plus subtile que celle de la fonction longueur. Dans certains cas, on effectue exactement n appels récursifs pour trouver le n-ième élément, et donc un nombre d'opérations proportionnel à n.

Dans d'autres cas, en revanche, on parcourt toute la liste. Cela se produit clairement lorsque n > longueur (lst). Il pourrait être tentant de commencer par comparer n avec la longueur de la liste, pour ne pas parcourir la liste inutilement, mais c'est inutile car le calcul de la longueur parcourt déjà toute la liste. Pire encore, calculer la longueur de la liste à chaque appel récursif résulterait en un programme de complexité quadratique (proportionnelle au carré de la longueur de la liste).

On peut remarquer que la liste est également intégralement parcourue lorsque n < 0. En effet, la valeur de n va rester strictement négative, puisqu'on la décrémente à chaque appel, et on finira par atteindre la liste vide.

Pour y remédier, ii suffit de modifier légèrement le premier test de la fonction, de la manière suivante :

if n < 0 or lst is None:

raise IndexError(\"indice invalide\")

On obtient exactement le même comportement qu'auparavant (la levée de l'exception IndexError) mais cela se fait maintenant en temps constant, car la liste n'est plus parcourue.

","title":"N-ième élément d'une liste"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

*****

Considérons maintenant l'opération consistant à mettre bout à bout les éléments de deux listes données.

On appelle cela la concaténation de deux

listes.

Ainsi, si la première liste contient 1,2,3 et la seconde 4,5 alors le

****

de fanntinn nn la linda 4 D M O4 AT

sénat da la anmne

la concaténation sous la forme d'une fonction concatener qui reçoit deux listes en arguments et renvoie une troisième liste contenant la concaténation.

def concatener{(l1, l2):

\"\"\"concatène les listes l1 et l2, sous la forme d'une nouvelle liste\"\"\"

Il est ici aisé de procéder récursivement sur la structure de la liste 11. Si elle est vide, la concaténation est identique à la liste l2, qu'on se contente donc de renvoyer.

if l1 is None:

return l2

Sinon, le premier élément de la concaténation est le premier élément de l1 et le reste de la concaténation est obtenu récursivement en concaténant le reste de 11 avec l2.

else:

return Cellule(l1.valeur, concatener(l1.suivante,l2))

Le programme ci-dessus contient l'intégralité du code.

Il est important de comprendre ici que les listes passées en argument à la fonction concatener ne sont pas modifiées.

Plus précisément, les éléments de la liste l1 sont copiés et ceux de l2 sont partagés. Illustrons-le avec la

concaténation des listes 1,2,3 et 4,5.

Après les trois instructions

l1 = Celiule(1, Cellule(2, Cellule(3, None)))

l2 = Cellule(4, Cellule(5, None))

l3 = concatener(l1, l2)

on à la situation suivante, avec huit cellules au total :

On voit que les trois cellules de l1 ont été dupliquées, pour former le début de la liste 1,2, 3 ,4, 5, et que les deux cellules de l2 sont partagées pour former à

la fois la liste l2 et la fin de la liste l3.

Il n'y a pas de danger à réaliser ainsi un tel partage de cellules, tant qu'on ne cherche pas à modifier les listes, Une alternative consisterait à copier également tous les éléments de l2, ce qui pourrait se faire en écrivant une fonction copie et en remplaçant return l2 par

return copie(l2).

Mais c'est inutile dès lors qu'on choisit de ne jamais modifier les listes une fois construites.

Dans la section suivante, nous discuterons d'une autre façon de réaliser la concaténation de deux listes l1 et l2, consistant à modifier la dernière cellule de la liste 11 pour la faire pointer vers la première cellule de la liste l2.

Mais nous mettrons également en garde contre les dangers que comporte une

********

Programme - Concaténation de deux listes

def concatener(l1, l2):

\"\"\"concatène les listes l1 et l2, sous La forme d'une nouvelle liste\"\"\"

if l1 is None:

return l2

else:

return Cellule(l1.valeur, concatener(l1.suivante,l2))

l1 = Cellule(1, Cellule(2, Cellule(3, None)))

l2 = Cellule(4, Cellule(5, None))

l3 = concatener(l1, l2)

print(\"lg l3=\", longueurB(l3))

Complexité. Il est clair que le coût de la fonction concatener est directement proportionnel à la longueur de la liste 11. En revanche, il ne dépend

pas de la longueur de la liste l2.

","title":"Concaténation de deux listes"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Comme quatrième et dernière opération sur les listes, considérons le renversement d'une liste, c'est-à-dire une fonction renverser qui, recevant en argument une liste comme 1,2, 3, renvoie la liste renversée 3, 2,1.

Vu que la récursivité a été utilisée avec succès pour écrire les trois opérations précédentes, il semble naturel de chercher une écriture récursive de la fonction renverser.

Le cas de base est celui d'une liste vide, pour laquelle

il suffit de renvoyer la liste vide. Pour le cas récursif, en revanche, c'est plus délicat, car le premier élément doit devenir le dernier élément de la liste renversée. Aussi, il faut renverser la queue de la liste puis concaténer à la fin le tout premier élément.

Vu que nous venons justement d'écrire une fonction

concatener, il n'y a qu'à s'en servir. Cela nous donne un code relativement simple pour la fonction renverser.

def renverser1(lst):

if lst is None:

return None

else:

return concatener(renverser(lst.suivante), Cellule(lst.valeur, None))

l1 = Cellule(1, Cellule(2, Cellule(3, Cellule(4, Cellule(5, None)))))

r1 = renverser1(l1)

Un tel code, cependant, est particulièrement inefficace. Si on en mesure le temps d'exécution, on s'aperçoit qu'il est proportionnel au carré du nombre d'éléments.

Pour renverser une liste de 1000 éléments, il faut près d'un demimillion d'opérations.

En effet, il faut commencer par renverser une liste de 999 éléments, puis concaténer le résultat avec une liste d'un élément. Comme on l'a vu, cette concaténation coûte 999 opérations. Et pour renverser la liste de 999 éléments, il faut renverser une liste de 998 éléments puis concaténer le résultat avec une liste d'un élément. Et ainsi de suite.

Au total, on a donc au moins 999 + 998 + .. + 1 = 499500 opérations.

Une fois n'est pas coutume, la récursivité nous à mis sur la piste d'une mauvaise solution, du moins en termes de performance.

Il se trouve que dans le cas de la fonction renverser, une boucle while est plus adaptée.

En effet, il suffit de parcourir les éléments de la liste lst avec une simple boucle, et d'ajouter ses éléments au fur et à mesure en tête d'une seconde liste, appelons-la r.

Ainsi, le premier élément de la liste lst se retrouve en dernière position dans la liste r, le deuxième élément de lst en avant-dernière position dans r, etc., jusqu'au dernier élément de lst qui se retrouve en première position dans r.

Une bonne image est celle d'une pile de feuilles de papier sur notre bureau : si on prend successivement chaque feuille au sommet de la pile pour former à côté une seconde pile, alors on aura inversé l'ordre des feuilles au final.

Ici, la liste lst joue le rôle de la première pile et la liste r celle de la seconde.

Pour mettre en œuvre le code, on commence par se donner deux variables : une variable r pour le résultat et une variable c pour parcourir la liste lst.

def renverser(lst):

r = None

c = lst

On parcourt ensuite la liste avec une boucle while, en ajoutant à chaque étape le premier élément de c en tête de la liste r, avant de passer à l'élément suivant.

while c is not None:

Cellule(c.valeur, r)

c = c.suivante

Enfin, il ne reste plus qu'à renvoyer la liste r une fois sorti de la boucle.

return r

Le programme ci-dessous contient l'intégralité du code.

def renverser(lst):

\"\"\"renvoie une liste contenant les éléments de lst dans l'ordre inverse\"\"\"

r = None

c = lst

while c is not None:

r = Cellule(c.valeur, r)

c = c.suivante

return r

def afficher(lst) :

\"\"\"affiche les éléments d'une liste\"\"\"

c = lst

while c is not None:

print(c.valeur,c.suivante)

c = c.suivante

print(\"l1 = \")

l1 = Cellule(1, Cellule(2, Cellule(3, Cellule(4, Cellule(5, None)))))

afficher(l1)

print(\"r1 = \")

r1 = renverser(l1)

afficher(r1)

Complexité. Il est clair que cette nouvelle fonction

directement proportionnel à la longueur de la liste lst, car le code fait un simple parcours de la liste, avec deux opérations élémentaires à chaque étape.

Ainsi, renverser une liste de 1000 éléments devient presque instantané, avec un millier d'opérations, là où notre fonction basée sur la concaténation utilisait un demi-million d'opérations.

","title":"Renverser une liste"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Jusqu'à présent, nous avons délibérément choisi de ne jamais modifier les deux attributs valeur et suivante d'un objet de la classe Cellule. Une fois qu'un tel objet est construit, il n'est plus jamais modifié.

Cependant, rien ne nous empêcherait de le faire, intentionnellement ou accidentellement, car il reste toujours possible de modifier la valeur de ces attributs a posteriori avec des affectations.

Reprenons l'exemple de la liste 1,2,3 du début de cette séquence, construite avec

lst = Cellule(1, Cellule(2, Cellule(3, None)))

et que nous représentons ainsi :

Nous pouvons modifier la valeur du deuxième élément de la liste avec l'affectation suivante

lst.suivante.valeu = 4

On n alors la situation suivante :

C'est-à-dire avec la liste 1,3,8.

Ici, on vient de modifie le contenu de la liste,

en modifiant un attribut valeur.

Mais on peut également modifier la structure de la liste, en modifiant un attribut suivante.

Si par exemple on réalise maintenant l'affectation

lst.suivante.suivante =Cellule(5,None)

alors on se retrouve avec la situation suivante :

Ici, on a représenté que l'attribut suivante du deuxième élément pointait anciennement vers l'élément 3 (en pointillés) et qu'il pointe désormais vers un nouvel élément 5. La variable lst contient maintenant la liste 1,4,3.

","title":"Modification d'une liste"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Puisque les listes peuvent être modifiées à posteriori, comme nous venons de l'expliquer, il peut être tentant d'en tirer profit pour écrire autrement certaines de nos opérations sur les listes.

Ainsi, pour réaliser la concaténation de deux listes, par exemple, il suffit de modifier l'attribut suivante du

dernier élément de la première liste pour lui donner la valeur de la seconde liste.

Cela semble une bonne idée. Mais il y a un risque.

Supposons que l'on construise deux listes 1,2,3

et 4,5 de la manière suivante :

l2 = Cellule(2, Cellule(3, None))

l1 = Cellule(1, l2)

l3 = Cellule(4, Cellule(5, None))

On note en particulier que la variable l2 contient toujours la liste 2,3, même si elle a servi depuis à construire la liste 1,2,3 stockée dans la variable l1.

S'il nous prend maintenant l'envie de concaténer les listes l1 et l3 en reliant le dernier élément de l1 au premier élément de l3, par exemple en appelant

une fonction concatener_en_place(l1, l3) qui ferait cela, alors on se retrouverait dans cette situation :

La variable l1 contient maintenant la liste 1,2,3,4,5, ce qui était recherché, mais la variable l2 ne contient plus la liste 2,3 mais la liste 2,3,4,5.

C'est là un effet de bord qui n'était peut-être pas du tout souhaité.

D'une manière générale, pouvoir accéder à une même donnée par deux chemins différents n'est pas un problème en soi, mais modifier ensuite la donnée par l'intermédiaire de l'un de ces chemins (ici l1) peut résulter en une modification non souhaitée de la valeur accessible par un autre chemin (ici l2).

Par ailleurs, que feraient deux appels supplémentaires à concatener_en_place(l1, l3)?

C'est pourquoi nous avons privilégié une approche où la concaténation, et plus généralement les opérations qui construisent des listes, renvoient de nouvelles listes plutôt que de modifier leurs arguments.

On peut remarquer que c'est là une approche également suivie par certaines constructions de Python. L'opération + de Python, par exemple, ne modifie pas ses arguments mais renvoie une nouvelle valeur, qu'il s'agisse d'entiers, de chaînes de caractères ou encore de tableaux.

Ainsi, si t est le tableau [1, 2], alors t + [3]

construit un nouveau tableau [1, 2, 3].

En ce sens, l'opération + se distingue d'autres opérations, comme .append, qui modifient leur argument.

Comme nous allons le voir dans la section suivante, cela ne nous empêche pas pour autant d'utiliser nos listes dans un style de programmation impératif.

","title":"Du danger des listes mutables"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

*****

Pour terminer cette séquence sur les listes chaînées, nous allons maintenant montrer comment encapsuler une liste chaînée dans un objet.

L'idée consiste à définir une nouvelle classe, Liste, qui possède un unique attribut, tete, qui contient une liste chaînée. On l'appelle tete car il désigne la tête de la liste, lorsque celle-ci n'est pas vide (et None sinon).

Le constructeur initialise l\"attribut tete avec la valeur None.

class Liste:

\"\"\"une Liste chaînée\"\"\"

def __init__(self):

self.tete = None

Autrement dit, un objet construit avec Liste() représente une liste vide.

On peut également introduire une méthode est_vide qui renvoie un booléen indiquant si la liste est vide.

def est_vide(self):

return self.tete is None

En effet, notre intention est d'encapsuler, c'est-à-dire de cacher, la représentation de la liste derrière cet objet. Pour cette raison, on ne souhaite pas que l'utilisateur de la classe Liste teste explicitement si l'attribut tete vaut None, mais qu'il utilise cette méthode est_vide.

On poursuit la construction de la classe Liste avec une méthode pour ajouter un élément en tête de la liste.

def ajoute(self, x):

self.tete = Cellule(x, self.tete)

Cette méthode modifie l'attribut tete et ne renvoie rien. Si par exemple on exécute les quatre instructions ci-dessous :

lst = Liste()

lst.ajoute(3)

lst.ajoute(2)

lst.ajoute(1)

on obtient la situation suivante :

On a donc construit ainsi la liste 1,2,3, dans cet ordre.

On peut maintenant reformuler nos opérations, à savoir longueur, nieme_element, concatener ou encore renverser, comme autant de méthodes de la classe Liste.

Ainsi, on peut écrire par exemple

def longueur(self):

return longueur(self.tete)

qui ajoute à la classe Liste une méthode longueur, qui nous permet d'écrire lst.longueur(} pour obtenir la longueur de la liste lst.

Il est important de noter qu'il n'y a pas confusion ici entre la fonction longueur définie précédemment et la méthode longueur.

En particulier, la seconde est définie en appelant la première. Le langage Python est ainsi fait que, lorsqu'on écrit longueur (self.tete), il ne s'agit pas d'un appel récursif à la méthode longueur. (Un appel récursif s'écrirait self. longueur().) Si l'on trouve que donner le même nom à la fonction et à la méthode est source de confusion, on peut tout à fait choisir un nom différent pour la méthode, comme par exemple

def taille(self):

return longueur(self.tete)

Mieux encore, on peut donner à cette méthode le nom __len__ et Python nous permet alors d'écrire len(lst} comme pour un tableau.

En eflet, lorsque l'on écrit len en Python, ce n'est qu'un synonyme pour l'appel de méthode __len__().

De même, on peut ajouter à la classe Liste une méthode pour accéder au n-ième élément de la liste, c'est-à-dire une méthode qui va appeler notre fonction nieme_element sur self.tete.

Le nom de la méthode est arbitraire et nous pourrions choisir de conserver le nom nieme_element. Mais

là encore nous pouvons faire le choix d'un nom idiomatique en Python, à savoir __getitem__

def __getitem_ _(self, n):

return nieme_element(n, self.tete)

Ceci nous permet alors d'écrire lst{[i] pour accéder au i-ème élément de notre liste, exactement comme pour les tableaux.

Pour la fonction renverser, on fait le choix de nommer la méthode reverse car là encore

*****

Dhaat nie nue must mena AIX masse dan obilansie da Dia

Programme - Encapsulation d'une liste dans un objet

class Liste:

\"\"\"une Liste chaînée\"\"\"

def __init__(self):

self.tete = None

def est_vide(self):

return self.tete is None

def ajoute(self, x):

self.tete = Cellule(x, self.tete)

def __len__(self):

return longueurB(self.tete)

def __getitem__(self, n):

return nieme_element(n, self.tete)

def reverse(self) :

self.tete = renverser(self.tete)

def __add__(self, lst):

r = Liste()

r.tete = concatener(self.tete, lst.tete)

return r

lst = Liste()

print(lst.est_vide())

lst.ajoute(3)

print(lst.est_vide())

lst.ajoute(2)

lst.ajoute(1)

print(len(lst))

print(lst[1])

Enfin, le cas de la concaténation est plus subtil, car il s'agit de renvoyer une nouvelle liste, c'est-à-dire un nouvel objet. On choisit d'appeler la méthode __add__ qui correspond à la syntaxe + de Python.

def __add__(self, lst):

r = Liste()

r.tete = concatener(self.tete, lst.tete)

return r

Ainsi, on peut écrire lst+lst pour obtenir la liste 1,2,3,1,2,3.

","title":"Encapsulation dans un objet"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Intérêt d'une telle encapsulation. Il est multiple. D'une part, il cache la représentation de la structure à l'utilisateur.

Ainsi, celui qui utilise notre classe Liste n'a plus à manipuler explicitement la classe Cellule.

Mieux encore, il peut complètement ignorer l'existence de la classe Cellule.

De même, il ignore que la liste vide est représentée par la valeur None. En particulier, la réalisation de la classe Liste pourrait être modifiée sans pour autant que le

code qui l'utilise n'ait besoin d'être modifié à son tour.

D'autre part, l'utilisation de classes et de méthodes nous permet de donner le même nom à toutes les méthodes qui sont de même nature.

Ainsi, on peut avoir plusieurs classes avec des méthodes est_vide, ajoute, etc. Si nous avions utilisé de simples fonctions, il faudrait distinguer

liste _est_vide, pile est vide, ensemble _est_vide, etc.

","title":""},{"edit":"

"}],[{"text":"

Écrire une fonction listeN(n) qui reçoit en argument un entier n, supposé positif ou nul, et renvoie la liste des entiers 1,2,...,n, dans cet ordre. Si n = 0, la liste renvoyée est vide.

Tester avec :

l2 = listeN(5)

afficher(l2)

Résultat :

1 <__main__.Cellule object at 0x103540a20>

2 <__main__.Cellule object at 0x103540a58>

3 <__main__.Cellule object at 0x103540da0>

4 <__main__.Cellule object at 0x103540a90>

5 None

Attention les adresses mémoires ne seront pas les mêmes.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

def listeN(n):

lst = None

while n > 0:

lst = Cellule(n, lst)

n -= 1

return lst

l2 = listeN(5)

afficher(l2)

"}],[{"text":"

Écrire une fonction affiche liste(lst) qui affiche, en utilisant la fonction print, tous les éléments de la liste lst, séparés par des espaces, suivis d'un retour chariot.

L'écrire comme une fonction récursive, puis avec une boucle while.

Tester avec :

l2 = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", None))))

affiche_liste(l2)

Le résultat est :

a b c d

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

Pour éviter que print n’insère un retour chariot après chaque élément, on utilise print(..., end= \" \"), puis un unique print() à la fin de la liste.

Avec une récursivité :

l2 = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", None))))

def affiche_liste(lst):

if lst is None:

print()

else :

print(lst.valeur, end=\" \")

affiche_liste(lst.suivante)

affiche_liste(l2)

Avec une itération :

l2 = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", None))))

def affiche_liste(lst):

c = lst

while c is not None:

print(c.valeur, end=\" \")

c = c.suivante

print()

affiche_liste(l2)

"}],[{"text":"

Réécrire la fonction nieme_element

lst = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", None))))

def nieme_element(n, lst):

\"\"\"renvote le n-ième élément de La liste lst

les éléments sont numérotés à partir de O\"\"\"

if lst is None:

raise IndexError(\"indice invalide\")

if n == 0 :

return lst.valeur

else:

return nieme_element(n - 1, lst.suivante)

print(nieme_element(2,lst))

avec une boucle while.

Tester avec :

l1 = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", None))))

print(nieme_element(2,l1))

Résultat :

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

Comme pour la fonction longueur, on se sert d’une

variable c pour parcourir la liste. On se sert également d’une variable i pour

mesurer notre avancement dans la liste. Il y a donc une double condition

d’arrêt à la boucle.

def nieme_element(n, lst):

i = 0

c = lst

while i < n and c is not None:

i += 1

c = c.suivante

if n < 0 or c is None:

raise IndexError(\"indice invalide\")

return c.valeur

l1 = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", None))))

print(nieme_element(2,l1))

Note : la condition n < 0 nous préserve d’une valeur négative qui aurait été passée à la fonction nieme_element. Bien entendu, on aurait pu effectuer ce

test dès l’entrée de la fonction, avant même de parcourir la liste, ou encore supposer que n est positif ou nul.

"}],[{"text":"

Écrire une fonction occurrences(x, lst) qui renvoie le

nombre d'occurrences de la valeur x dans la liste lst.

L'écrire comme une fonction récursive, puis avec une boucle while.

Tester avec :

l1 = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", Cellule(\"b\", Cellule(\"c\", Cellule(\"b\", None)))))))

print(\"nb b :\",occurrences(\"b\",l1))

print(\"nb a :\",occurrences(\"a\",l1))

Résultat :

nb b : 3

nb a : 1

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

Avec une fonction récursive :

def occurrences(x, lst):

if lst is None:

return 0

elif x == lst.valeur:

return 1 + occurrences(x, lst.suivante)

else:

return occurrences(x, lst.suivante)

l1 = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", Cellule(\"b\", Cellule(\"c\", Cellule(\"b\", None)))))))

print(\"nb b :\",occurrences(\"b\",l1))

print(\"nb a :\",occurrences(\"a\",l1))

Avec une itération (boucle) :

def occurrences(x, lst):

n=0

c = lst

while c.suivante is not None :

if x == c.valeur:

n += 1

c = c.suivante

if x == c.valeur:

n += 1

return n

l1 = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", Cellule(\"b\", Cellule(\"c\", Cellule(\"b\", None)))))))

print(\"nb b :\",occurrences(\"b\",l1))

print(\"nb a :\",occurrences(\"a\",l1))

"}],[{"text":"

Écrire une fonction trouve(x, lst} qui renvoie le rang de la première occurrence de x dans lst, le cas échéant, et None sinon.

L'écrire comme une fonction récursive, puis avec une boucle while.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

Tester avec ;

l1 = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", Cellule(\"b\", Cellule(\"c\", Cellule(\"b\", None)))))))

print(\"posi c :\",trouve(\"c\",l1))

print(\"posi a :\",trouve(\"a\",l1))

print(\"posi e :\",trouve(\"e\",l1))

Résultat :

posi c : 2

posi a : 0

posi e : None

"},{"solution":"

Ici la version récursive est assez pénible à écrire, car

il faut tester si l’appel récursif a renvoyé None :

ef trouve(x, lst):

if lst is None:

return None

elif lst.valeur == x :

return 0

else:

r = trouve(x, lst.suivante)

if r == None:

return None

else:

return 1 + r

l1 = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", Cellule(\"b\", Cellule(\"c\", Cellule(\"b\", None)))))))

print(\"posi c :\",trouve(\"c\",l1))

print(\"posi a :\",trouve(\"a\",l1))

print(\"posi e :\",trouve(\"e\",l1))

La boucle, en revanche, est plus simple à écrire :

def trouve(x, lst):

i=0

c = lst

while c is not None:

if c.valeur == x:

return i

c = c.suivante

i += 1

return None

l1 = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", Cellule(\"b\", Cellule(\"c\", Cellule(\"b\", None)))))))

print(\"posi c :\",trouve(\"c\",l1))

print(\"posi a :\",trouve(\"a\",l1))

print(\"posi e :\",trouve(\"e\",l1))

"}],[{"text":"

Écrire une fonction récursive concatener_inverse(l1, l2)

qui renvoie le même résultat que concatener(renverser(l1), l2), mais sans appeler ces deux fonctions.

En déduire une fonction renverser qui a la même complexité que le programme renverser de la séquence.

Tester avec :

lst1 = Cellule(1, Cellule(2, Cellule(3, Cellule(4, Cellule(5, Cellule(6, None))))))

lst = concatener_inverse(lst1,lst1)

affiche_liste(lst)

Résultat :

6 5 4 3 2 1 1 2 3 4 5 6

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

On procède récursivement sur la structure de la

liste l1 :

def concatener_inverse(l1, l2):

if l1 is None:

return l2

else:

return concatener_inverse(l1.suivante, \\

Cellule(l1.valeur, l2))

lst1 = Cellule(1, Cellule(2, Cellule(3, Cellule(4, Cellule(5, Cellule(6, None))))))

lst = concatener_inverse(lst1,lst1)

affiche_liste(lst)

La fonction renverser s’en déduit trivialement, en prenant une liste videdef renverser (1st):

return concatener_inverse(lst, None)

"}],[{"text":"

Écrire une fonction identiques(l1, l2) qui renvoie un booléen indiquant si les listes l1 et l2 sont identiques, c'est-à-dire contiennent exactement les mêmes éléments, dans le même ordre.

On suppose que l'on peut comparer les éléments de l1 et l2 avec l'égalité == de Python.

Tester avec :

lst1 = Cellule(1, Cellule(2, Cellule(3, Cellule(4, Cellule(5, Cellule(6, None))))))

lst2 = Cellule(1, Cellule(2, Cellule(3, Cellule(4, Cellule(5, Cellule(6, None))))))

lst3 = Cellule(1, Cellule(2, Cellule(3, Cellule(7, Cellule(5, Cellule(6, None))))))

print(identiques(lst1,lst2))

print(identiques(lst1,lst3))

Résultat :

True

False

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

On le fait ici avec une fonction récursive. Il faut

prendre soin de bien traiter le cas où l’une ou l’autre des listes est vide :

def identiques(l1, l2):

if l1 is None:

return l2 is None

if l2 is None:

return l1 is None

return l1.valeur == l2.valeur \\

and identiques(l1.suivante, l2.suivante)

lst1 = Cellule(1, Cellule(2, Cellule(3, Cellule(4, Cellule(5, Cellule(6, None))))))

lst2 = Cellule(1, Cellule(2, Cellule(3, Cellule(4, Cellule(5, Cellule(6, None))))))

lst3 = Cellule(1, Cellule(2, Cellule(3, Cellule(7, Cellule(5, Cellule(6, None))))))

print(identiques(lst1,lst2))

print(identiques(lst1,lst3))

"}],[{"text":"

Écrire une fonction inserer(x, lst) qui prend en arguments un entier x et une liste d'entiers lst, supposée triée par ordre croissant, et qui renvoie une nouvelle liste dans laquelle x a été inséré à sa place

Ainsi, insérer la valeur 3 dans la liste 1,2, 5,8 renvoie la liste 1,2,3,5,8.

On suggère d'écrire inserer comme une fonction récursive.

Tester avec :

lst = Cellule(2, Cellule(4, Cellule(7, Cellule(8, Cellule(9, Cellule(12, None))))))

affiche_liste(lst)

lst = inserer(4,lst)

lst = inserer(1,lst)

lst = inserer(14,lst)

affiche_liste(lst)

Résultat :

2 4 7 8 9 12

1 2 4 4 7 8 9 12 14

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

Le cas d'arrêt est double : soit la liste est vide,

soit x n’est pas plus grand que la valeur en tête de liste. Dans les deux cas, on ajoute x au début de lst. Sinon, on conserve le premier élément et on

insère x récursivement dans la liste lst.suivante.

def inserer(x, lst):

if lst is None or x <= lst.valeur:

return Cellule(x, lst)

else:

return Cellule(lst.valeur, inserer(x, lst.suivante))

lst = Cellule(2, Cellule(4, Cellule(7, Cellule(8, Cellule(9, Cellule(12, None))))))

affiche_liste(lst)

lst = inserer(4,lst)

lst = inserer(1,lst)

lst = inserer(14,lst)

affiche_liste(lst)

"}],[{"text":"

En se servant de l'exercice précédent, écrire une fonction tri_par_insertion(lst) qui prend en argument une liste d'entiers lst et renvoie une nouvelle liste, contenant les mêmes éléments et triée par ordre croissant.

On suggère de l'écrire comme une fonction récursive.

Tester avec :

lst1 = Cellule(5, Cellule(8, Cellule(7, Cellule(1, Cellule(3, Cellule(6, None))))))

affiche_liste(lst1)

lst2 = tri_par_insertion(lst1)

affiche_liste(lst2)

Résultat :

5 8 7 1 3 6

1 3 5 6 7 8

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

Le cas de base correspond à une liste de longueur

au plus 1, pour laquelle il suffit de la renvoyer.

def tri_par_insertion(lst):

if lst is None or lst.suivante is None:

return lst

else:

return inserer(lst.valeur, \\

tri_par_insertion(lst.suivante))

lst1 = Cellule(5, Cellule(8, Cellule(7, Cellule(1, Cellule(3, Cellule(6, None))))))

affiche_liste(lst1)

lst2 = tri_par_insertion(lst1)

affiche_liste(lst2)

Note : on pourrait également écrire if longueur(ist) <= 1 mais ce serait calculer inutilement la longueur de la liste (calculer la longueur oblige à parcourir toute la liste), ce qui dégraderait les performances de ce programme.

"}],[{"text":"

Exercice 57 Écrire une fonction liste_de_tableau(t} qui renvoie une liste qui contient les éléments du tableau t, dans le même ordre.

On suggère de l'écrire avec une boucle for.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

Tester avec :

t1 = [2,4,5,7,9,10,12]

print(t1)

lst1 = liste_de_tableau(t1)

affiche_liste(lst1)

Résultat ;

[2, 4, 5, 7, 9, 10, 12]

2 4 5 7 9 10 12

"},{"solution":"

Pour préserver l’ordre des éléments, il faut prendre

soin de parcourir le tableau de la droite vers la gauche :

def liste_de_tableau(t):

lst = None

for i in range(len(t) - 1, -1, -1):

lst = Cellule(t[i], lst)

return lst

t1 = [2,4,5,7,9,10,12]

print(t1)

lst1 = liste_de_tableau(t1)

affiche_liste(lst1)

"}],[{"text":"

Écrire une fonction derniere_cellule(lst) qui renvoie l'adresse mémoire de la dernière cellule de la liste lst. On suppose la liste lst non vide.

Tester avec :

lst1 = Cellule(5, Cellule(8, Cellule(7, Cellule(1, Cellule(3, Cellule(6, None))))))

print(derniere_cellule(lst1))

lst2 = Cellule(1, Cellule(5, Cellule(4, Cellule(6, Cellule(8, None)))))

print(derniere_cellule(lst2))

Résultat :

<__main__.Cellule object at 0x10405f898>

<__main__.Cellule object at 0x10405fe48>

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

def derniere_cellule(lst):

c = lst

while c.suivante is not None:

c = c.suivante

return c

lst1 = Cellule(5, Cellule(8, Cellule(7, Cellule(1, Cellule(3, Cellule(6, None))))))

print(derniere_cellule(lst1))

"}],[{"text":"

En utilisant la fonction de l'exercice précédent, écrire une seconde fonction, concatener_en_place(l1, l2), qui réalise une concaténation en place des listes l1 et l2, c'est-à-dire qui relie la dernière cellule de l1 à la première cellule de l2. Cette fonction doit renvoyer la toute première cellule de la concaténation.

Tester avec :

lst1 = Cellule(5, Cellule(8, Cellule(7, Cellule(1, Cellule(3, Cellule(6, None))))))

lst2 = Cellule(1, Cellule(5, Cellule(4, Cellule(6, Cellule(8, None)))))

affiche_liste(lst1)

affiche_liste(lst2)

lst3 = concatener_en_place(lst1, lst2)

affiche_liste(lst1)

affiche_liste(lst2)

affiche_liste(lst3)

Résultat :

5 8 7 1 3 6

1 5 4 6 8

5 8 7 1 3 6 1 5 4 6 8

1 5 4 6 8

5 8 7 1 3 6 1 5 4 6 8

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

def concatener_en_place(l1, l2):

if l1 is None:

return l2

c = derniere_cellule(l1)

c.suivante = l2

return l1

lst1 = Cellule(5, Cellule(8, Cellule(7, Cellule(1, Cellule(3, Cellule(6, None))))))

lst2 = Cellule(1, Cellule(5, Cellule(4, Cellule(6, Cellule(8, None)))))

affiche_liste(lst1)

affiche_liste(lst2)

lst3 = concatener_en_place(lst1, lst2)

affiche_liste(lst1)

affiche_liste(lst2)

affiche_liste(lst3)

"}]]

Détails: Écrit par : Richard GAUTHIER; Création : 14 Octobre 2020; Mis à jour : 14 Octobre 2020; Clics : 1420

Exercice 1 :

L'entreprise LocHome souhaite moderniser son système de location. En effet, elle utilise des fiches papiers pour gérer ses locations.

1.1. Donner la modélisation relationnelle de service de location.

Cette dernière doit permettre de mentionner :

- le client, possédants un numéro de téléphone alphanumérique unique, nom, prénom et adresse;

- la maison, possédants un identifiant unique, nombre de pièces et adresse;

- en location, possédants la date de début, la date de fin et les relations entre client et maison.

On prendra soin de préciser toutes les contraintes utilisateurs qui ne peuvent êtres inscrites dans les schémas des relations.

1.2. Donner les commandes SQL pour écrire ces tables.

Exercice 2 :

Soit les tables suivantes :

« Candidats » composé des champs suivants :
+ Matricule : Numéro d'immatriculation du candidat
+ Nom: nom du candidat
+ DateNaissance : date de naissance du candidat
+ DateDiplome : date d'obtention du diplôme
+ Code_ecole : code de l'école qui a délivrée le diplôme

«Ecole » composé des champs suivants :
+ Code_ecole :
+ Lib_école : intitulé de l'école

2.1. Ecrire en SQL l'insertion dans la table « candidats » un nouveau candidat ayant le matricule 3200. nommé
« Albert ». né le 12052004, et qui a obtenu son diplôme le 03/07/2020 délivré par Lycée Sérusier ayant le code 29022.

2.2. Ecrire en SQL la requête pour avoir la liste des candidats triés par ordre alphabétique.

2.3. Ecrire en SQL la requête pour avoir la liste des candidats lauréats de l'école « Séruiser ».

2.4. Ecrire en SQL la requête pour calculer l'age moyen des candidats.

Exercice 3 :

Vous allez importer dans phpmyadmin la base world.sql (Télécharger ici).

Elle se décompose de la manière suivante :

Table

city

name, le nom

code, le code du pays

district

population, la population de la ville

Table

country

code, le cpde du pays

name, le nom du pays

capital, la capitale du pays

Table

countryinfo

` (

code, le code du pays

indepyear, date indépendance pays

region, la région ou se situe le pays

continent, le continent ou se situe le pays

surfaceArea, la surface du pays

`governmentForm, le régime du pays

`population

lifeExpectancy, l'espérance de vie du pays

Table

countrylanguage

code, le code du pays

language, langue parler dans le pays

isOfficial, langue officiel (True ou False),

percentage, % parler par la population

3.1. Importer la base world.sql dans phpmyadmin.

3.2. Ecrire la requête SQL pour afficher toute la table des pays (country).

3.3. Ecrire la requête SQL pour afficher population française (code pays FRA).

3.4. Ecrire la requête SQL pour mettre à jour la population française (67000000 et code pays FRA).

3.5. Ecrire la requête SQL qui affiche le pays le plus peuplé.

3.6. Ecrire la requête SQL pour inserer dans la table city la ville de carhaix avec les attributs suivants : Carhaix, FRA, Bretagne, 7100.

3.7. Ecrire la requête SQL qui calcule la population mondiale.

3.8.Ecrire la requête SQL qui afficher la liste des pays qui parlent le français dans le monde.

3.9. Ecrire en utilisant une jointure avec les tables country et city, la requête SQL qui affiche les villes en France dans la table city.

3.10. Ecrire la requête SQL qui supprime la table countrylangage.

Détails: Écrit par : Richard GAUTHIER; Création : 13 Octobre 2020; Mis à jour : 17 Octobre 2021; Clics : 1162

[[{"login":"aa"}],[{"quiz":1090}]]

Détails: Écrit par : Richard GAUTHIER; Création : 11 Octobre 2020; Mis à jour : 11 Octobre 2020; Clics : 1212

[[{"login":"devoir"}],[{"quiz":1090}]]

Détails: Écrit par : Richard GAUTHIER; Création : 11 Octobre 2020; Mis à jour : 6 Octobre 2021; Clics : 809

Page 45 sur 79

1ère Générale NSI

Term. Générale NSI

Terminale STI2D SIN

Bts Ccst

Technico-commercial 3.0

Vidéos YouTube

tnsi json sequence 18 Piles et files

tnsi json sequence 17 Listes chaînées

Devoir sql 2020

1nsi devoir 2 login theme a

1nsi devoir 2 login theme a (2)