Aller au contenu

Exercices listes - piles - files

Exercice 1 : Implémentation d'une file avec deux piles⚓︎

Comment créer une file avec 2 piles ?
L'idée est la suivante : on crée une pile d'entrée et une pile de sortie.

  • quand on veut enfiler, on empile sur la pile d'entrée.
  • quand on veut défiler, on dépile sur la pile de sortie.
  • si celle-ci est vide, on dépile entièrement la pile d'entrée dans la pile de sortie.
La classe Pile

Il est impératif de comprendre qu'on peut choisir n'importe quelle implémentation de la classe Pile. Il suffit de connaître l'interface, Comme on ne va se servir que de cette interface, les mécanismes n'ont aucune influence sur le code de la classe File que nous ferons ensuite.

Par exemple, on choisit celle avec la liste chaînée (voir les compléments : Compléments

Exécuter absolument le code ci-dessous pour pouvoir continuer

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier

Une file avec deux piles

Compléter le code suivant

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier

Solution pour la méthode enfile
Python
def enfile(self, x):
    self.entree.empile(x)
Solution totale
Python
class File:
    def __init__(self):
        self.entree = Pile()
        self.sortie = Pile()

    def est_vide(self):
        return self.entree.est_vide() and self.sortie.est_vide()

    def enfile(self, x):
        self.entree.empile(x)

    def defile(self):
        if self.est_vide():
            print("File vide !")
            return None

        if self.sortie.est_vide():
            while not self.entree.est_vide():
                self.sortie.empile(self.entree.depile())

        return self.sortie.depile()

Exercice 2⚓︎

Exercice 5 du sujet Étrangers 1 - 2021 (sujet complet en pdf)

Notion abordée : structures de données : les piles.

Dans cet exercice, on considère une pile d'entiers positifs. On suppose que les quatre fonctions suivantes ont été programmées préalablement en langage Python :

  • empiler(P, e) : ajoute l'élément e sur la pile P ;
  • depiler(P) : enlève le sommet de la pile P et retourne la valeur de ce sommet ;
  • est_vide(P) : retourne True si la pile est vide et False sinon ;
  • creer_pile() : retourne une pile vide.

Dans cet exercice, seule l'utilisation de ces quatre fonctions sur la structure de données pile est autorisée.

Q1. Recopier le schéma ci-dessous et le compléter sur votre copie en exécutant les appels de fonctions donnés. On écrira ce que renvoie la fonction utilisée dans chaque cas, et on indiquera None si la fonction ne retourne aucune valeur.

enex1Q1

Q2. On propose la fonction ci-dessous, qui prend en argument une pile P et renvoie un couple de piles :

Python
def transforme(P) : 
    Q = creer_pile()
    while not est_vide(P) : 
        v = depile(P) 
        empile(Q, v)
    return (P,Q)
Recopier et compléter sur votre copie le document ci-dessous

enex1Q2

Q3. Ecrire une fonction en langage Python maximum(P) recevant une pile P comme argument et qui renvoie la valeur maximale de cette pile. On ne s’interdit pas qu’après exécution de la fonction, la pile soit vide.

Q4. On souhaite connaître le nombre d’éléments d’une pile à l’aide de la fonction taille(P). On s'interdit qu’après exécution de la fonction, la pile soit vide.

ex1Q3

Correction de l'exercice 2

ex1Q1

ex1Q2

Python
1
2
3
4
5
6
7
8
9
def maximum(P):
    if est_vide(P):
        return None
    m = depile(P)
    while not est_vide(P):
        val = depile(P)
        if val > m:
            m = val
    return m

Avec le code ci-dessus, la pile p est vide à la fin de l'exécution. Pour éviter cela, on peut par exemple créer une pile q temporaire qui recevra les éléments de p, avant de retransférer à la fin du programme les éléments de q dans p.

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def maximum(P):
    Q = creer_pile()
    if est_vide(P):
        return None
    m = depile(P)
    empile(Q, m)
    while not est_vide(P):
        val = depile(P)
        empile(Q, val)
        if val > m:
            m = val
    while not est_vide(Q):
        empile(P, depile(Q))
    return m

Q4a. On va vider la pile p dans une pile q tout en comptant le nombre d'éléments dépilés dans une variable t. On redonne ensuite à p son état initial en vidant q dans p.

Q4b

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def taille(P):
    if est_vide(P):
        return 0
    Q = creer_pile()
    t = 0
    while not est_vide(P):
        empile(Q, depile(P))
        t += 1
    while not est_vide(Q):
        empile(P, depile(Q))
    return t

Exercice 3⚓︎

Exercice 1 du sujet La Réunion J2 - 2022 (Sujet complet en pdf)

Cet exercice porte sur les structures de données (pile).

La notation polonaise inverse (NPI) permet d'écrire des expressions de calculs numériques sans utiliser de parenthèse. Cette manière de présenter les calculs a été utilisée dans des calculatrices de bureau dès la fin des années 1960. La NPI est une forme d’écriture d’expressions algébriques qui se distingue par la position relative que prennent les nombres et leurs opérations.

Par exemple :

Notation classique Notation NPI
\(3+9\) \(3 \qquad\) \(9 \qquad\) \(+\)
\(8 \times (3+5)\) \(8 \qquad\) \(3 \qquad\) \(5 \qquad\) \(+ \qquad\) \(\times\)
\((17+5) \times 4\) \(17 \qquad\) \(5 \qquad\) \(+ \qquad\) \(4 \qquad\) \(\times\)

L’expression est lue et évaluée de la gauche vers la droite en mettant à jour une pile.

  • Les nombres sont empilés dans l’ordre de la lecture.
  • Dès la lecture d’un opérateur (+, -, ×, /), les deux nombres au sommet de la pile sont dépilés et remplacés par le résultat de l’opération effectuée avec ces deux nombres. Ce résultat est ensuite empilé au sommet de la pile. A la fin de la lecture, la valeur au sommet est renvoyée.

Exemple : l’expression qui correspond au calcul \(7 \times (3+25)\) s’évalue à 196 comme le montrent les états successifs de la pile créée, nommée p :

  • On empile la valeur 7.
  • On empile la valeur 3.
  • On empile la valeur 25.
  • On remplace les deux nombres du sommet de la pile (25 et 3) par leur somme 28.
  • On remplace les deux nombres du sommet de la pile (28 et 7) par leur produit 196.

enex2Q1

  1. En vous inspirant de l’exemple ci-dessus, dessiner le schéma descriptif de ce que donne l’évaluation par la NPI de l’expression : \(12 \qquad\) \(4 \qquad\) \(5 \qquad\) \(\times\) \(+\)

  2. On dispose de la pile suivante nommée p1 :

ex2Q2

On rappelle ci-dessous les primitives de la structure de pile (LIFO : Last In First out) :

Fonction Description
pile_vide() Créé et renvoie une nouvelle pile vide
empiler(p, e) Place l’élément e au sommet de la pile p.
depiler(p) Supprime et renvoie l’élément se trouvant au sommet de p.
est_vide(p) Renvoie un booléen indiquant si p est vide ou non.

On dispose aussi de la fonction suivante, qui prend en paramètre une pile p :

Python
def top(p):
    x = depiler(p)
    empiler(p, x)
    return x
On exécute la ligne suivante temp = top(p1) : a. Quelle valeur contient la variable temp après cette exécution ? b. Représenter la pile p1 après cette exécution.

  1. En utilisant uniquement les 4 primitives d’une pile, écrire en langage Python la fonction addition(p) qui prend en paramètre une pile p d'au moins deux éléments et qui remplace les deux nombres du sommet d’une pile p par leur somme.
    Remarque : cette fonction ne renvoie rien, mais la pile p est modifiée.

  2. On considère que l’on dispose également d’une fonction multiplication(p) qui remplace les deux nombres du sommet d’une pile p par leur produit (on ne demande pas d’écrire cette fonction).
    Recopier et compléter, en n’utilisant que les primitives d’une pile et les deux fonctions addition et multiplication, la suite d’instructions (ci-dessous) qui réalise le calcul \((3+5) \times 7\) dont l’écriture en NPI est : \(3 \qquad\) \(5 \qquad\) \(+ \qquad\) \(7 \qquad\) \(\times\)

Python
p = pile_vide() 
empiler(p, 3)
...

Exercice 3

ex2Q1

La variable temp contient la valeur 25.

p1 est identique, elle contient toujours les valeurs 25, 3 et 7.

Python
1
2
3
4
def addition(p):
    nb1 = depiler(p)
    nb2 = depiler(p)
    empiler(p, nb1 + nb2)
Python
1
2
3
4
5
6
p = pile_vide()
empiler(p, 3)
empiler(p, 5)
addition(p)
empiler(p, 7)
multiplication(p)

Exercice 4⚓︎

Exercice 2 du sujet Métropole Candidats Libres J1 - 2021 Sujet complet en pdf

Cet exercice traite des notions de piles et de programmation orientée objet.

On crée une classe Pile qui modélise la structure d'une pile d'entiers.
Le constructeur de la classe initialise une pile vide.
La définition de cette classe sans l’implémentation de ses méthodes est donnée ci-dessous.

Python
class Pile:

def __init__(self):
"""Initialise la pile comme une pile vide."""

def est_vide(self):
"""Renvoie True si la liste est vide, False sinon."""

def empiler(self, e):
"""Ajoute l'élément e sur le sommet de la pile, ne renvoie rien."""

def depiler(self):
"""Retire l’élément au sommet de la pile et le renvoie."""

def nb_elements(self):
"""Renvoie le nombre d'éléments de la pile. """

def afficher(self):
"""Affiche de gauche à droite les éléments de la pile, du fond de la pile vers son sommet. 
Le sommet est alors l’élément affiché le plus à droite. Les éléments sont séparés par une virgule. 
Si la pile est vide la méthode affiche « pile vide »."""
Seules les méthodes de la classe ci-dessus doivent être utilisées pour manipuler les objets Pile.

  1. a. Écrire une suite d’instructions permettant de créer une instance de la classe Pile affectée à une variable pile1 contenant les éléments 7, 5 et 2 insérés dans cet ordre.
    Ainsi, à l’issue de ces instructions, l’instruction pile1.afficher() produit l’affichage : 7, 5, 2.

b. Donner l’affichage produit après l’exécution des instructions suivantes.

Python
element1 = pile1.depiler() 
pile1.empiler(5) 
pile1.empiler(element1) 
pile1.afficher()
  1. On donne la fonction mystere suivante :

Python
def mystere(pile, element): 
    pile2 = Pile()
    nb_elements = pile.nb_elements() 
    for i in range(nb_elements):
        elem = pile.depiler() 
        pile2.empiler(elem) 
        if elem == element:
            return pile2 
    return pile2
a. Dans chacun des quatre cas suivants, quel est l’affichage obtenu dans la console ?

  • Cas n°1

    Python Console Session
    >>>pile.afficher()
7, 5, 2, 3
>>>mystere(pile, 2).afficher()

  • Cas n°2

    Python Console Session
    >>>pile.afficher()
7, 5, 2, 3
>>>mystere(pile, 9).afficher()

  • Cas n°3

    Python Console Session
    >>>pile.afficher()
7, 5, 2, 3
>>>mystere(pile, 3).afficher()

  • Cas n°4

    Python Console Session
    >>>pile.est_vide() True
>>>mystere(pile, 3).afficher()

b. Expliquer ce que permet d’obtenir la fonction mystere.

  1. Écrire une fonction etendre(pile1, pile2) qui prend en arguments deux objets Pile appelés pile1 et pile2 et qui modifie pile1 en lui ajoutant les éléments de pile2 rangés dans l'ordre inverse. Cette fonction ne renvoie rien.
    On donne ci-dessous les résultats attendus pour certaines instructions.

Python Console Session
>>>pile1.afficher() 
7, 5, 2, 3
>>>pile2.afficher() 
1, 3, 4
>>>etendre(pile1, pile2)
>>>pile1.afficher() 
7, 5, 2, 3, 4, 3, 1
>>>pile2.est_vide() 
True
4. Écrire une fonction supprime_toutes_occurences(pile, element) qui prend en arguments un objet Pile appelé pile et un élément element et supprime tous les éléments element de pile.
On donne ci-dessous les résultats attendus pour certaines instructions.

Python Console Session
>>>pile.afficher() 
7, 5, 2, 3, 5
>>>supprime_toutes_occurences (pile, 5)
>>>pile.afficher() 
7, 2, 3

Exercice 4

Python
1
2
3
4
pile1 = Pile()
pile1.empiler(7)
pile1.empiler(5)
pile1.empiler(2)

L'affichage produit est 7, 5, 5, 2.

  • Cas n°1 : 3, 2
  • Cas n°2 : 3, 2, 5, 7
  • Cas n°3 : 3
  • Cas n°4 : «pile vide»

La fonction mystere permet d'obtenir la pile retournée jusqu'à un élément particulier (s'il existe).

Python
1
2
3
4
def etendre(pile1, pile2):
    while not pile2.est_vide():
        val = pile2.depiler()
        pile1.empiler(val)
Python
1
2
3
4
5
6
7
8
9
def supprime_toutes_occurences(pile, element):
    p_temp = Pile()
    while not pile.est_vide():
        val = pile.depiler()
        if val != element:
            p_temp.empiler(val)
    while not p_temp.est_vide():
        val = p_temp.depiler()
        pile.empiler(val)

Exercice 5⚓︎

Exercice 5 du sujet Amérique du Nord J1 - 2021 (Sujet complet en pdf)

Cet exercice porte sur la notion de pile, de file et sur la programmation de base en Python.

Les interfaces des structures de données abstraites Pile et File sont proposées ci-dessous. On utilisera uniquement les fonctions ci-dessous :

Les interfaces des structures de données abstraites Pile et File sont proposées ci-dessous. On utilisera uniquement les fonctions ci-dessous :

Structure de données abstraite : Pile
Utilise : Élément, Booléen Opérations :

  • creer_pile_vide : ∅\(\rightarrow\) Pile
    👉 creer_pile_vide() renvoie une pile vide
  • est_vide : Pile \(\rightarrow\) Booléen
    👉 est_vide(pile) renvoie True si pile est vide, False sinon
  • empiler : Pile, Élément \(\rightarrow\) ∅
    👉 empiler(pile, element) ajoute element à la pile pile
  • depiler : Pile \(\rightarrow\) Élément
    👉 depiler(pile) renvoie l’élément au sommet de la pile en le retirant de la pile

Structure de données abstraite : File
Utilise : Élément, Booléen Opérations :

  • creer_file_vide : ∅ \(\rightarrow\) File
    👉 creer_file_vide() renvoie une file vide
  • est_vide : File \(\rightarrow\) Booléen
    👉 est_vide(file) renvoie True si file est vide, False sinon
  • emfiler : File, Élément \(\rightarrow\) ∅
    👉 emfiler(file, element) ajoute element à la file file
  • defiler : File \(\rightarrow\) Élément
    👉 depiler(file) renvoie l’élément au sommet de la file en le retirant de la file file

1.

a) On considère la file F suivante : enfilement \(\rightarrow \fbox{"rouge" "vert" "jaune" "rouge" "jaune"} \rightarrow\) défilement
Quel sera le contenu de la pile P et de la file F après l’exécution du programme Python suivant :

Python
1
2
3
P = cree_pile_vide()
while not (est_vide(F)):
    empiler(P, defiler(F))

b) Créer une fonction taille_file qui prend en paramètre une file F et qui renvoie le nombre d’éléments qu’elle contient. Après appel de cette fonction la file F doit avoir retrouvé son état d’origine.

