14 - Parcours de liste

Exercice 0 : QCM – vérification des prérequis

Pour chaque question, une seule réponse est correcte.

1. Quelle est la valeur de L[2] si L = [10, 20, 30, 40] ?

  • A. 20
  • B. 30
  • C. 40
  • D. Une erreur IndexError
Correction

Réponse : B. En Python, les indices commencent à 0. Donc L[0] = 10, L[1] = 20, L[2] = 30.

  • A est faux : c’est L[1] (erreur : compter à partir de 1 au lieu de 0).
  • C est faux : c’est L[3].
  • D est faux : l’indice 2 est bien valide pour une liste de quatre éléments (indices 0, 1, 2, 3).

2. Que fait la boucle for x in L: ?

  • A. Elle parcourt les indices de L
  • B. Elle parcourt les éléments de L
  • C. Elle modifie chaque élément de L
  • D. Elle trie L
Correction

Réponse : B. La boucle for x in L: affecte successivement chaque élément de la liste L à la variable x.

  • A est faux : pour parcourir les indices, on écrit for i in range(len(L)):.
  • C est faux : modifier x dans la boucle ne modifie pas la liste (car x est une copie de la valeur).
  • D est faux : trier une liste se fait avec L.sort() ou sorted(L).

3. Quelle est la complexité d’une recherche séquentielle dans une liste de \(n\) éléments ?

  • A. \(O(1)\)
  • B. \(O(\log n)\)
  • C. \(O(n)\)
  • D. \(O(n^2)\)
Correction

Réponse : C. Dans le pire cas, il faut parcourir tous les \(n\) éléments (si l’élément cherché est le dernier ou n’est pas dans la liste). La complexité est donc linéaire.

  • A est faux : un accès en \(O(1)\) suppose de connaître l’indice (accès direct).
  • B est faux : c’est la complexité de la recherche dichotomique, qui nécessite une liste triée.
  • D est faux : un simple parcours linéaire n’est pas quadratique.

4. Que renvoie la fonction suivante pour comptage([3, 1, 3, 3, 2], 3) ?

def comptage(L, val):
    c = 0
    for x in L:
        if x == val:
            c += 1
    return c
  • A. 1
  • B. 2
  • C. 3
  • D. 5
Correction

Réponse : C. La fonction compte le nombre d’occurrences de val dans L. Ici, 3 apparaît aux indices 0, 2 et 3, soit trois fois.

  • A est faux : c’est le nombre d’occurrences de 2 (ou de 1), pas de 3.
  • B est faux : on a oublié de compter une occurrence.
  • D est faux : c’est la longueur de la liste, pas le nombre d’occurrences de 3.

Préambule

En programmation, il est de bonne pratique de documenter son code et de le tester sur quelques valeurs. Voici un exemple des deux pratiques sur la fonction somme suivante.

import doctest

def somme(maliste):
    """
    Fonction qui calcule la somme des nombres d'une liste non vide.

    Paramètre : une liste non vide
    Valeur renvoyée : la somme des éléments de la liste

    Exemples :
    >>> somme([3])
    3
    >>> somme([1, 2, 3, 4, 5])
    15
    >>> somme([12, -17, 3, -2, 11, -13, 6])
    0
    """

    s = 0
    for nombre in maliste:
        s = s + nombre
    return s

help(somme)
print(doctest.testmod())

Recopier ce code et l’exécuter pour observer ce qui se passe dans la console.

Vous vous inspirerez de cette façon de faire dans l’écriture des fonctions demandées dans les questions ci-dessous.

Exercice 1 : recherche d’un nombre dans une liste non triée

  1. Écrire une fonction est_element qui prend en paramètres un objet a et une liste L et retourne un booléen traduisant la véracité de l’affirmation « l’objet a est un élément de la liste L ».
  2. Modifier la fonction ci-dessus afin qu’elle retourne l’indice minimal de la liste correspondant à une occurrence de a.
  3. Même question pour trouver le nombre d’occurrences de a dans la liste.
Correction

1. Recherche d’appartenance :

def est_element(a, L):
    """
    Vérifie si a est dans la liste L.

    >>> est_element(3, [1, 2, 3, 4])
    True
    >>> est_element(5, [1, 2, 3, 4])
    False
    >>> est_element(1, [])
    False
    """
    for x in L:
        if x == a:
            return True
    return False

On parcourt la liste élément par élément. Dès qu’on trouve a, on renvoie True. Si on termine la boucle sans l’avoir trouvé, on renvoie False.

Piège courant : écrire else: return False dans la boucle, ce qui renvoie False dès le premier élément différent de a.

2. Recherche de l’indice :

def indice_element(a, L):
    """
    Renvoie l'indice de la première occurrence de a dans L.
    Renvoie -1 si a n'est pas dans L.

    >>> indice_element(3, [1, 2, 3, 4])
    2
    >>> indice_element(5, [1, 2, 3, 4])
    -1
    >>> indice_element(2, [2, 5, 2, 8])
    0
    """
    for i in range(len(L)):
        if L[i] == a:
            return i
    return -1

On parcourt les indices avec range(len(L)) pour pouvoir renvoyer l’indice correspondant.

3. Comptage des occurrences :

def nb_occurrences(a, L):
    """
    Renvoie le nombre d'occurrences de a dans L.

    >>> nb_occurrences(3, [1, 3, 2, 3, 3])
    3
    >>> nb_occurrences(5, [1, 2, 3])
    0
    """
    compteur = 0
    for x in L:
        if x == a:
            compteur += 1
    return compteur

