Correction exercice 3 du TP1

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 :

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

Version Python :

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"

Variante avec les indices :

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]

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 :

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"

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

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

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

Question 3

É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 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

En Python :

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

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.

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.