Python
1
2
3
def taille_file(F):
    """File->Int"""
    ...

2. Écrire une fonction former_pile qui prend en paramètre une file F et qui renvoie une pile P contenant les mêmes éléments que la file.
Le premier élément sorti de la file devra se trouver au sommet de la pile ; le deuxième élément sorti de la file devra se trouver juste en-dessous du sommet, etc.
Exemple : si F = \(\fbox{"rouge" "vert" "jaune" "rouge" "jaune"}\) alors l’appel former_pile(F) va renvoyer la pile P ci-dessous :

Python
        | "jaune" |
        | "rouge" |
        | "jaune" |
        | "vert"  |
        | "rouge" |
         _________
3. Écrire une fonction nb_elements qui prend en paramètres une file F et un élément elt et qui renvoie le nombre de fois où elt est présent dans la file F.
Après appel de cette fonction la file F doit avoir retrouvé son état d’origine.

4. Écrire une fonction verifier_contenu qui prend en paramètres une file F et trois entiers : nb_rouge, nb_vert et nb_jaune.
Cette fonction renvoie le booléen True si "rouge" apparaît au plus nb_rouge fois dans la file F, "vert" apparaît au plus nb_vert fois dans la file F et "jaune" apparaît au plus nb_jaune fois dans la file F. Elle renvoie False sinon. On pourra utiliser les fonctions précédentes.

