informatique (tronc commun des prépas scientifiques) · Chapitre 2 · Exercice de TD
Le maximum et son indice, les égalités en prime
Recherche séquentielle et dictionnaires · niveau 2
Énoncé
Écrire indices_du_maximum(t) qui renvoie la liste de tous les indices où le maximum de la liste t est atteint, en un seul parcours de complexité .
Corrigé
On met à jour le maximum courant. Si une valeur strictement plus grande est trouvée, on vide la liste des indices pour n'y mettre que la nouvelle position. Si une valeur égale est trouvée, on ajoute l'indice à la liste :
def indices_du_maximum(t: list) -> list:
"""Précondition : t est non vide."""
m = t[0]
pos = [0]
for i in range(1, len(t)):
# Invariant : m = max(t[0..i-1]) et pos est la liste des indices j < i tels que t[j] == m
if t[i] > m:
m = t[i]
pos = [i] # On réinitialise car l'ancien maximum est dépassé
elif t[i] == m:
pos.append(i)
return pos