26 - Parcours de liste

Cours associés : 16 - Complexité , 19 - Dichotomie .

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 publiée après la séance.

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 publiée après la séance.

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 publiée après la séance.

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 publiée après la séance.

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 ».

   Indice

   Parcourir la liste avec for x in L: et renvoyer True dès que x est égal à a. Le return False ne se place qu’après la boucle, quand tous les éléments ont été examinés.

   Code à copier puis compléter

   def est_element(a, L):
       for x in L:
           if ...:
               return True
       return ...
   

2. Modifier la fonction ci-dessus afin qu’elle retourne l’indice minimal de la liste correspondant à une occurrence de a.

   Indice

   Parcourir les indices avec for i in range(len(L)): pour pouvoir renvoyer i dès que L[i] est égal à a. Si a n’est pas dans la liste, renvoyer une valeur qui ne peut pas être un indice, par exemple -1.

3. Même question pour trouver le nombre d’occurrences de a dans la liste.

   Indice

   Un compteur part de 0 et augmente de 1 à chaque élément égal à a ; on le renvoie après la boucle, sans s’arrêter au premier élément trouvé.

Correction publiée après la séance.

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.

def maximum(L):
    if len(L) == 0:
        return "La liste est vide"
    maxi = L[0]
    for x in L:
        if ...:
            maxi = ...
    return maxi

Correction publiée après la séance.

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.

def recherche_dicho(val, L):
    gauche = 0
    droite = len(L) - 1
    while gauche <= droite:
        milieu = (gauche + droite) // 2
        if L[milieu] == val:
            return ...
        elif L[milieu] < val:
            gauche = ...
        else:
            droite = ...
    return -1

Correction publiée après la séance.

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.

   Indice

   Si i + len(mot) dépasse len(texte), le mot ne peut pas tenir : renvoyer False. Sinon, comparer texte[i + j] et mot[j] pour chaque position j du mot : à la première différence, renvoyer False, et après la boucle, True.

   Code à copier puis compléter

   def isprefixe(texte, mot, i):
       if i + len(mot) > len(texte):
           return False
       for j in range(len(mot)):
           if texte[...] != mot[j]:
               return ...
       return ...
   

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 ».

   Indice

   Essayer chaque position i où le mot peut commencer, de 0 à len(texte) - len(mot), et ajouter i à une liste quand isprefixe(texte, mot, i) vaut True.

   Code à copier puis compléter

   def cherche_occurrences(texte, mot):
       positions = []
       for i in range(len(texte) - len(mot) + 1):
           if ...:
               positions.append(...)
       return positions
   

Correction publiée après la séance.