Implémentation d'algorithmes sur tableaux
Introduit| English | Sens |
|---|---|
| traversal/træˈvɜːsl/ | parcours |
| index/ˈɪndeks/ | indice |
| linear search/ˈlɪnɪə sɜːtʃ/ | recherche linéaire |
Algorithmes standards sur tableau
- La plupart des tâches sur les tableaux consistent en un parcours combiné à l'un de quelques modèles standards.
- Somme / moyenne : accumuler un total, puis diviser par
length. - Comptage : incrémenter quand un élément correspond à une condition.
- Min / max : suivre la plus petite ou la plus grande valeur rencontrée jusqu'ici.
Trouver le maximum
- Commencez par
max = a[0](le premier élément), puis traversez depuis l'indice1. if (a[i] > max) { max = a[i]; }à l'intérieur de la boucle.- Après la boucle,
maxcontient la plus grande valeur du tableau. - Commencez par le premier élément, pas
0—0pourrait être plus grand que toutes les valeurs.

Trouver le maximum d'un tableau, tracé étape par étape
Rechercher une valeur
- Pour vérifier si une valeur existe, traversez et comparez chaque élément.
- Retourner l'index où il est trouvé, ou
-1si la boucle se termine sans correspondance. if (a[i] == target) return i;à l'intérieur de la boucle ;return -1;à l'extérieur.- Il s'agit d'une recherche linéaire (l'Unité 4.14 la traite en détail).
Décalages et modifications
- Certains algorithmes déplacent ou changent des éléments — par ex. décaler tout vers la gauche, ou doubler chaque valeur.
- Modifier nécessite la boucle indexée pour pouvoir affecter
a[i] = .... - Surveillez les limites lors de la lecture de
a[i+1]— le dernier indice n'a pas de voisin. - Tracez soigneusement les indices pour éviter un accès hors limites.
Initialisez une recherche min/max avec le PREMIER élément, pas 0. int max = 0; échoue si toutes les valeurs sont négatives (il rapporterait faussement 0). Utilisez int max = a[0]; et commencez la boucle à l'indice 1. Et lorsqu'un algorithme lit a[i+1], arrêtez la boucle à i < a.length - 1, sinon la dernière itération lit au-delà de la fin.
Trouver le maximum de a :
int max = a[0];for (int i = 1; i < a.length; i++) { if (a[i] > max) max = a[i]; }- Pour
a = {3, 9, 5}: max devient9.
Les algorithmes de tableau combinent un parcours avec un motif : somme/moyenne, comptage, min/max, ou recherche (renvoyer l'index ou -1). Initialisez un min/max avec le premier élément, pas 0. La modification des éléments nécessite la boucle indexée, et la lecture de a[i+1] nécessite une borne plus serrée pour rester dans les limites.
Trouver le maximum
max commence à a[0]=3, devient 9, puis reste (a = {3,9,5}).
Pour trouver le maximum d'un tableau, vous devriez initialiser max à...
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Commencer à 0 échoue si toutes les valeurs sont négatives.
Pour a = {3, 9, 5}, quelle est la valeur maximale ?
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
9 est le plus grand élément.
Quel résultat retourne une recherche linéaire si la cible n'est pas trouvée ?
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Par convention, -1 signifie « non trouvé ».
Un algorithme qui lit a[i+1] doit boucler tant que...
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
S'arrêter une étape plus tôt garde a[i+1] dans les limites.
Modifier les éléments du tableau (a[i] = ...) nécessite la boucle indexée, pas for-each.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
for-each ne peut pas écrire en retour dans le tableau.