Aller au contenu

TP - Algorithmes de référence☘

Si nécessaire, téléchargez le module TAD_Listes.py qui contient une implémentation de liste et placez ce module dans le dossier [A02-Listes].

L'interface est celle donnée dans le cours :

Méthode/Opérations Description
L = Liste() Initialisation d'une liste vide
est_vide(L) Renvoie True si la liste L est vide, False sinon.
inserer_en_tete(elt, L) « Ajoute » un nouvel élément en tête de la liste,
c'est-à-dire renvoie le couple (elt, L)
tete(L) Renvoie la valeur de l'élément en tête (le premier élément du couple)
queue(L) Renvoie la liste située en queue (le second élément du couple)

Attention

Cette interface n'est pas orientée objet, elle s'utilise de la même manière que dans les exemples du cours et dans le TD.

Préambule☘

Ce TP a pour but de programmer certains des algorithmes de référence étudiés en classe de 1ère NSI, en utilisant la structure de Liste.

Téléchargez le fichier « à trous » TPA02.21.py (clic droit -> [Enregistrer sous]) et enregistrez-le dans ce dossier.

Partie 1 - Liste triée ?☘

Complétez la définition récursive (vous n'avez pas le choix !) de la fonction est_triee() qui prend en paramètre une liste et qui renvoie True si les éléments de la liste sont triés par ordre croissant et False sinon.

1
2
3
4
5
6
def est_triee(lst):
    """
    lst - Liste d'éléments munis d'une relation d'ordre
    Sortie: bool - True si les éléments de lst sont classés par ordre croissant,
            False sinon
    """

Plan de test

>>> L1 = (5, (2, (1, (4, (3, ())))))
>>> est_triee(L1)
False

>>> L2 = (0, (2, (4, (6, (8, ())))))
>>> est_triee(L2)
True

Partie 2 - Insérer dans une liste triée☘

Complétez la définition récursive (toujours pas le choix !) de la fonction inserer() qui prend en paramètre une liste triée et qui insère l'élément passé en paramètre à sa bonne place dans la liste (la liste doit rester triée).

1
2
3
4
5
6
def inserer(lst, elt):
    """
    lst - Liste d'éléments triés par ordre croissant
    elt - Un élément
    Sortie: Liste - lst dans laquelle elt a été inséré à la bonne place
    """

Plan de test

>>> L2 = (0, (2, (4, (6, (8, ())))))
>>> L2 = inserer(L2, 3)
>>> L2 = inserer(L2, -1)
>>> L2 = inserer(L2, 11)
>>> L2
(-1, (0, (2, (3, (4, (6, (8, (11, ()))))))))

Partie 3 - Tri par insertion☘

Complétez la définition récursive de la fonction tri_insertion() qui prend en paramètre une liste et qui renvoie la liste triée par insertion.

1
2
3
4
5
def tri_insertion(lst):
    """
    lst - Liste d'éléments munis d'une relation d'ordre
    Sortie: Liste - lst dont les éléments sont triés par ordre croissant
    """

Plan de test

>>> L1 = (3, (4, (1, (2, (5, ())))))
>>> tri_insertion(L1)
(1, (2, (3, (4, (5, ())))))

Partie 4 - Décalages☘

En utilisant éventuellement des fonctions supplémentaires à celles de l'interface de base, programmez :

  1. une fonction de décalage à gauche (la liste 1 - 2 - 3 - 4 devient 2 - 3 - 4 - 1) ;
  2. une fonction de décalage à droite (la liste 1 - 2 - 3 - 4 devient 4 - 1 -2 - 3).