Correction exercice 2 du TP1

Question 1

Implémenter la fonction est_element en Python.

D'abord un algorithme en pseudo-code :

FONCTION est_element ENTRÉES:

Séquence
Item dont on veut savoir s'il est dans la séquence

SORTIE: si l'item appartient à la séquence, renvoie Vrai. Renvoie Faux sinon DÉBUT

  POUR CHAQUE item de la séquence FAIRE
      SI item est celui cherché ALORS
          on a trouvé !
          RENVOYER Vrai
      FIN
  FIN
  nous sommes arrivés au bout sans rien trouver...
  RENVOYER Faux

FIN </code>

Traduction en Python :

def est_element(L, a)
    """
    L: Séquence
    a: Item dont on veut savoir s'il est dans la séquence
    Renvoie True si a appartient à L
    """
    for item in L:
        if item == a:
            return True
    return False

# j'ajoute les tests nécessaires
assert est_element([5,12,96,45,12], 4) == False # cas e absent
assert est_element([5,12,96,45,12], 96) == True # cas e présent 1 fois
assert est_element([5,12,96,45,12], 12) == True # cas e présent 2 fois
assert est_element([], 12) == False # cas L vide

Certains élèves sont embarrassés par le sujet qui leur dit qu'ils ne peuvent pas utiliser in pour résoudre directement le problème mais qu'ils doivent l'utiliser pour le for … in. C'est On rencontre parfois ce problème quand on essaie de simplifier un sujet. C'est parfois plus clair avec légèrement plus de complexité. Je vous propose donc une légère variation du sujet : supposez que la question soit : renvoyer Vrai si L contient un diviseur de a. Formulé ainsi, vous serez obligé de faire une boucle comme celle faite dans l'exercice. La fonction serait alors :

def contient_diviseur(L, a):
    for item in L:
        if item != 0 and a % item == 0:
            return True
    return False

Question 2

Pour un algorithme s'appliquant à une donnée de taille n – ici, n est la longueur de la liste : n = len(L), autrement dit le nombre d'éléments de L – on veut évaluer le nombre d’opérations élémentaires pertinentes.

On pourra compter le nombre d'exécution de la comparaison « == ».

On étudie le comportement asymptotique de ce nombre.

Dans le meilleur des cas, l'item recherché est le premier de la liste. On le trouve tout de suite. On n'a une seule comparaison à faire.
Dans le pire des cas, l'élément n'est pas dans L. On est obligé de parcourir tous les éléments de L. On fait donc n comparaisons. Le coût est linéaire.

Question 3

Écrire une fonction qui prend en argument une chaîne de caractères et un caractère 'c' et vérifie la présence ou pas du caractère dans la chaîne de caractères (et la tester).

C'est la magie de Python : il n'y a rien à changer !

>>>est_element("bonjour", "b")
True
>>>est_element("bonjour", "x")
False

Question 4

Adapter, modifier, la fonction de la première question en demandant

si a est présent, renvoyer l'indice de la première occurrence de a dans L
sinon, renvoyer False

Presque la même chose. Dans le cas où on trouve l'élément, au lieu de renvoyer True, on renvoie l'indice.

FONCTION est_element
ENTRÉES:
  Séquence
  Item dont on veut savoir s'il est dans la séquence
SORTIE: si l'item appartient à la séquence, renvoie Vrai. Renvoie Faux sinon
DÉBUT
    POUR CHAQUE item de la séquence FAIRE
        SI item est celui cherché ALORS
            on a trouvé !
            RENVOYER l'indice
        FIN
    FIN
    nous sommes arrivés au bout sans rien trouver...
    RENVOYER Faux
FIN

Mais on est un peu ennuyé : dans le programme précédent, nous avons utilisé une boucle for item in L qui consiste à faire défiler les items présents dans L. Mais on ne note pas les indices…

Il y a plusieurs façon de faire mais il y a toujours des méthodes simples en Python. Il y a notamment une astuce qui permet de parcourir simultanément les indices et les items d'une séquence :

def est_element(L, a)
    """
    L: Séquence
    a: Item dont on veut savoir s'il est dans la séquence
    Renvoie l'indice de la première occurrence de a dans L, False sinon
    """
    for indice, item in enumerate(L): # parcours simultané indice et item !
        if item == a:
            return indice
    return False

Question 4 bis

Adapter, modifier, la première question en demandant

si a est présent, renvoyer la liste des indices de toutes les occurrences de a dans L
sinon, renvoyer False

Grosse différence : Dans le programme précédent, sitôt que l'on trouvait une occurrence, on interrompait l'exécution de la fonction avec return. Maintenant, on doit toujours aller au bout de la fonction pour compter toutes les occurrences.

FONCTION est_element
ENTRÉES:
  Séquence
  Item dont on veut savoir s'il est dans la séquence
SORTIE: la liste des indices de l'item,
        False si l'item n'est pas présent
DÉBUT
    initialiser une liste vide d'indices 
    POUR CHAQUE item de la séquence FAIRE
        SI item est celui cherché ALORS
            ajouter cette indice à la liste d'indices
        FIN
    FIN
    SI la liste d'indices est vide ALORS
        RENVOYER False
    SINON
        RENVOYER la liste d'indices
    FIN
FIN

def est_element(L, a)
    """
    L: Séquence
    a: Item dont on veut savoir s'il est dans la séquence
    Renvoie la liste des indices des occurrences de a dans L, False si aucune
    """
    indices = []
    for indice, item in enumerate(L): # parcours simultané indice et item !
        if item == a:
            indices.append(indice)
    if indices == []:
        return False
    else:
        return indices