====== Correction exercice 2 du TP1 ======

<WRAP box>
===== Question 1 =====

Implémenter la fonction ''est_element'' en Python.
</WRAP>

D'abord un algorithme en pseudo-code :

<WRAP lang-none linenum>
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 :

<code python linenums>
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
</code>

<WRAP info>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 :
<code python>
def contient_diviseur(L, a):
    for item in L:
        if item != 0 and a % item == 0:
            return True
    return False
</code>
</WRAP>

<WRAP box>
===== 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.
</WRAP>

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

<WRAP box>
===== 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).
</WRAP>

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

<code python>
>>>est_element("bonjour", "b")
True
>>>est_element("bonjour", "x")
False
</code>

<WRAP box>
===== 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''
</WRAP>

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

<code lang-none linenums>
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
</code>

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 :

<code python linenums>
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
</code>

<WRAP box>
===== 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''
</WRAP>

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.

<code lang-none linenums>
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
</code>

<code python linenums>
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
</code>