Aller au contenu

Exercices pour s'entraîner☘

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 [A02-Listes] avec le nom donné à l'exercice : ProgA02.51.py, ProgA02.52.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_Listes.py qui contient une implémentation de liste et placez ce module dans votre répertoire de travail.
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.

ProgA02.51 - Liste d'entiers successifs☘

Complétez la définition (récursive ou non, c'est vous qui choisissez) de la fonction liste_entiers() qui prend en paramètre un entier strictement positif n et qui renvoie la liste des entiers de 1 à n dans cet ordre.

1
2
3
4
5
def liste_entiers(n):
    """
    n - int, entier strictement positif
    Sortie: Liste - Liste constituée des entiers de 1 à n, dans cet ordre
    """

Exemple

>>> L1 = liste_entiers(5)

>>> L1
(1, (2, (3, (4, (5, ())))))
Une solution itérative
1
2
3
4
5
6
7
8
9
def liste_entiers(n):
    """
    n - int, entier strictement positif
    Sortie: Liste - Liste constituée des entiers de 1 à n, dans cet ordre
    """
    lst = Liste()
    for i in range(n):
        lst = inserer_en_tete(n-i, lst)
    return lst
Une solution récursive

On ajoute un paramètre « invisible », initialisé par défaut à la valeur 1. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def liste_entiers_rec(n, i=1):
    """
    n - int, entier strictement positif
    i - int
    Sortie: Liste - Liste constituée des entiers de 1 à n, dans cet ordre
    """
    if i == n:
        return inserer_en_tete(i, Liste())
    else:
        return inserer_en_tete(i, liste_entiers_rec(n, i+1))

ProgA02.52 - Dernier élément d'une liste☘

Programmez la définition récursive (ici, vous n'avez pas le choix !) de la fonction dernier() qui prend en paramètre une liste et qui renvoie le dernier élément de cette liste.

1
2
3
4
5
def dernier(lst) :
    """
    lst – Liste non vide d'éléments
    Sortie: dernier élément de la liste lst
    """

Il faudra réaliser un test de vérification pour la liste vide.

Exemple

>>> L1 = liste_entiers(5)

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

>>> dernier(L1)
5

>>> L2 = Liste()

>>> dernier(L2)
AssertionError: Liste vide

Attention

Cette fonction a été étudiée dans le cours.
Essayez de retrouver comment faire avant de céder à la facilité de recopier votre cahier...

Une solution
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def dernier(lst) :
    """
    lst – Liste non vide d'éléments
    Sortie: dernier élément de la liste lst
    """
    assert not est_vide(lst), 'Liste vide'
    if est_vide(queue(lst)) :
        return tete(lst)
    else :
        return(dernier(queue(lst)))

ProgA02.53 - Insérer en fin de liste☘

Programmez la définition récursive (ici, vous n'avez pas le choix !) de la fonction inserer_en_fin() qui prend en paramètre un élément et une liste et qui renvoie la liste dans laquelle l'élément a été inséré en dernière position.

1
2
3
4
5
6
def inserer_en_fin(elt, lst):
    """
    elt – une valeur de même type que les éléments de lst
    lst – Liste d'éléments
    Sortie: Liste - lst dans laquelle elt est insérée en dernier
    """

Exemple

>>> L1 = (5, (8, (3, (7, ()))))

>>> L1 = inserer_en_fin(2, L1)

>>> L1
(5, (8, (3, (7, (2, ())))))

Attention

Cette fonction a été étudiée en Travaux Dirigés.
Essayez de retrouver comment faire avant de céder à la facilité de recopier votre cahier...

Une solution
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def inserer_en_fin(elt, lst):
    """
    elt – une valeur de même type que les éléments de lst
    lst – Liste d'éléments
    Sortie: Liste - lst dans laquelle elt est insérée en dernier
    """
    if est_vide(lst):
        return inserer_en_tete(elt, lst)
    else:
        debut = tete(lst)
        fin = queue(lst)
        return inserer_en_tete(debut, inserer_en_fin(elt, fin))

ProgA02.54 - Insérer en k-ième position☘

Programmez la définition récursive (ici, vous n'avez pas le choix !) de la fonction insere_position() qui prend en paramètre un élément, un entier k strictement positif et une liste et qui renvoie la liste dans laquelle l'élément a été inséré à l'indice k.

1
2
3
4
5
6
7
def insere_position(elt, k, lst):
    """
    elt – une valeur de même type que les éléments de lst
    k – int, position de l'insertion
    lst – Liste non vide d'éléments
    Sortie: Liste - lst dans laquelle elt est inséré à l'indice k
    """

Exemple

>>> L1 = (5, (8, (3, (7, ()))))

>>> L1 = insere_position(0, 2, L1)

>>> L1
(5, (8, (0, (3, (7, (2, ()))))))

>>> L1 = insere_position(0, 6, L1)
AssertionError: Indice trop élevé

Il faudra réaliser un test de vérification pour la valeur de l'indice.

Attention

Cette fonction a été étudiée en Travaux Dirigés.
Essayez de retrouver comment faire avant de céder à la facilité de recopier votre cahier...

Une solution
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def insere_position(elt, k, lst):
    """
    elt – une valeur de même type que les éléments de lst
    k – int, position de l'insertion
    lst – Liste non vide d'éléments
    Sortie: Liste - lst dans laquelle elt est inséré à l'indice k
    """
    assert not (est_vide(lst) and k > 0), "Indice trop élevé"
    if k == 0:
        return inserer_en_tete(elt, lst)
    else:
        debut = tete(lst)
        fin = queue(lst)
        return inserer_en_tete(debut, insere_position(elt, k-1, fin))

ProgA02.55 - Indice d'un élément☘

Programmez la définition récursive (ici, vous n'avez pas le choix !) de la fonction indice() qui prend en paramètre un élément et une liste et qui renvoie l'indice de cet élément dans la liste. S'il n'est pas présent, la fonction renvoie -1.

1
2
3
4
5
6
7
def indice(elt, lst, i = 0):
    """
    elt – une valeur de même type que les éléments de lst
    lst – Liste non vide d'éléments
    i - int, initialisé par défaut à 0
    Sortie: int - indice i de elt s'il est présent dans lst, -1 sinon
    """

Exemple

>>> L1 = (5, (8, (3, (7, ()))))

>>> indice(3, L1)
2

>>> indice(0, L1)
-1
Une solution
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def indice(elt, lst, i = 0):
    """
    elt – une valeur de même type que les éléments de lst
    lst – Liste non vide d'éléments
    i - int, initialisé par défaut à 0
    Sortie: int - indice i de elt s'il est présent dans lst, -1 sinon
    """
    if est_vide(lst):
        return -1
    else:
        if elt == tete(lst):
            return i
        else:
            return indice(elt, queue(lst), i+1)

ProgA02.56 - Nombre d'occurences d'un élément☘

Programmez la définition récursive (ici, vous n'avez pas le choix !) de la fonction nb_occurrences() qui prend en paramètre un élément et une liste et qui renvoie le nombre de fois où cet élément est présent dans la liste.

1
2
3
4
5
6
def nb_occurrences(elt, lst):
    """
    elt – une valeur de même type que les éléments de lst
    lst – Liste non vide d'éléments
    Sortie: int - nombre d'occurences de elt dans lst
    """

Exemple

>>> L2 = (2, (3, (5, (1, (4, (4, (7, (2, (4, (2, ()))))))))))

>>> nb_occurrences(4, L2)
3

>>> nb_occurrences(5, L2)
1
Une solution
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def nb_occurrences(elt, lst):
    """
    elt – une valeur de même type que les éléments de lst
    lst – Liste non vide d'éléments
    Sortie: int - nombre d'occurences de elt dans lst
    """
    if est_vide(lst):
        return 0
    else:
        if elt == tete(lst):
            return 1 + nb_occurrences(elt, queue(lst))
        else:
            return nb_occurrences(elt, queue(lst))

ProgA02.57* - Moyenne des éléments☘

Complétez la définition récursive (ici, vous n'avez pas le choix !) de la fonction moyenne() qui prend en paramètre une liste d'entiers et son nombre d'éléments et qui renvoie la moyenne (flottant) des éléments de cette liste.

1
2
3
4
5
6
def moyenne(lst, taille):
    """
    lst - Liste d'entiers
    taille - int, nombre d'éléments de lst
    Sortie: float - Moyenne des éléments de lst
    """

On admettra que l'utilisateur est « intelligent », c'est-à-dire que la variable taille correspond bien au nombre d'élément de la liste lst passée en argument.

Plan de test

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

>>> moyenne(L1, 5)
3.0
Une piste

La somme éléments d'une liste s'écrit, de façon récursive : 

somme(éléments) = premier_élément + somme(éléments_restant)
Essayez d'écrire de même le calcul de la moyenne.

Une solution
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def moyenne(lst, taille):
    """
    lst - Liste d'entiers
    taille - int, nombre d'éléments de lst
    Sortie: float - Moyenne des éléments de lst
    """
    if est_vide(lst):
        return 0
    else:
        debut = tete(lst)
        fin = queue(lst)
        return (debut + moyenne(fin, taille-1) * (taille-1))/taille

ProgA02.58 - Égalité de deux listes☘

Complétez la définition récursive (ici, vous n'avez pas le choix !) de la fonction sont_egales() qui prend en paramètre deux listes (pas forcément de même taille...) et qui renvoie True si ces deux listes ont exactement les mêmes éléments, dans le même ordre, et qui renvoie False sinon.

1
2
3
4
5
def sont_egales(lst1, lst2):
    """
    lst1, lst2 - Liste
    Sortie: bool - True si lst1 et lst2 contiennent les mêmes éléments dans le même ordre, False sinon
    """

Plan de test

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

>>> L2 = (2, (3, (5, (1, (4, (4, (7, (2, (4, (2, ()))))))))))

>>> sont_egales(L1, L2)
False

>>> sont_egales(L1, L1)
True
Une solution
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def sont_egales(lst1, lst2):
    """
    lst1, lst2 - Liste
    Sortie: bool - True si lst1 et lst2 contiennent les mêmes éléments dans le même ordre, False sinon
    """
    if est_vide(lst1) and not est_vide(lst2) :
        return False
    if est_vide(lst2) and not est_vide(lst1) :
        return False
    if est_vide(lst1) and est_vide(lst2) :
        return True
    if tete(lst1) != tete(lst2):
        return False
    else:
        return sont_egales(queue(lst1), queue(lst2))

ProgA02.59 - Concaténer deux listes☘

Complétez la définition récursive (ici, vous n'avez pas le choix !) de la fonction concatener() qui prend en paramètre deux listes (pas forcément de même taille...) et qui renvoie une liste constituée des éléments de la première liste suivis des éléments de la seconde liste.

1
2
3
4
5
def concatener(lst1, lst2):
    """
    lst1, lst2 - Liste
    Sortie: Liste - Liste constituée des éléments de lst1 suivis des éléments de lst2.
    """

Plan de test

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

>>> L2 = (2, (3, (5, (1, (4, (4, (7, (2, (4, (2, ()))))))))))

>>> L3 = concatener(L1, L2)

>>> L3
(1, (2, (3, (4, (5, (2, (3, (5, (1, (4, (4, (7, (2, (4, (2, ())))))))))))))))
Une solution
1
2
3
4
5
6
7
8
9
def concatener(lst1, lst2):
    """
    lst1, lst2 - Liste
    Sortie: Liste - Liste constituée des éléments de lst1 suivis des éléments de lst2.
    """
    if estVide(lst1):
        return lst2
    else:
        return insererEnTete(tete(lst1), concatener(queue(lst1), lst2))

ProgA02.60 - Renverser une liste☘

Complétez la définition récursive (à nouveau, vous n'avez pas le choix !) de la fonction renverser() qui prend en paramètre une liste et qui renvoie une liste renversée constituée des éléments de la liste passée en paramètre.

1
2
3
4
5
def renverser(lst, L = Liste()):
    """
    lst - Liste d'éléments
    Sortie: Liste - La liste lst dans laquelle les éléments ont été renversés
    """

Plan de test

>>> L1 = (5, (2, (1, (4, (3, ())))))
>>> L2 = renverser(L1)
>>> L2
(3, (4, (1, (2, (5, ()))))))
Une solution
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def renverser(lst, L=None):
    """
    lst - Liste d'éléments
    Sortie: Liste - La liste lst dans laquelle les éléments ont été renversés
    """
    if L is None:
        L = Liste()
    if est_vide(lst):
        return L
    else:
        L = inserer_en_tete(tete(lst), L)
        return renverser(queue(lst), L)