Parcours séquentiel d'un tableau

Un parcours séquentiel examine les éléments d'un tableau un par un, du premier au dernier. Il sert à chercher une valeur, à compter ses occurrences, à trouver le plus grand ou le plus petit élément, ou à calculer une somme et une moyenne.

La forme est toujours la même : initialiser une variable avant la boucle, la mettre à jour dans la boucle, la renvoyer après la boucle.

def maximum(t):
    m = t[0]
    for i in range(1, len(t)):
        if t[i] > m:
            m = t[i]
    return m

print(maximum([12, 5, 18, 7, 18, 3]))

18

m part du premier élément ; la boucle examine les éléments suivants, d'indices 1 à len(t) − 1, et chaque fois qu'un élément est plus grand, il remplace m. Après la boucle, m contient le maximum. On peut aussi parcourir les valeurs avec for x in t : le schéma est le même.

Compter et trouver la première occurrence. compte ajoute 1 à un compteur à chaque égalité ; indice avance tant qu'il n'a pas trouvé la valeur et s'arrête dès qu'il la trouve ; s'il est arrivé au bout (i == len(t)), la valeur est absente et il renvoie -1. On peut aussi l'écrire avec une boucle for et un return dans la boucle.

def compte(t, v):
    n = 0
    for i in range(len(t)):
        if t[i] == v:
            n = n + 1
    return n

def indice(t, v):
    i = 0
    while i < len(t) and t[i] != v:
        i = i + 1
    if i == len(t):
        return -1
    return i

t = [12, 5, 18, 7, 18, 3]
print(compte(t, 18), indice(t, 18), indice(t, 4))

2 2 -1

Moyenne. On accumule la somme, puis on divise par len(t) après la boucle (le tableau ne doit pas être vide).

def moyenne(t):
    s = 0
    for i in range(len(t)):
        s = s + t[i]
    return s / len(t)

print(moyenne([12, 5, 18, 7, 18, 3]))

10.5

Coût linéaire. Le nombre d'opérations est proportionnel à la longueur du tableau. Une recherche s'arrête tôt si la valeur est au début, mais examine tout le tableau dans le pire cas (valeur à la fin ou absente) :

def nb_comparaisons(t, v):
    c = 0
    for x in t:
        c = c + 1
        if x == v:
            return c
    return c

t = list(range(1000))
print(nb_comparaisons(t, 0), nb_comparaisons(t, 999), nb_comparaisons(t, -1))

1 1000 1000

Énoncé. Les lignes d'une fonction qui renvoie le nombre d'éléments d'un tableau strictement supérieurs à un seuil ont été mélangées ; chacune a gardé son indentation.

            n = n + 1
    return n
        if x > seuil:
def nb_superieurs(t, seuil):
    for x in t:
    n = 0

Méthode.

1. La seule ligne non indentée, def nb_superieurs(t, seuil):, ouvre la fonction : elle vient en premier.
2. Le compteur doit recevoir une valeur avant d'être utilisé : n = 0 vient ensuite, avant la boucle.
3. Chaque ligne terminée par deux-points ouvre un bloc : après for x in t: vient if x > seuil:, un cran plus à droite, puis n = n + 1, encore un cran plus à droite.
4. return n est au niveau de la boucle, après elle : on ne renvoie qu'une fois tout le tableau parcouru.

def nb_superieurs(t, seuil):
    n = 0
    for x in t:
        if x > seuil:
            n = n + 1
    return n

print(nb_superieurs([12, 5, 18, 7, 18, 3], 10))

3

Trois éléments dépassent 10 : 12, 18 et 18.

Six éléments : le premier sert à initialiser m, la boucle fait cinq tours pour les autres. Le nombre de tours est proportionnel à la longueur du tableau.