Exercice 5

Le contenu de la pile P sera

Python
| "rouge" |
| "vert"  |
| "jaune" |
| "rouge" |
| "jaune" |
 _________
Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def taille_file(F):
    """File -> Int"""
    F_temp = creer_file_vide()
    n = 0
    while not est_vide(F):
        enfiler(F_temp, defiler(F))
        n += 1
    while not est_vide(F_temp):
        enfiler(F, defiler(F_temp))
    return n
Python
1
2
3
4
5
6
7
8
9
def former_pile(F):
    """File -> Pile"""
    P_temp = creer_pile_vide()
    P = creer_pile_vide()
    while not est_vide(F):
        empiler(P_temp, defiler(F))
    while not est_vide(P_temp):
        empiler(P, depiler(P_temp))
    return P
Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def nb_elements(F, elt):
    """File, Int -> Int"""
    F_temp = creer_file_vide()
    n = 0
    while not est_vide(F):
        val = defiler(F)
        if val == elt:
            n += 1
        enfiler(F_temp, val)
    while not est_vide(F_temp):
        enfiler(F, deFiler(F_temp))
    return n
Python
1
2
3
4
5
def verifier_contenu(F, nb_rouge, nb_vert, nb_jaune):
    """File, Int, Int, Int -> Bool"""
    return nb_elements(F, "rouge") <= nb_rouge and \
           nb_elements(F, "vert") <= nb_vert and \
           nb_elements(F, "jaune") <= nb_jaune

