Aller au contenu

Exercices pour s'entraîner sur les Files☘

Prenez l'habitude de revenir vous entraîner régulièrement avec ces exercices tout au long de l'année. Ils sont généralement accompagnés de pistes et de leur solution pour vous permettre de progresser.

Rappels

  • Chaque programme Python doit être sauvegardé sous forme de fichier texte avec l'extension .py.
    Enregistrez ce fichier dans le dossier [A01-Piles_Files] avec le nom donné à l'exercice : ProgA01.62.py, ProgA01.63.py, etc...
  • Pour exécuter ce programme, il suffit de le sauvegarder puis d'appuyer sur la touche [F5].

Préambule☘

Téléchargez le module TAD_Files.py qui contient une implémentation objet de file. Placez ce module dans le répertoire de travail [A01-Piles_Files].
L'interface est celle donnée dans le cours :

Méthode/Opérations Description
F = File() Initialisation d'une file vide.
F.est_vide() Renvoie True si la file F est vide, False sinon.
F.enfiler(elt) Enfile un nouvel élément en queue de la file.
F.defiler() Lorsque la file F n'est pas vide, supprime le premier élément de la file et renvoie la valeur de cet élément.

L'affichage de la file avec la fonction print() est aussi implémenté.

Consignes générales☘

Consignes communes

Les fonctions des programmes A01.62 jusqu'à A01.65 peuvent être programmées dans le même fichier Python.

Il n'est pas utile de chercher à comprendre comment la structure de file a été implémentée pour réaliser ces programmes.

Exercice A01.61☘

Réalisez un plan de test de l'interface du module TAD_Files.py.

Une réponse possible
>>> f = File()    
>>> f.est_vide()
True

>>> f.enfiler(7)    
>>> f.enfiler(4)    
>>> f.enfiler(3)    
>>> f    
3 -> 4 -> 7

>>> f.defiler()
7

>>> f.enfiler(8)

>>> f    
8 -> 3 -> 4

>>> f.est_vide()
False

>>> f2 = File()      
>>> f2.defiler()
AssertionError: La file est vide

ProgA01.62☘

Complétez le code de la fonction file_alea() qui prend en paramètres trois entiers borne_inf, borne_sup et nb. Cette fonction renvoie une file contenant nb entiers aléatoires générés entre borne_inf et borne_sup.

1
2
3
4
5
6
7
def file_alea(borne_inf, borne_sup, nb):
    """
    borne_inf, borne_sup - int, entiers tels que borne_inf < borne_sup
    nb - int, entier strictement positif
    Sortie: File - file constituée de nb entiers aléatoires générés entre borne_inf et borne_sup
    """
    pass

Exemple de tests

>>> f = file_alea(0, 50, 5)
>>> f
42 -> 23 -> 13 -> 12 -> 17
Une solution

Il ne faut pas oublier d'importer la fonction randint du module random...

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
from TAD_Files import *
from random import randint

def file_alea(borne_inf, borne_sup, nb):
    """
    borne_inf, borne_sup - int, entiers tels que borne_inf < borne_sup
    nb - int, entier strictement positif
    Sortie: File - file constituée de nb entiers aléatoires générés entre borne_inf et borne_sup
    """
    f = File()
    for i in range(nb):
        f.enfiler(randint(borne_inf, borne_sup))
    return f

ProgA01.63☘

  1. Dans la console, testez les instructions ci-dessous (les réponses de la console ont été volontairement effacées).
    Que pouvez-vous constater ?

    >>> f = file_alea(0, 50, 5)
>>> f

>>> g = f    
>>> g

>>> g.defiler()

>>> g

>>> f
    Une solution

    On peut constater que l'affectation « = » a simplement rajouté un alias (une étiquette) supplémentaire à la file f. L'affectation ne crée donc pas une nouvelle file et toute modification en utilisant l'alias k entraîne de facto une modification sous l'alias f. 

    >>> f = file_alea(0, 50, 5)
>>> f
27 -> 21 -> 17 -> 0 -> 37

>>> g = f
>>> g
27 -> 21 -> 17 -> 0 -> 37

>>> g.defiler()
37

>>> g
27 -> 21 -> 17 -> 0

>>> f
27 -> 21 -> 17 -> 0
    Il faut donc créer une fonction de copie de File pour éviter cet inconvénient...

  2. Complétez le code de la fonction copie_file() qui prend en paramètre une file f et qui renvoie une autre file contenant les mêmes éléments que f dans le même ordre. 

    1
2
3
4
5
    def copie_file(f):
    """
    f - File
    Sortie: File - file constituée des mêmes éléments que f, dans le même ordre et sans modifier f
    """

    Exemple de tests

    >>> f = file_alea(0, 50, 5)
>>> f
27 -> 21 -> 17 -> 0 -> 37

>>> f2 = copie_file(f)
>>> f2
27 -> 21 -> 17 -> 0 -> 37

>>> f2.defiler()
37

