Introduction
Dans la plupart des programmes, les tableaux servent à organiser des données similaires sous une forme séquentielle. Savoir les parcourir est une compétence fondamentale en informatique, car cela permet d'y rechercher une valeur, d'en extraire des informations ou d'y appliquer des traitements. Ces parcours mobilisent des mécanismes communs à de nombreux algorithmes et permettent d’introduire des raisonnements essentiels comme les invariants ou le coût d’un traitement.
Parcourir un tableau : le schéma de base
Parcourir un tableau signifie examiner chaque élément, un à un, dans l’ordre. C’est le schéma le plus direct pour traiter une séquence de données. En Python, ce parcours peut s’effectuer soit par les indices, soit par les valeurs.
Exemples :
# Parcours par les indices
notes = [12, 15, 14, 10]
for i in range(len(notes)):
print(notes[i])
# Parcours direct par les valeurs
for note in notes:
print(note)
Ces deux variantes permettent d'accéder à l’ensemble du tableau. Le choix entre les deux dépend du besoin : on utilise souvent les indices si l’on veut manipuler la position ou modifier les valeurs.
Ce type de parcours est appelé parcours séquentiel. Il est linéaire : si le tableau contient n éléments, l’algorithme effectue au plus n opérations. On dit que son coût est linéaire, noté O(n). Ce type de coût est considéré comme raisonnable et souvent incontournable, en l’absence d’organisation particulière des données.
À retenir
Le parcours d’un tableau est une opération linéaire. En accédant à chaque élément l’un après l’autre, il permet d’effectuer toutes sortes de traitements. Le coût de ce parcours est proportionnel à la taille du tableau.
Rechercher une valeur dans un tableau
La recherche séquentielle est le premier algorithme naturel que l'on peut écrire sur un tableau. Elle consiste à tester chaque élément jusqu’à trouver une valeur donnée.
Exemple : rechercher si la note 18 est présente dans une liste.
notes = [12, 15, 14, 10, 18]
trouve = False
for note in notes:
if note == 18:
trouve = True
break
Cette méthode renvoie un booléen, mais on peut aussi chercher l’indice de la première occurrence :
indice = -1
for i in range(len(notes)):
if notes[i] == 18:
indice = i
break
Le coût de la recherche séquentielle est aussi linéaire, car, dans le pire des cas, il faut examiner tous les éléments du tableau.
Il est important de noter que des méthodes plus rapides existent si le tableau est trié, comme la recherche dichotomique, qui sera étudiée dans une leçon ultérieure. La recherche séquentielle reste cependant la méthode universelle dans tous les cas.
À retenir
La recherche d’un élément dans un tableau est un exemple classique de parcours linéaire. On l’appelle « recherche séquentielle » et son coût est proportionnel à la taille du tableau.
Calculer sur les éléments d’un tableau
Lors d’un parcours, on peut aussi accumuler des valeurs pour en tirer des informations globales. Ces algorithmes partagent un schéma commun : une variable est initialisée avant la boucle, puis mise à jour à chaque itération.
Calcul de la somme et de la moyenne
notes = [12, 15, 14, 10]
somme = 0
for note in notes:
somme += note
moyenne = somme / len(notes)
Python propose aussi sum(notes), mais connaître le mécanisme interne est essentiel pour comprendre les coûts et la logique de l’algorithme.
Rechercher un maximum ou un minimum
Ce type de recherche repose sur un invariant : à chaque étape du parcours, on conserve la meilleure valeur rencontrée jusque-là.
Exemple :
maximum = notes[0]
for note in notes:
if note > maximum:
maximum = note
Le raisonnement est identique pour le minimum. Il s’agit d’un parcours séquentiel, avec un invariant sur la variable maximum, qui contient toujours la plus grande valeur vue jusqu’à l’élément courant.
Compter des occurrences
Compter le nombre de fois qu’une valeur apparaît suit un schéma similaire.
compteur = 0
for note in notes:
if note == 14:
compteur += 1
Dans tous ces cas, on observe le même motif algorithmique : initialisation d’un accumulateur, puis mise à jour conditionnelle ou systématique au fil du parcours.
À retenir
Calculer une moyenne, un maximum ou un nombre d’occurrences repose sur un schéma commun : initialisation, parcours, mise à jour. Ces algorithmes s’appuient sur des invariants simples et ont un coût linéaire.
Parcours conditionnels et filtrés
Il arrive qu’on veuille traiter uniquement certains éléments du tableau, selon un critère. Le parcours est alors enrichi par une condition interne.
Exemple : calculer la moyenne des notes supérieures ou égales à 10.
notes = [12, 15, 8, 14, 10, 7]
somme = 0
nb = 0
for note in notes:
if note >= 10:
somme += note
nb += 1
if nb > 0:
moyenne = somme / nb
else:
moyenne = None # ou un message d’erreur
Ce type de traitement dépasse légèrement les attendus du programme, mais constitue une extension naturelle des parcours précédents. Il introduit également une vigilance nécessaire : il faut vérifier que le dénominateur n’est pas nul, pour éviter les erreurs de division.
Autre exemple : déterminer la note maximale et sa position.
maximum = notes[0]
indice_max = 0
for i in range(1, len(notes)):
if notes[i] > maximum:
maximum = notes[i]
indice_max = i
On suit ici deux informations simultanément dans le parcours : la meilleure valeur et sa position. Cela illustre la capacité à enrichir les traitements au sein d’une même boucle.
À retenir
Les parcours peuvent être conditionnels ou combinés : on peut filtrer les éléments à traiter ou accumuler plusieurs informations simultanément. Ces motifs sont très utilisés dans les algorithmes réels.
Conclusion
Parcourir un tableau pour chercher ou calculer permet d’aborder les premiers raisonnements algorithmiques. Les opérations classiques comme la recherche, le calcul d’un maximum ou d’une moyenne partagent un schéma fondamental : le parcours linéaire avec mise à jour d’un état. Ces algorithmes sont simples mais essentiels, et introduisent des notions comme le coût linéaire, les invariants ou la condition de terminaison, qui seront approfondies dans les leçons suivantes.