Exercice 6⚓︎

Exercice 2 du sujet Centres Étrangers J1 - 2022 (Sujet complet en pdf)

Cet exercice porte sur les structures de données (files et la programmation objet en langage python)

Un supermarché met en place un système de passage automatique en caisse. Un client scanne les articles à l’aide d’un scanner de code-barres au fur et à mesure qu’il les ajoute dans son panier.
Les articles s’enregistrent alors dans une structure de données.

La structure de données utilisée est une file définie par la classe Panier, avec les primitives habituelles sur la structure de file.
Pour faciliter la lecture, le code de la classe Panier n’est pas écrit.

Python
class Panier():
    def __init__(self):
        """Initialise la file comme une file vide."""

    def est_vide(self):
        """Renvoie True si la file est vide, False sinon."""

    def enfiler(self, e):
        """Ajoute l'élément e en dernière position de la file, ne renvoie rien."""

    def defiler(self):
        """Retire le premier élément de la file et le renvoie."""

Le panier d’un client sera représenté par une file contenant les articles scannés. Les articles sont représentés par des tuples (code_barre, designation, prix, horaire_scan) où

  • code_barre est un nombre entier identifiant l’article ;
  • designation est une chaine de caractères qui pourra être affichée sur le ticket de caisse ;
  • prix est un nombre décimal donnant le prix d’une unité de cet article ;
  • horaire_scan est un nombre entier de secondes permettant de connaitre l’heure où l’article a été scanné.