>>> f2
27 -> 21 -> 17 -> 0

>>> f
27 -> 21 -> 17 -> 0 -> 37

    Attention

    La file f ne doit pas être modifiée par effet de bord.

    Une piste

    Utilisez une file temporaire.

    Une autre piste

    Enfilez les éléments de la file d'origine dans la file temporaire puis défilez la file temporaire pour remplir la file d'origine et la file « copie ».

    Une solution
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
    def copie_file(f):
    """
    f - File
    Sortie: File - file constituée des mêmes éléments que f, dans le même ordre et sans modifier f
    """
    temp = File()
    resultat = File()
    while not f.est_vide():
        element = f.defiler()
        temp.enfiler(element)

    while not temp.est_vide():
        element = temp.defiler()
        f.enfiler(element)
        resultat.enfiler(element)

    return resultat

ProgA01.64☘

Complétez le code de la fonction longueur_file() qui prend en paramètre une file et qui renvoie le nombre d'éléments de cette file.

1
2
3
4
5
6
def longueur_file(f):
    """
    f - File
    Sortie: int - nombre d'éléments de la file f, sans modifier cette file
    """
    pass

Exemple de tests

>>> f = file_alea(0, 50, 5)
>>> longueur_file(f)
5

Attention

Cette file ne doit pas être modifiée par effet de bord.

Une piste

La même que celle de l'exercice précédent.

Une solution
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def longueur_file(f):
    """
    f - File
    Sortie: int - nombre d'éléments de la file f, sans modifier cette file
    """
    temp = File()
    longueur = 0
    while not f.est_vide():
        element = f.defiler()
        temp.enfiler(element)
        longueur += 1

    while not temp.est_vide():
        element = temp.defiler()
        f.enfiler(element)

    return longueur

ProgA01.65☘

Dans cet exercice, il faudra aussi importer la structure de pile présente dans le module TAD_Piles.py.

  1. Complétez le code de la fonction inverser_file() qui prend en paramètre une file et qui inverse les éléments de cette file par effet de bord. Cette fonction ne renvoie rien.

    1
2
3
4
5
6
    def inverser_file(f):
    """
    f - File
    Sortie: None - Les éléments de la file f sont inversés (effet de bord)
    """
    pass

    Exemple de tests

    >>> f = file_alea(0, 50, 5)
>>> f
12 -> 36 -> 15 -> 27 -> 25

>>> inverser_file(f)
>>> f
25 -> 27 -> 15 -> 36 -> 12

    Attention

    Seul l'usage des files et des piles est autorisé.

    Une piste

    L'introdution vous l'a déjà conseillé : utilisez une pile temporaire.

    Une solution
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
    def inverser_file(f):
    """
    f - File
    Sortie: None - Les éléments de la file f sont inversés (effet de bord)
    """
    temp = Pile()
    while not f.est_vide():
        element = f.defiler()
        temp.empiler(element)

    while not temp.est_vide():
        element = temp.depiler()
        f.enfiler(element)

  2. Complétez le code de la fonction echange_premier_dernier() qui prend en paramètre une file et qui échange, par effet de bord, le premier et le dernier élément de cette file. Cette fonction ne renvoie rien.

    1
2
3
4
5
6
    def echange_premier_dernier(f):
    """
    f - File
    Sortie: None - Le premier et le dernier élément de la file sont échangés (effet de bord)
    """
    pass

    Exemple de tests

    >>> f = file_alea(0, 50, 5)
>>> f
12 -> 36 -> 15 -> 27 -> 25

>>> echange_premier_dernier(f)
>>> f
25 -> 36 -> 15 -> 27 -> 12

>>> f = File()
>>> f.enfiler(3)
>>> echange_premier_dernier(f)
>>> f
3
    Une piste

    Utilisez la fonction inverser_file() en faisant attention aux nombres d'éléments de la file.

    Une solution
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
    def echange_premier_dernier(f):
    """
    f - File
    Sortie: None - Le premier et le dernier élément de la file sont échangés (effet de bord)
    """
    if not f.est_vide():
        premier = f.defiler()
        if not f.est_vide():
            inverser_file(f)
            dernier = f.defiler()
            f.enfiler(dernier)
            inverser_file(f)
            f.enfiler(premier)
    else:
        f.enfiler(premier)

  3. Testez votre réponse à l'exercice des tunnels magiques, inspiré du concours Castor Informatique 2013.

    Énoncé de l'exercice

    Un tunnel noir renverse l'ordre de la file, un tunnel blanc échange le premier et le dernier élément de la file.
    Quelle sera la file en sortie des trois tunnels ?

    Tunnels magiques

    Une solution
    >>> f = File()        
>>> f.enfiler('D')        
>>> f.enfiler('C')        
>>> f.enfiler('B')        
>>> f.enfiler('A')        
>>> f
A -> B -> C -> D

>>> inverser_file(f)        
>>> echange_premier_dernier(f)        
>>> inverser_file(f)        
>>> f
D -> B -> C -> A