Exercice 3 du TP 1

On se place dans le cas d'une séquence – list, tuple, str – non vide d'objets que l'on peut comparer.

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

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

1. Implémenter cette fonction.
2. Écrire une variante qui renvoie, en plus du maximum, la séquence des indices où ce maximum est atteint

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.

Précondition : La séquence contient au moins deux valeurs distinctes.

É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

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

FONCTION deux_maximum2
ENTRÉE: séquence L 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

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