1. On souhaite ajouter un article dont le tuple est le suivant
(31002, "café noir", 1.50, 50525).
Ecrire le code utilisant une des quatre méthodes ci-dessus permettant d’ajouter l’article à l’objet de classe Panier appelé panier1.

2. On souhaite définir une méthode remplir(panier_temp) dans la classe Panier permettant de remplir la file avec tout le contenu d’un autre panier panier_temp qui est un objet de type Panier.

Recopier et compléter le code de la méthode remplir en remplaçant chaque ... par la primitive de file qui convient.

Python
def remplir(self, panier_temp): 
    while not panier_temp. ...:
        article = panier_temp. ...
        self ...    (article)

3. Pour que le client puisse connaitre à tout moment le montant de son panier, on souhaite ajouter une méthode prix_total() à la classe Panier qui renvoie la somme des prix de tous les articles présents dans le panier.
Ecrire le code de la méthode prix_total. Attention, après l’appel de cette méthode, le panier devra toujours contenir ses articles.

4. Le magasin souhaite connaitre pour chaque client la durée des achats. Cette durée sera obtenue en faisant la différence entre le champ horaire_scan du dernier article scanné et le champ horaire_scan du premier article scanné dans le panier du client. Un panier vide renverra une durée égale à zéro. On pourra accepter que le panier soit vide après l’appel de cette méthode.

