Chapitre 5 : Occurrence, extremum, moyenne, coût linéaire
Parcourir une table
Python propose max, sum, in... mais que font-ils au juste ? Dans ce chapitre, tu les réécris toi-même avec une boucle : c'est le parcours séquentiel d'un tableau, le plus utilisé de tous les algorithmes. Tu verras aussi combien de comparaisons ils effectuent : leur coût.
Au programme de NSI : Algorithmique : Parcours séquentiel d'un tableau. Écrire un algorithme de recherche d'une occurrence sur des valeurs de type quelconque. Écrire un algorithme de recherche d'un extremum, de calcul d'une moyenne. Montrer que le coût est linéaire.
Le parcours séquentiel
Parcourir séquentiellement un tableau, c'est examiner ses éléments un par un, dans l'ordre, du premier au dernier. On le fait avec une boucle for sur les indices (range(len(t))) ou sur les valeurs (for v in t). Pendant le parcours, on met à jour une ou plusieurs variables.
t = [4, 8, 15]
for i in range(len(t)):
print(i, t[i])
for valeur in t:
print(valeur)Rechercher une occurrence
Pour savoir où apparaît une valeur, on parcourt le tableau et on s'arrête dès qu'on la trouve : return dans une fonction interrompt le parcours. Si on arrive au bout, la valeur est absente : on renvoie une valeur spéciale (-1 ou None).
def position(t, cible):
for i in range(len(t)):
if t[i] == cible:
return i
return -1
print(position([4, 8, 15], 8))
print(position([4, 8, 15], 99))Rechercher un extremum
Le maximum s'obtient en gardant dans une variable le plus grand élément vu jusqu'ici. On l'initialise avec le premier élément (pas avec 0 : toutes les valeurs peuvent être négatives !), puis on le remplace chaque fois qu'on en trouve un plus grand.
def maximum(t):
maxi = t[0]
indice = 0
for i in range(len(t)):
if t[i] > maxi:
maxi = t[i]
indice = i
return maxi, indiceCalculer une moyenne
La moyenne est la somme des valeurs divisée par leur nombre. On accumule la somme pendant le parcours. Attention au tableau vide : diviser par 0 est impossible. Il faut décider ce que renvoie la fonction dans ce cas (par exemple None).
def moyenne(t):
if len(t) == 0:
return None
somme = 0
for valeur in t:
somme = somme + valeur
return somme / len(t)Le coût d'un parcours
Le coût d'un algorithme se mesure en nombre d'opérations élémentaires. Dans un parcours séquentiel, on fait au plus une comparaison par élément : si le tableau a n éléments, on en fait au plus n. Doubler la taille du tableau double le travail : on dit que le coût est linéaire.
| Taille du tableau | Comparaisons au plus |
|---|---|
| 10 | 10 |
| 100 | 100 |
| 1 000 | 1 000 |
| 1 000 000 | 1 000 000 |
À toi de jouer : Exercice guidé
Écris la fonction maximum(valeurs) sans utiliser la fonction max : parcours le tableau en gardant le plus grand élément vu. Initialise maxi avec le premier élément, pas avec 0. Remplace chaque ___.