On utilise le schéma de l’accumulateur : on initialise un compteur à 0, on l’incrémente à chaque occurrence trouvée, et on le renvoie à la fin.

Exercice 2 : recherche du maximum d’une liste

Écrire une fonction de recherche du maximum d’une liste de nombres. Elle prend en paramètre une liste de nombres et renvoie le maximum si la liste est non vide ; le message « La liste est vide » sinon.

Correction
def maximum(L):
    """
    Renvoie le maximum d'une liste de nombres.

    >>> maximum([3, 1, 7, 2, 5])
    7
    >>> maximum([-4, -1, -8])
    -1
    >>> maximum([42])
    42
    >>> maximum([])
    'La liste est vide'
    """
    if len(L) == 0:
        return "La liste est vide"

    maxi = L[0]
    for i in range(1, len(L)):
        if L[i] > maxi:
            maxi = L[i]
    return maxi

Principe : on initialise maxi avec le premier élément, puis on le met à jour à chaque fois qu’on trouve un élément plus grand.

Piège courant : initialiser maxi = 0. Cela échoue pour une liste de nombres négatifs (ex. [-4, -1, -8] renverrait 0 au lieu de -1).

Exercice 3 : recherche d’un élément dans une liste triée

Écrire une fonction de recherche dichotomique d’un nombre dans une liste triée de nombres. Elle prend en paramètres un nombre et une liste triée de nombres et renvoie l’indice du nombre s’il est présent dans la liste ; la valeur \(-1\) sinon.

Correction
def recherche_dicho(val, L):
    """
    Recherche dichotomique de val dans une liste triée L.
    Renvoie l'indice de val si trouvé, -1 sinon.

    >>> recherche_dicho(7, [1, 3, 5, 7, 9, 11])
    3
    >>> recherche_dicho(4, [1, 3, 5, 7, 9, 11])
    -1
    >>> recherche_dicho(1, [1, 3, 5, 7])
    0
    >>> recherche_dicho(7, [1, 3, 5, 7])
    3
    """
    gauche = 0
    droite = len(L) - 1

    while gauche <= droite:
        milieu = (gauche + droite) // 2
        if L[milieu] == val:
            return milieu
        elif L[milieu] < val:
            gauche = milieu + 1
        else:
            droite = milieu - 1

    return -1

Principe : on divise l’intervalle de recherche en deux à chaque étape :

  1. On calcule l’indice du milieu.
  2. Si L[milieu] == val, on a trouvé.
  3. Si L[milieu] < val, la valeur cherchée est dans la moitié droite : on ajuste gauche.
  4. Sinon, elle est dans la moitié gauche : on ajuste droite.

Complexité : à chaque itération, l’intervalle de recherche est divisé par deux. Il faut donc au plus \(\lfloor \log_2(n) \rfloor + 1\) comparaisons, soit une complexité en \(O(\log n)\).

Condition d’arrêt : la boucle s’arrête quand gauche > droite, ce qui signifie que l’intervalle de recherche est vide.

Exercice 4 : recherche d’un mot dans un texte

  1. Écrire une fonction isprefixe prenant en paramètres deux chaînes de caractères texte, mot et un entier i, et testant si mot est préfixe de texte[i:], autrement dit si mot a une occurrence dans texte à la place i. La fonction renverra un booléen. On ne s’autorisera pour ce faire que des comparaisons lettre à lettre.
  2. Utiliser la fonction isprefixe pour écrire une fonction cherche_occurrences donnant sous forme d’un tableau la liste des occurrences de mot dans texte. Les occurrences peuvent se chevaucher. Ainsi, dans « bonbonbon », il y a deux occurrences de « bonbon ».
Correction

1.

def isprefixe(texte, mot, i):
    """
    Teste si mot apparaît dans texte à la position i.

    >>> isprefixe("bonjour", "bon", 0)
    True
    >>> isprefixe("bonjour", "bon", 1)
    False
    >>> isprefixe("bonjour", "jour", 3)
    True
    >>> isprefixe("abc", "abcd", 0)
    False
    """
    if i + len(mot) > len(texte):
        return False
    for j in range(len(mot)):
        if texte[i + j] != mot[j]:
            return False
    return True

On vérifie d’abord que le mot ne dépasse pas la fin du texte, puis on compare caractère par caractère. Dès qu’une lettre diffère, on renvoie False.

2.

def cherche_occurrences(texte, mot):
    """
    Renvoie la liste des positions de mot dans texte.

    >>> cherche_occurrences("bonbonbon", "bonbon")
    [0, 3]
    >>> cherche_occurrences("abcabc", "abc")
    [0, 3]
    >>> cherche_occurrences("hello", "xyz")
    []
    """
    positions = []
    for i in range(len(texte) - len(mot) + 1):
        if isprefixe(texte, mot, i):
            positions.append(i)
    return positions

On teste chaque position i de 0 à len(texte) - len(mot). Pour "bonbonbon" et "bonbon" : on teste les positions 0, 1, 2, 3. À la position 0, "bonbon" correspond. À la position 3, "bonbon" correspond aussi (chevauchement avec la première occurrence). Résultat : [0, 3].

Complexité : dans le pire cas, on teste chaque position et chaque lettre du mot, soit \(O(n \times m)\) où \(n\) est la longueur du texte et \(m\) celle du mot.


13 - Traitement de données en tables 15 - Spécification et tests