Ecrire une méthode duree_courses de la classe Panier qui renvoie cette durée.

Exercice 6

Il faut écrire :

Python
panier_1.enfile((31002, "café noir", 1.50, 50525))
Python
1
2
3
4
def remplir(self, panier_temp):
    while not panier_temp.est_vide():
        article = panier_temp.defile()
        self.enfile(article)
Python
1
2
3
4
5
6
7
8
9
def prix_total(self):
    total = 0
    panier_temp = Panier()
    while not self.est_vide():
        article = self.defile()
        total += article[2]
        panier_temp.enfile(article)
    self.remplir(panier_temp)
    return total
Python
1
2
3
4
5
6
7
def duree_passage_en_caisse(self):
    if self.est_vide():
        return None
    horaire_premier = self.defile()[3]
    while not self.est_vide():
        horaire_dernier = self.defile()[3]
    return horaire_dernier - horaire_premier

Exercice 7⚓︎

Exercice 3 du sujet Centres Etrangers J1 - 2023 (Sujet complet en pdf)

Jeu du Simon

Cet exercice porte sur les structures de Files

Simon est un jeu de société électronique de forme circulaire comportant quatre grosses touches de couleurs différentes : rouge, vert, bleu et jaune.

Le jeu joue une séquence de couleurs que le joueur doit mémoriser et répéter ensuite. S’il réussit, une couleur parmi les 4 est ajoutée à la fin de la séquence. La nouvelle séquence est jouée depuis le début et le jeu continue. Dès que le joueur se trompe, la séquence est vidée et réinitialisée avec une couleur et une nouvelle partie commence.

Exemple de séquence jouée : rouge \(\rightarrow\) bleu \(\rightarrow\) rouge \(\rightarrow\) jaune \(\rightarrow\) bleu

