====== Correction exercice 3 du TP1  ======

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

On souhaite déterminer l'élément maximum des éléments de la séquence. On peut procéder par recherche séquentielle :

<code lang-none>
FONCTION maximum
ENTRÉE: séquence non vide d'objets comparables
SORTIE: élément maximum
DÉBUT
    maximum trouvé jusqu'ici est le premier élément de la séquence
    POUR CHAQUE item de la séquence à partir du rang 1 FAIRE
        SI cet item est plus grand que le maximum trouvé ALORS
            le maximum trouvé devient égal à cet élément
        FIN
    FIN
    renvoyer le maximum trouvé
FIN
</code> 
</WRAP>

Version Python :

<code python linenums>
def maximum(s):
    """
    s: séquence d'éléments comparables (int, float, str...)
    renvoie l'élément maximum
    """
    max_found = s[0]
    for item in s[1:]:
        if item > max_found:
            max_found = item
    return max_found

# exemple
m = maximum(["léopard", "chien", "zèbre", "baleine"])
print(m) # affiche "zèbre"
</code> 

Variante avec les indices :

<code python linenums>
def maximum(s):
    """
    s: séquence d'éléments comparables (int, float, str...)
    renvoie l'élément maximum et la liste des indices où il est atteint
    """
    max_found = s[0]
    indices = []
    for indice, item in enumerate(s):
        if item > max_found:
            max_found = item
            indices = [indice]
        elif item == max_found:
            indices.append(indice)
    return max_found, indices
    
# exemple
m, i = maximum(["léopard", "chien", "zèbre", "baleine", "chien", "zèbre"])
print(m) # affiche "zèbre"
print(i) # affiche les  indices : [2, 5]
</code>

<WRAP info>Comme dans l'exercice 2 avec ''est_element'', on peut critiquer l'idée d'implémenter une fonction ''maximum'' alors que la fonction ''max'' existe déjà et fait partie des fonctions de base en Python. Voici un exemple légèrement plus complexe qui justifie le recours à une fonction développée exprès -- une fonction //ad hoc//.

Supposons que l'entrée soit une liste de mot et que l'on veuille en sortie les mots les plus longs. La fonction ''max'' ne permet pas de faire cela. Voici ce qu'il faudrait faire :

<code python linenums>
def longueur_maximum(L):
    """
    L: liste de mots (chaînes de caractères)
    renvoie la liste des mots les plus longs
    """
    max_found = len(s[0])
    mots = []
    for item in L:
        if len(item) > max_found:
            max_found = len(item)
            mots = [item]
        elif len(item) == max_found:
            mots.append(item)
    return mots
    
# exemple
m = maximum(["léopard", "astérisque", "occasionnel", "dynamite", "baleine", "chien", "zèbre"])
print(m) # affiche "occasionnel"
</code>
</WRAP>

<WRAP box>
===== Question 2 =====

On cherche maintenant le deuxième maximum, c’est-à-dire, ici, la valeur maximale, une fois que l’on a éliminé les éléments égaux à la valeur maximale entendue comme ci-dessus.

Écrire une première fonction ''deux_maximum'' qui, pour une séquence L, retourne le couple ''(max1, max2)'' tel que :
  * ''max1 != max2''
  * ''max1 in L'' et ''max2 in L''
  * pour tout ''e in L'', ''e <= max1'' et si ''e != max1'' alors ''e <= max2''
</WRAP>

Je propose une version qui consisterait à faire un premier passage de L pour obtenir ''max1'', puis un deuxième passage pour obtenir ''max2''

<code python linenums>
def deux_maximum(L):
    # premier passage
    max1 = L[0]
    for item in L[1:]:
        if item > max1:
            max1 = item
    # on connaît maintenant max1
    # on cherche une valeur différente de max1
    for item in L[1:]:
        if item != max1:
            max2 = item
            break
    # maintenant max2 est initialisé sur une valeur qui est < max1
    for item in L:
        # si l'item est plus grand que max2 mais sans atteindre max1...
        if max1 > item > max2:
            max2 = item
    return max1, max2
</code>   

<WRAP box>
===== Question 3 =====

Écrire -- si distincte de la première -- une deuxième version ''deux_maximum2'' qui respecte l'algorithme suivant.

<code lang-none>
FONCTION deux_maximum2
ENTRÉE: séquence d'éléments comparables
        comptant au moins deux éléments distincts
SORTIE: paire (max1, max2), max1 étant le premier maximum et max2 le second
DÉBUT
    initialiser max1 et max2 à L[0], L[1],
    max1 devant être le plus grand des deux et max2 le plus petit
    POUR CHAQUE item de la liste à partir du rang 2 FAIRE
        modifier max1 et max2 selon la valeur de item
    FIN
    renvoyer max1, max2
</code>
</WRAP>

En Python :

<code python linenums>
def deux_maximum_2(L):
    if L[1] > L[0]:
        max1 = L[1]
        max2 = L[0]
    else:
        max1 = L[0]
        max2 = L[1]
    for item in L[2:]:
        # la difficulté est qu'on peut avoir max1 == max2,
        # ce qui fait plusieurs cas à envisager
        if item > max1:
            if max1 > max2:
                max2 = max1
            max1 = item
        elif max1 > item > max2:
            max2 = item
         
    return max1, max2
</code>

<WRAP box>
===== Question 4 =====

Donnez la complexité des fonctions obtenues en questions 2 et 3 -- une seule si vous avez fait deux fois la même chose.
</WRAP>

On pourrait croire que les complexités sont très différentes. Il n'en est rien.

  * Ma solution de la question 3 consiste en 3 boucles simples. La complexité sera linéaire -- quelque chose comme 2 + 12n
  * La solution de la question 4 est linéaire également. Quelque chose comme 3 + 5n. C'est moins mais l'ordre est le même.