Dans cet exercice nous essaierons de reproduire ce jeu. Les quatre couleurs sont stockées dans un tuple nommé couleurs : couleurs = ("bleu", "rouge", "jaune", "vert")
Pour stocker la séquence à afficher nous utiliserons une structure de file que l’on nommera sequence tout au long de l’exercice.
La file est une structure linéaire de type FIFO (First In First Out). Nous utiliserons durant cet exercice les fonctions suivantes :

Structure de données abstraite : File

  • creer_file_vide() : renvoie une file vide
  • est_vide(f) : renvoie True si f est vide, False sinon
  • enfiler(f, element) : ajoute element en queue de f
  • defiler(f) : retire l'élément en tête de f et le renvoie
  • taille(f) : renvoie le nombre d'éléments de f

En fin de chaque séquence, le Simon tire au hasard une couleur parmi les 4 proposées. On utilisera la fonction randint(a,b) de la bibliothèque random qui permet d’obtenir un nombre entier compris entre a inclus et b inclus pour le tirage aléatoire.
Exemple : randint(1,5) peut renvoyer 1, 2, 3, 4 ou 5.

1. Recopier et compléter, sur votre copie, les des lignes 3 et 4 de la fonction ajout(f) qui permet de tirer au hasard une couleur et de l’ajouter à une séquence. La fonction ajout prend en paramètre la séquence f ; elle renvoie la séquence f modifiée (qui intègre la couleur ajoutée au format chaîne de caractères).

Python
1
2
3
4
5
        def ajout(f):
            couleurs = ("bleu", "rouge", "jaune", "vert")
            indice = randint(..., ...)
            enfiler(..., ...)
            return f

En cas d’erreur du joueur durant sa réponse, la partie reprend au début ; il faut donc vider la file sequence pour recommencer à zéro en appelant vider(sequence) qui permet de rendre la file sequence vide sans la renvoyer.

2. Ecrire la fonction vider qui prend en paramètre une séquence f et la vide sans la renvoyer.

Le Simon doit afficher successivement les différentes couleurs de la séquence.
Ce rôle est confié à la fonction affich_seq(sequence), qui prend en paramètre la file de couleurs sequence, définie par l’algorithme suivant :

  • on ajoute une nouvelle couleur à sequence ;
  • on affiche les couleurs de la séquence, une par une, avec une pause de 0,5 s entre chaque affichage.

Une fonction affichage(couleur) (dont la rédaction n’est pas demandée dans cet exercice) permettra l’affichage de la couleur souhaitée avec couleur de type chaîne de caractères correspondant à une des 4 couleurs.
La temporisation de 0,5 s sera effectuée avec la commande time.sleep(0.5). Après l’exécution de la fonction affich_seq, la file sequence ne devra pas être vidée de ses éléments.

3. Recopier et compléter, sur la copie, les ... des lignes 4 à 10 de la fonction affich_seq(sequence) ci-dessous :

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def affich_seq(sequence):
    stock = creer_file_vide()
    ajout(sequence)
    while not est_vide(sequence):
        c = ...
        ...
        time.sleep(0.5)
        ...
    while ...:
        ...
4. Cette question est indépendante des précédentes : bien qu’elle fasse appel aux fonctions construites précédemment, elle peut être résolue même si le candidat n’a pas réussi toutes les questions précédentes.

Nous allons ici créer une fonction tour_de_jeu(sequence) qui gère le déroulement d’un tour quelconque de jeu côté joueur. La fonction tour_de_jeu prend en paramètre la file de couleurs sequence, qui contient un certain nombre de couleurs.

  • Le jeu électronique Simon commence par ajouter une couleur à la séquence et affiche l’intégralité de la séquence.
  • Le joueur doit reproduire la séquence dans le même ordre. Il choisit une couleur via la fonction saisie_joueur().
  • On vérifie si cette couleur est conforme à celle de la séquence.
  • S’il s’agit de la bonne couleur, on poursuit sinon on vide sequence. Si le joueur arrive au bout de la séquence, il valide le tour de jeu et le jeu se poursuit avec un nouveau tour de jeu, sinon le joueur a perdu et le jeu s’arrête.

La fonction tour_de_jeu s’arrête donc si le joueur a trouvé toutes les bonnes couleurs de sequence dans l’ordre, ou bien dès que le joueur se trompe.

Après l’exécution de la fonction tour_de_jeu, la file sequence ne devra pas être vidée de ses éléments en cas de victoire.

a. Afin d’obtenir la fonction tour_de_jeu(sequence) correspondant au comportement décrit ci-dessus, recopier le script ci-dessous et

  • Compléter les ...
  • Choisir parmi les propositions de syntaxes suivantes lesquelles correspondent aux ZONES A, B, C, D, E et F figurant dans le script et les y remplacer (il ne faut donc en choisir que six parmi les onze) :
Python
vider(sequence) 
defiler(sequence) 
enfiler(sequence,c_joueur) 
enfiler(stock,c_seq) 
enfiler(sequence, defiler(stock)) 
enfiler(stock, defiler(sequence)) 
affich_seq(sequence)
while not est_vide(sequence): 
while not est_vide(stock):
if not est_vide(sequence): 
if not est_vide(stock):

zones exo7

b. Proposer une modification pour que la fonction se répète si le joueur trouve toutes les couleurs de la séquence (dans ce cas, une nouvelle couleur est ajou- tée) ou s’il se trompe (dans ce cas, la séquence est vidée et se voit ajouter une nouvelle couleur). On pourra ajouter des instructions qui ne sont pas proposées dans la question a.

Exercice 7

Correction Q1.
Python
1
2
3
4
5
def ajout(f):
    couleurs = ("bleu", "rouge", "jaune", "vert")
    indice = randint(0, 3)
    enfiler(f, couleur[indice])
    return f
Correction Q2.
Python
def vider(f):
    while not est_vide(f):
        defiler(f)
Correction Q3.
Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def affich_seq(sequence):
    stock = creer_file_vide()
    ajout(sequence)
    while not est_vide(sequence):
        c = defiler(sequence)
        affichage(c)
        time.sleep(0.5)
        enfiler(stock, c)
    while not est_vide(stock):
        enfiler(sequence, defiler(stock))
Correction Q4.a.
Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def tour_de_jeu(sequence):
    affich_seq(sequence)
    stock = creer_file_vide()
    while not est_vide(sequence):
        c_joueur = saisie_joueur()
        c_seq = defiler(sequence)
        if c_joueur == c_seq:
            enfiler(stock, c_seq)
        else:
            vider(sequence)
    while not est_vide(stock):
        enfiler(sequence, defiler(stock))
Correction Q4.b.

Question bizarre...

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def tour_de_jeu_modifie(sequence):
    while True:
        affich_seq(sequence)
        stock = creer_file_vide()
        while not est_vide(sequence):
            c_joueur = saisie_joueur()
            c_seq = defiler(sequence)
            if c_joueur == c_seq:
                enfiler(stock, c_seq)
            else:
                vider(sequence)
                vider(stock)
        while not est_vide(stock):
            enfiler(sequence, defiler(stock))

ou bien

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def tour_de_jeu_modifie(sequence):
    affich_seq(sequence)
    stock = creer_file_vide()
    while not est_vide(sequence):
        c_joueur = saisie_joueur()
        c_seq = defiler(sequence)
        if c_joueur == c_seq:
            enfiler(stock, c_seq)
        else:
            vider(sequence)
            print("Perdu ! On rejoue !")
            tour_de_jeu_modifie(sequence)
    while not est_vide(stock):
        enfiler(sequence, defiler(stock))
    tour_de_jeu_modifie(sequence)

Crédits⚓︎

Auteur : Gilles Lassus