Séance 4 — Les tableaux

Ranger, parcourir, chercher, transformer

Séance 4 d’Algorithmique : ranger, parcourir, chercher, transformer.
Auteur

Dr. El Hadji Bassirou TOURÉ · DMI/FST/UCAD

NoteNavigation conceptuelle

Amont. Les variables et l’affectation (Séance 1) ; les conditions (Séance 2) ; les boucles Pour et TantQue, le compteur, l’accumulateur, le maximum et l’erreur de décalage d’une unité (Séance 3). Un tableau n’ajoute qu’une chose : une variable à \(n\) cases, dont la case utilisée est choisie par le calcul d’un indice.

Aval. Les fonctions et procédures qui reçoivent un tableau en paramètre (Séance 5) reprennent les parcours de cette séance, écrits une fois sous un nom.

ImportantObjectifs
  • Déclarer un tableau, désigner une case par un indice calculé, lire et écrire une case.
  • Dérouler à la main un parcours par Pour : remplissage, somme, moyenne, comptage.
  • Chercher une valeur avec arrêt dès qu’elle est trouvée, et compter les comparaisons.
  • Trouver le maximum d’un tableau et sa position.
  • Inverser et décaler un tableau en place, dans le bon sens de parcours.
  • Repérer, par une trace, un indice hors bornes et une case lue avant d’être remplie.

Les conventions du pseudo-code

Les séances 1 à 3 ont fixé les instructions de base et les trois boucles. La présente séance ajoute le tableau : sa déclaration, l’accès à une case, son remplissage ; elle rappelle l’évaluation des deux membres de ET et OU (Séance 2) et précise l’écriture des réels. Le tableau ci-dessous rassemble toutes les conventions utilisées dans la suite ; les cinq dernières lignes sont nouvelles.

Écriture Sens
\(x\leftarrow e\) \(x\) reçoit la valeur de l’expression \(e\) (se lit « \(x\) reçoit \(e\) »)
Lire n n reçoit la valeur tapée au clavier ; une valeur par ligne
Écrire "tour", i écrit les valeurs séparées par une espace, puis passe à la ligne : tour 1
\(=\), \(\neq\), \(<\), \(\leq\), \(>\), \(\geq\) ; ET, OU, NON comparaisons et connecteurs logiques, de résultat vrai ou faux
\(+\), \(-\), \(\times\) ; div, mod opérations ; quotient et reste de la division entière (\(7\) mod \(2=1\))
TantQue \(C\) Faire … FinTantQue test de \(C\) avant chaque tour ; de zéro à plusieurs tours
Pour \(i\) de \(a\) à \(b\) [pas \(p\)] Faire … FinPour \(i=a, a+p, \dots\) tant que \(i\leq b\) (\(i\geq b\) si \(p<0\)) ; compteur non défini après FinPour
Répéter … Jusqu’à \(C\) corps exécuté, puis test ; sortie quand \(C\) est vraie ; au moins un tour
\(C_1\) ET \(C_2\) ; \(C_1\) OU \(C_2\) les deux membres sont toujours évalués, même quand le premier décide déjà du résultat (Séance 2)
\(a\,/\,b\) division réelle ; un réel s’écrit avec une virgule et au moins une décimale : \(58/5\) donne 11,6, \(200/5\) donne 40,0
T : tableau[1..n] déntiers déclare un tableau T de \(n\) cases d’indices 1 à \(n\), encore non remplies ; \(n\) a une valeur au moment de la déclaration, et la taille ne change plus
T[i] la case d’indice \(i\), pour \(1\leq i\leq n\) ; l’indice est une expression entière (T[i + 1], T[n - i + 1])
T[i] \(\leftarrow e\) ; Lire T[i] la case \(i\) reçoit une valeur ; les autres cases ne changent pas
T \(\leftarrow\) [12, 8, 15, 9, 14] remplit les cases 1 à \(n\) dans l’ordre ; autant de valeurs que de cases

Trois situations sont des erreurs qui arrêtent l’exécution : un indice hors de 1 à \(n\), la lecture d’une case qui n’a jamais reçu de valeur, et une division par zéro (Séance 2). Les traces de ce document les signalent par « arrêt ».

Dans une trace d’un algorithme à tableau, chaque case du tableau a sa colonne. La case écrite au pas est en rouge gras ; les cases lues pendant le pas, pour calculer une expression ou un test, sont en orange. Une case vide n’a pas encore de valeur. Les variables ordinaires gardent la présentation de la Séance 3 : la valeur qui vient de changer est en gras.

Le tableau et ses cases

Pourquoi un tableau

À Saint-Louis, Aïssatou relève les notes de ses 30 étudiants. Avec les variables des séances précédentes, il faut trente noms (note1, note2, …, note30), trente instructions Lire, et une somme écrite en trente termes ; aucune boucle ne peut aider, car une boucle répète une même instruction, alors que chaque note a ici un nom différent. Le besoin est celui d’un nom unique pour toutes les notes, avec un numéro qui choisit l’une d’elles : ce numéro, une boucle peut le faire varier.

NoteTableau, case, indice

Un tableau est une suite de \(n\) cases de même type, désignée par un seul nom. Chaque case est repérée par son indice, un entier de 1 à \(n\) ; T[i] désigne la case d’indice \(i\) du tableau T. L’indice peut être une constante (T[3]), une variable (T[i]) ou une expression entière (T[i + 1]), évaluée au moment de l’accès.

Il faut distinguer l’indice et la valeur. Dans le tableau de la figure, l’indice 3 désigne la troisième case, et la valeur rangée dans cette case est 15 : T[3] vaut 15. Avec \(i=2\), l’expression T[i + 1] désigne encore la case 3 et vaut 15 ; T[i] + 1 vaut \(8+1=9\). Les crochets entourent toujours l’indice, jamais la valeur.

L’indice peut lui-même être lu dans une case : c’est l’indexation indirecte. Pour évaluer T[T[k]], on lit d’abord la case \(k\), dont la valeur sert d’indice, puis la case de cet indice. Avec U \(\leftarrow\) [3, 1, 2], U[U[1]] lit U[1] \(=3\), puis U[3], et vaut 2. La valeur lue doit être elle-même un indice valide : dans le tableau de la figure, T[T[4]] lit T[4] \(=9\), puis demande T[9], qui n’existe pas. L’indexation indirecte sert dès qu’une donnée désigne une position, par exemple une réponse de 1 à 5 qui choisit le compteur à augmenter.

La déclaration

Un tableau se déclare par une ligne de la forme T : tableau[1..n] déntiers, qui fixe son nom, ses indices (de 1 à \(n\)) et le type de ses cases. La taille \(n\) doit avoir une valeur au moment où la ligne est exécutée : une constante, ou une variable déjà affectée ou lue. Elle ne change plus ensuite. Après la déclaration, les \(n\) cases existent mais ne contiennent encore aucune valeur : elles sont non remplies, et les lire serait une erreur (section 6).

Plusieurs langages de programmation numérotent les cases à partir de 0. Le pseudo-code du cours, comme le livre de Cormen, les numérote de 1 à \(n\) : la première case est T[1], la dernière T[n], et un tableau de \(n\) cases n’a ni T[0] ni T[n + 1]. Ce choix a un avantage qui servira dans la recherche (section 4) : 0 n’étant pas un indice, il peut signifier « aucune case ».

Exemple pas à pas : lire et écrire une case

L’algorithme suivant déclare un tableau de 4 cases, en remplit trois par des affectations, dont une calculée à partir de deux autres cases, puis en remplit une quatrième avec un indice calculé.

T : tableau[1..4] d'entiers
T[1] ← 4
T[2] ← 7
T[3] ← T[1] + T[2]
i ← 3
T[i + 1] ← T[i] × 2
Écrire T[2], T[4]
Pas Ligne Instruction i T[1] T[2] T[3] T[4] Test Écrit
1 1 T : tableau[1..4] déntiers
2 2 T[1] ← 4 4
3 3 T[2] ← 7 4 7
4 4 T[3] ← T[1] + T[2] 4 7 11
5 5 i ← 3 3 4 7 11
6 6 T[i + 1] ← T[i] × 2 3 4 7 11 22
7 7 Écrire T[2], T[4] 3 4 7 11 22 7 22

Au pas 1, le tableau existe mais ses quatre colonnes sont vides. Les pas 2 et 3 écrivent les cases 1 et 2. Au pas 4, l’expression T[1] + T[2] lit les cases 1 et 2 (en orange) et la valeur 11 est écrite dans la case 3 (en rouge) : lire une case ne la modifie pas, l’écrire remplace son contenu. Au pas 6, avec \(i=3\), la cible T[i + 1] est la case 4 et la source T[i] la case 3 : T[4] reçoit \(11\times2=22\). La ligne 7 écrit 7 22. La figure suivante montre le pas 6 : la ligne exécutée est surlignée, le tableau est dessiné en cases avec ses indices au-dessus, la case lue T[3] est en orange et la case écrite T[4] en rouge ; en dessous, l’état des variables.

AvertissementIndice et valeur

T[i] et i sont deux choses différentes : i est le numéro de la case, T[i] ce qu’elle contient. L’instruction \(\texttt{i}\leftarrow\texttt{i} + 1\) passe à la case suivante sans rien changer au tableau ; T[i] \(\leftarrow\) T[i] + 1 ajoute 1 au contenu de la case \(i\) sans changer de case.

Le parcours par Pour

La plupart des traitements d’un tableau visitent ses cases une à une, de la première à la dernière. Le nombre de cases est connu : c’est la taille \(n\). La boucle Pour de la Séance 3 convient donc, et son compteur sert d’indice.

NoteParcours d’un tableau

Un parcours est une boucle Pour \(i\) de 1 à \(n\) dont le corps traite la case T[i]. Il fait \(n\) tours et visite chaque case une fois, dans l’ordre des indices. Les compteurs et accumulateurs nécessaires sont initialisés avant la boucle, mis à jour à chaque case, lus après la boucle.

Exemple pas à pas : le remplissage par Lire

Le premier parcours remplit le tableau à partir du clavier. La taille est lue avant la déclaration, puis chaque tour lit une valeur et la range dans la case du tour. Les entrées sont 4, puis 12, 8, 15 et 9.

Lire n
T : tableau[1..n] d'entiers
Pour i de 1 à n Faire
  Lire T[i]
FinPour
Écrire "dernière case :", T[n]
Pas Ligne Instruction n i T[1] T[2] T[3] T[4] Test Écrit
1 1 Lire n 4
2 2 T : tableau[1..n] déntiers 4
3 3 Pour i de 1 à n Faire 4 1 vrai
4 4 Lire T[i] 4 1 12
5 3 Pour i de 1 à n Faire 4 2 12 vrai
6 4 Lire T[i] 4 2 12 8
7 3 Pour i de 1 à n Faire 4 3 12 8 vrai
8 4 Lire T[i] 4 3 12 8 15
9 3 Pour i de 1 à n Faire 4 4 12 8 15 vrai
10 4 Lire T[i] 4 4 12 8 15 9
11 3 Pour i de 1 à n Faire 4 5 12 8 15 9 faux
12 6 Écrire “dernière case :”, T[n] 4 12 8 15 9 dernière case : 9

Le pas 1 lit la taille, le pas 2 déclare un tableau de 4 cases vides. Aux pas 4, 6, 8 et 10, l’instruction Lire T[i] range la valeur tapée dans la case dont l’indice est la valeur courante de \(i\) : les cases se remplissent de gauche à droite, une par tour. Au pas 11, \(i=5\) et le test \(5\leq4\) est faux : la boucle s’arrête après exactement \(n\) tours. Le pas 12 lit la case T[n], la dernière, et écrit dernière case : 9.

Exemple pas à pas : la somme et la moyenne

Dans les exemples suivants, le tableau est rempli en une ligne par la liste de ses valeurs, pour que la trace se concentre sur le traitement. Les cinq notes sont celles d’Awa, à Kaolack, dans cinq matières. La somme est l’accumulateur de la Séance 3, appliqué case par case.

n ← 5
T : tableau[1..n] d'entiers
T ← [12, 8, 15, 9, 14]
s ← 0
Pour i de 1 à n Faire
  s ← s + T[i]
FinPour
moy ← s / n
Écrire s, moy
Pas Ligne Instruction n s i moy T[1] T[2] T[3] T[4] T[5] Test Écrit
1 1 n ← 5 5
2 2 T : tableau[1..n] déntiers 5
3 3 T ← [12, 8, 15, 9, 14] 5 12 8 15 9 14
4 4 s ← 0 5 0 12 8 15 9 14
5 5 Pour i de 1 à n Faire 5 0 1 12 8 15 9 14 vrai
6 6 s ← s + T[i] 5 12 1 12 8 15 9 14
7 5 Pour i de 1 à n Faire 5 12 2 12 8 15 9 14 vrai
8 6 s ← s + T[i] 5 20 2 12 8 15 9 14
9 5 Pour i de 1 à n Faire 5 20 3 12 8 15 9 14 vrai
10 6 s ← s + T[i] 5 35 3 12 8 15 9 14
11 5 Pour i de 1 à n Faire 5 35 4 12 8 15 9 14 vrai
12 6 s ← s + T[i] 5 44 4 12 8 15 9 14
13 5 Pour i de 1 à n Faire 5 44 5 12 8 15 9 14 vrai
14 6 s ← s + T[i] 5 58 5 12 8 15 9 14
15 5 Pour i de 1 à n Faire 5 58 6 12 8 15 9 14 faux
16 8 moy ← s / n 5 58 11,6 12 8 15 9 14
17 9 Écrire s, moy 5 58 11,6 12 8 15 9 14 58 11,6

Le pas 3 remplit les cinq cases d’un coup (toutes en rouge). L’accumulateur \(s\) part de 0 au pas 4. Chaque tour lit une seule case, celle d’indice \(i\), et l’ajoute à \(s\) : \(s\) vaut successivement 12, 20, 35, 44 et 58 (pas 6, 8, 10, 12 et 14). Au pas 15, \(i=6\) rend faux le test \(i\leq5\) ; le pas 16 calcule la moyenne \(58/5\), et la ligne 9 écrit 58 11,6. Comme \(/\) donne un réel, la moyenne est 11,6 et non le quotient entier 11, que donnerait \(58\) div \(5\).

Exemple pas à pas : le comptage

Un compteur placé dans un parcours compte les cases qui vérifient une condition : ici, les notes d’au moins 10.

n ← 5
T : tableau[1..n] d'entiers
T ← [12, 8, 15, 9, 14]
c ← 0
Pour i de 1 à n Faire
  Si T[i] ≥ 10 Alors
    c ← c + 1
  FinSi
FinPour
Écrire "au moins 10 :", c
Pas Ligne Instruction n c i T[1] T[2] T[3] T[4] T[5] Test Écrit
1 1 n ← 5 5
2 2 T : tableau[1..n] déntiers 5
3 3 T ← [12, 8, 15, 9, 14] 5 12 8 15 9 14
4 4 c ← 0 5 0 12 8 15 9 14
5 5 Pour i de 1 à n Faire 5 0 1 12 8 15 9 14 vrai
6 6 Si T[i] ≥ 10 Alors 5 0 1 12 8 15 9 14 vrai
7 7 c ← c + 1 5 1 1 12 8 15 9 14
8 5 Pour i de 1 à n Faire 5 1 2 12 8 15 9 14 vrai
9 6 Si T[i] ≥ 10 Alors 5 1 2 12 8 15 9 14 faux
10 5 Pour i de 1 à n Faire 5 1 3 12 8 15 9 14 vrai
11 6 Si T[i] ≥ 10 Alors 5 1 3 12 8 15 9 14 vrai
12 7 c ← c + 1 5 2 3 12 8 15 9 14
13 5 Pour i de 1 à n Faire 5 2 4 12 8 15 9 14 vrai
14 6 Si T[i] ≥ 10 Alors 5 2 4 12 8 15 9 14 faux
15 5 Pour i de 1 à n Faire 5 2 5 12 8 15 9 14 vrai
16 6 Si T[i] ≥ 10 Alors 5 2 5 12 8 15 9 14 vrai
17 7 c ← c + 1 5 3 5 12 8 15 9 14
18 5 Pour i de 1 à n Faire 5 3 6 12 8 15 9 14 faux
19 10 Écrire “au moins 10 :”, c 5 3 12 8 15 9 14 au moins 10 : 3

Le test du Si lit à chaque tour la case du tour (pas 6, 9, 11, 14 et 16). Il est vrai pour les cases 1, 3 et 5, qui contiennent 12, 15 et 14 : le compteur augmente aux pas 7, 12 et 17. Les cases 2 et 4 (8 et 9) rendent le test faux, et la ligne 7 est sautée. L’algorithme écrit au moins 10 : 3. Le nombre de tours (5) ne dépend que de l’en-tête ; le Si ne décide que de ce qui est fait à chaque tour.

AvertissementLes bornes d’un parcours

Un parcours va de 1 à \(n\). Pour \(i\) de 1 à \(n-1\) oublie la dernière case, sans aucun message : c’est l’erreur de décalage d’une unité de la Séance 3. Pour \(i\) de 0 à \(n-1\), écrit par habitude d’un langage qui numérote à partir de 0, demande la case T[0], qui n’existe pas ; Pour \(i\) de 1 à \(n+1\) demande T[n + 1] (section 6).

Chercher dans un tableau

La recherche avec arrêt

À la gare routière de Kaolack, un agent cherche dans la liste du jour le numéro d’un colis : il parcourt la liste depuis le début et s’arrête au premier numéro égal, sans lire la suite. Un parcours par Pour lirait toujours toute la liste. Comme le nombre de cases à examiner n’est pas connu à l’entrée (il dépend de la place de la valeur cherchée), la boucle est un TantQue, avec deux conditions de continuation.

NoteRecherche séquentielle avec arrêt

Pour chercher \(x\) dans T[1..n], comparer \(x\) aux cases 1, 2, 3… tant qu’il reste des cases à examiner (\(i\leq n\)) et que \(x\) n’a pas été trouvé (\(\texttt{pos}=0\)). Le résultat pos est l’indice de la première case égale à \(x\), ou 0 si \(x\) est absent.

La valeur 0 de pos joue deux rôles : avant la boucle, elle signifie « pas encore trouvé » ; à la fin, « absent ». Elle ne peut être confondue avec une position, puisque les indices commencent à 1.

Exemple pas à pas : une valeur présente

Le tableau est celui des notes d’Awa ; la valeur cherchée, lue au clavier, est 15.

n ← 5
T : tableau[1..n] d'entiers
T ← [12, 8, 15, 9, 14]
Lire x
pos ← 0
i ← 1
TantQue i ≤ n ET pos = 0 Faire
  Si T[i] = x Alors
    pos ← i
  FinSi
  i ← i + 1
FinTantQue
Écrire "case :", pos
Pas Ligne Instruction n x pos i T[1] T[2] T[3] T[4] T[5] Test Écrit
1 1 n ← 5 5
2 2 T : tableau[1..n] déntiers 5
3 3 T ← [12, 8, 15, 9, 14] 5 12 8 15 9 14
4 4 Lire x 5 15 12 8 15 9 14
5 5 pos ← 0 5 15 0 12 8 15 9 14
6 6 i ← 1 5 15 0 1 12 8 15 9 14
7 7 TantQue i ≤ n ET pos = 0 Faire 5 15 0 1 12 8 15 9 14 vrai
8 8 Si T[i] = x Alors 5 15 0 1 12 8 15 9 14 faux
9 11 i ← i + 1 5 15 0 2 12 8 15 9 14
10 7 TantQue i ≤ n ET pos = 0 Faire 5 15 0 2 12 8 15 9 14 vrai
11 8 Si T[i] = x Alors 5 15 0 2 12 8 15 9 14 faux
12 11 i ← i + 1 5 15 0 3 12 8 15 9 14
13 7 TantQue i ≤ n ET pos = 0 Faire 5 15 0 3 12 8 15 9 14 vrai
14 8 Si T[i] = x Alors 5 15 0 3 12 8 15 9 14 vrai
15 9 pos ← i 5 15 3 3 12 8 15 9 14
16 11 i ← i + 1 5 15 3 4 12 8 15 9 14
17 7 TantQue i ≤ n ET pos = 0 Faire 5 15 3 4 12 8 15 9 14 faux
18 13 Écrire “case :”, pos 5 15 3 4 12 8 15 9 14 case : 3

Les deux premiers tours suivent le même motif de trois pas : test de la ligne 7, comparaison de la ligne 8 (fausse pour 12, puis pour 8), progression de la ligne 11. Au troisième tour, la comparaison du pas 14 trouve T[3] \(=15\) : pos reçoit 3 au pas 15. La progression du pas 16 porte encore \(i\) à 4, car elle suit le Si. Au pas 17, le test lit \(\texttt{pos}=3\) et devient faux : la boucle s’arrête sans examiner les cases 4 et 5, et l’algorithme écrit case : 3. La figure suivante montre le pas 14, la comparaison qui réussit : seule la case T[3] est lue.

Exemple pas à pas : une valeur absente

Avec l’entrée 10, qui ne figure pas dans le tableau, la comparaison échoue à chaque case.

Pas Ligne Instruction n x pos i T[1] T[2] T[3] T[4] T[5] Test Écrit
1 1 n ← 5 5
2 2 T : tableau[1..n] déntiers 5
3 3 T ← [12, 8, 15, 9, 14] 5 12 8 15 9 14
4 4 Lire x 5 10 12 8 15 9 14
5 5 pos ← 0 5 10 0 12 8 15 9 14
6 6 i ← 1 5 10 0 1 12 8 15 9 14
7 7 TantQue i ≤ n ET pos = 0 Faire 5 10 0 1 12 8 15 9 14 vrai
8 8 Si T[i] = x Alors 5 10 0 1 12 8 15 9 14 faux
9 11 i ← i + 1 5 10 0 2 12 8 15 9 14
10 7 TantQue i ≤ n ET pos = 0 Faire 5 10 0 2 12 8 15 9 14 vrai
11 8 Si T[i] = x Alors 5 10 0 2 12 8 15 9 14 faux
12 11 i ← i + 1 5 10 0 3 12 8 15 9 14
13 7 TantQue i ≤ n ET pos = 0 Faire 5 10 0 3 12 8 15 9 14 vrai
14 8 Si T[i] = x Alors 5 10 0 3 12 8 15 9 14 faux
15 11 i ← i + 1 5 10 0 4 12 8 15 9 14
16 7 TantQue i ≤ n ET pos = 0 Faire 5 10 0 4 12 8 15 9 14 vrai
17 8 Si T[i] = x Alors 5 10 0 4 12 8 15 9 14 faux
18 11 i ← i + 1 5 10 0 5 12 8 15 9 14
19 7 TantQue i ≤ n ET pos = 0 Faire 5 10 0 5 12 8 15 9 14 vrai
20 8 Si T[i] = x Alors 5 10 0 5 12 8 15 9 14 faux
21 11 i ← i + 1 5 10 0 6 12 8 15 9 14
22 7 TantQue i ≤ n ET pos = 0 Faire 5 10 0 6 12 8 15 9 14 faux
23 13 Écrire “case :”, pos 5 10 0 6 12 8 15 9 14 case : 0

Les cinq comparaisons (pas 8, 11, 14, 17 et 20) sont fausses et pos reste 0. Au pas 22, \(i\) vaut 6 et la première condition, \(6\leq5\), est fausse : la boucle s’arrête parce qu’il ne reste plus de case. La case T[6], qui n’existe pas, n’est jamais lue, puisque la comparaison est dans le corps et que le corps n’est exécuté qu’après un test vrai. L’algorithme écrit case : 0.

Le nombre de comparaisons

Le coût d’une recherche se mesure au nombre de comparaisons entre \(x\) et une case. Un parcours complet par Pour, sans arrêt, en fait toujours \(n\) : 5 pour \(x=15\). La recherche avec arrêt en fait 3 pour \(x=15\), et 5 pour \(x=10\), absent. Plus généralement, une valeur présente pour la première fois à la case \(k\) coûte \(k\) comparaisons, une valeur absente en coûte \(n\). La figure montre, en orange, les cases comparées dans les deux cas pour \(x=15\).

Une condition qui lit une case de trop

Une écriture plus courte de la recherche place la comparaison dans la condition de la boucle : TantQue \(i\leq n\) ET T[i] \(\neq x\). Elle convient quand \(x\) est présent. Quand \(x\) est absent, elle échoue :

n ← 5
T : tableau[1..n] d'entiers
T ← [12, 8, 15, 9, 14]
Lire x
i ← 1
TantQue i ≤ n ET T[i] ≠ x Faire
  i ← i + 1
FinTantQue
Écrire "case :", i
Pas Ligne Instruction n x i T[1] T[2] T[3] T[4] T[5] Test Écrit
1 1 n ← 5 5
2 2 T : tableau[1..n] déntiers 5
3 3 T ← [12, 8, 15, 9, 14] 5 12 8 15 9 14
4 4 Lire x 5 10 12 8 15 9 14
5 5 i ← 1 5 10 1 12 8 15 9 14
6 6 TantQue i ≤ n ET T[i] ≠ x Faire 5 10 1 12 8 15 9 14 vrai
7 7 i ← i + 1 5 10 2 12 8 15 9 14
8 6 TantQue i ≤ n ET T[i] ≠ x Faire 5 10 2 12 8 15 9 14 vrai
9 7 i ← i + 1 5 10 3 12 8 15 9 14
10 6 TantQue i ≤ n ET T[i] ≠ x Faire 5 10 3 12 8 15 9 14 vrai
11 7 i ← i + 1 5 10 4 12 8 15 9 14
12 6 TantQue i ≤ n ET T[i] ≠ x Faire 5 10 4 12 8 15 9 14 vrai
13 7 i ← i + 1 5 10 5 12 8 15 9 14
14 6 TantQue i ≤ n ET T[i] ≠ x Faire 5 10 5 12 8 15 9 14 vrai
15 7 i ← i + 1 5 10 6 12 8 15 9 14
16 6 TantQue i ≤ n ET T[i] ≠ x Faire 5 10 6 12 8 15 9 14 erreur arrêt : T[6] hors bornes

Les cinq premiers tests lisent les cases 1 à 5 et sont vrais. Au pas 16, \(i\) vaut 6 : la première partie \(6\leq5\) est fausse, mais la convention du cours évalue les deux membres d’un ET, et la seconde partie lit T[6], qui n’existe pas. L’exécution s’arrête sur un indice hors bornes. Le pseudo-code de Cormen, comme les langages C, Java et Python, arrête l’évaluation d’un ET dès que son premier membre est faux, et ne lirait donc pas T[6] ; le pseudo-code du cours évalue les deux membres. La version avec pos, où la case n’est lue que dans le corps, est correcte avec les deux conventions.

Exemple pas à pas : le maximum et sa position

Le maximum est un accumulateur (Séance 3) ; dans un tableau, on veut souvent aussi sa position. Les températures maximales relevées à Kaolack pendant cinq jours sont 31, 35, 33, 38 et 36 °C.

n ← 5
T : tableau[1..n] d'entiers
T ← [31, 35, 33, 38, 36]
maxi ← T[1]
pos ← 1
Pour i de 2 à n Faire
  Si T[i] > maxi Alors
    maxi ← T[i]
    pos ← i
  FinSi
FinPour
Écrire maxi, pos
Pas Ligne Instruction n maxi pos i T[1] T[2] T[3] T[4] T[5] Test Écrit
1 1 n ← 5 5
2 2 T : tableau[1..n] déntiers 5
3 3 T ← [31, 35, 33, 38, 36] 5 31 35 33 38 36
4 4 maxi ← T[1] 5 31 31 35 33 38 36
5 5 pos ← 1 5 31 1 31 35 33 38 36
6 6 Pour i de 2 à n Faire 5 31 1 2 31 35 33 38 36 vrai
7 7 Si T[i] > maxi Alors 5 31 1 2 31 35 33 38 36 vrai
8 8 maxi ← T[i] 5 35 1 2 31 35 33 38 36
9 9 pos ← i 5 35 2 2 31 35 33 38 36
10 6 Pour i de 2 à n Faire 5 35 2 3 31 35 33 38 36 vrai
11 7 Si T[i] > maxi Alors 5 35 2 3 31 35 33 38 36 faux
12 6 Pour i de 2 à n Faire 5 35 2 4 31 35 33 38 36 vrai
13 7 Si T[i] > maxi Alors 5 35 2 4 31 35 33 38 36 vrai
14 8 maxi ← T[i] 5 38 2 4 31 35 33 38 36
15 9 pos ← i 5 38 4 4 31 35 33 38 36
16 6 Pour i de 2 à n Faire 5 38 4 5 31 35 33 38 36 vrai
17 7 Si T[i] > maxi Alors 5 38 4 5 31 35 33 38 36 faux
18 6 Pour i de 2 à n Faire 5 38 4 6 31 35 33 38 36 faux
19 12 Écrire maxi, pos 5 38 4 31 35 33 38 36 38 4

Le maximum part de la première case, une donnée, et non d’une constante : maxi \(=31\) et pos \(=1\) (pas 4 et 5). La boucle commence donc à la case 2. À chaque tour, la case du tour est comparée au maximum provisoire ; quand elle est plus grande (pas 7 et 13), maxi et pos sont mis à jour ensemble (pas 8 et 9, puis 14 et 15). La boucle fait \(n-1=4\) comparaisons et l’algorithme écrit 38 4 : 38 °C, le quatrième jour.

Quand le maximum apparaît plusieurs fois, le test choisit la position rendue. Sur les températures 31, 38, 33, 38 et 36, le test strict T[i] \(>\) maxi ne change pas la position quand une case égale au maximum est rencontrée : l’algorithme écrit 38 2, la première position. Avec T[i] \(\geq\) maxi, une case égale remplace la position : il écrit 38 4, la dernière.

Modifier un tableau

Les traitements précédents lisent le tableau sans le modifier. D’autres le transforment en place : chaque tour écrit une ou deux cases. Deux règles s’ajoutent alors : une case écrite perd son ancienne valeur, qu’il faut avoir lue ou sauvegardée avant, et le sens du parcours décide de ce qui est lu.

Exemple pas à pas : l’inversion

Inverser un tableau, c’est échanger la première case avec la dernière, la deuxième avec l’avant-dernière, et ainsi de suite : la case \(i\) s’échange avec la case \(n-i+1\), sa symétrique.

n ← 5
T : tableau[1..n] d'entiers
T ← [4, 9, 2, 7, 5]
Pour i de 1 à n div 2 Faire
  tmp ← T[i]
  T[i] ← T[n - i + 1]
  T[n - i + 1] ← tmp
FinPour
Pas Ligne Instruction n i tmp T[1] T[2] T[3] T[4] T[5] Test Écrit
1 1 n ← 5 5
2 2 T : tableau[1..n] déntiers 5
3 3 T ← [4, 9, 2, 7, 5] 5 4 9 2 7 5
4 4 Pour i de 1 à n div 2 Faire 5 1 4 9 2 7 5 vrai
5 5 tmp ← T[i] 5 1 4 4 9 2 7 5
6 6 T[i] ← T[n - i + 1] 5 1 4 5 9 2 7 5
7 7 T[n - i + 1] ← tmp 5 1 4 5 9 2 7 4
8 4 Pour i de 1 à n div 2 Faire 5 2 4 5 9 2 7 4 vrai
9 5 tmp ← T[i] 5 2 9 5 9 2 7 4
10 6 T[i] ← T[n - i + 1] 5 2 9 5 7 2 7 4
11 7 T[n - i + 1] ← tmp 5 2 9 5 7 2 9 4
12 4 Pour i de 1 à n div 2 Faire 5 3 9 5 7 2 9 4 faux

Un échange demande trois affectations et une variable auxiliaire tmp. Au premier tour, tmp reçoit T[1] \(=4\) (pas 5), T[1] reçoit T[5] \(=5\) (pas 6), puis T[5] reçoit tmp (pas 7). Sans tmp, l’affectation du pas 6 effacerait la valeur 4 avant qu’elle soit recopiée. Le second tour échange de la même façon les cases 2 et 4. La borne \(n\) div \(2=2\) arrête la boucle au pas 12 : le tableau vaut 5, 7, 2, 9, 4, et la case du milieu, T[3], n’a pas bougé. La figure montre le pas 6 : T[1], en rouge, reçoit la valeur lue dans T[5], en orange, tandis que l’ancienne valeur 4 est à l’abri dans tmp.

Exemple pas à pas : le décalage circulaire

Au marché de Ziguinchor, cinq vendeuses se partagent la meilleure place à tour de rôle : chaque semaine, la liste se décale d’un cran vers la droite, et la dernière passe en tête. Le décalage recopie chaque case dans sa voisine de droite ; la dernière valeur, qui serait écrasée, est d’abord sauvegardée.

n ← 5
T : tableau[1..n] d'entiers
T ← [4, 9, 2, 7, 5]
der ← T[n]
Pour i de n à 2 pas -1 Faire
  T[i] ← T[i - 1]
FinPour
T[1] ← der
Pas Ligne Instruction n der i T[1] T[2] T[3] T[4] T[5] Test Écrit
1 1 n ← 5 5
2 2 T : tableau[1..n] déntiers 5
3 3 T ← [4, 9, 2, 7, 5] 5 4 9 2 7 5
4 4 der ← T[n] 5 5 4 9 2 7 5
5 5 Pour i de n à 2 pas -1 Faire 5 5 5 4 9 2 7 5 vrai
6 6 T[i] ← T[i - 1] 5 5 5 4 9 2 7 7
7 5 Pour i de n à 2 pas -1 Faire 5 5 4 4 9 2 7 7 vrai
8 6 T[i] ← T[i - 1] 5 5 4 4 9 2 2 7
9 5 Pour i de n à 2 pas -1 Faire 5 5 3 4 9 2 2 7 vrai
10 6 T[i] ← T[i - 1] 5 5 3 4 9 9 2 7
11 5 Pour i de n à 2 pas -1 Faire 5 5 2 4 9 9 2 7 vrai
12 6 T[i] ← T[i - 1] 5 5 2 4 4 9 2 7
13 5 Pour i de n à 2 pas -1 Faire 5 5 1 4 4 9 2 7 faux
14 8 T[1] ← der 5 5 5 4 9 2 7

Le compteur descend de 5 à 2 (pas \(-1\)). Au premier tour, T[5] reçoit T[4] \(=7\) ; l’ancienne valeur de T[5], 5, est déjà dans der (pas 4). Au tour suivant, T[4] reçoit T[3], et ainsi de suite : chaque case est lue avant d’être écrasée, puisque la case lue (\(i-1\)) est à gauche de la case écrite (\(i\)) et que le parcours va de droite à gauche. Le pas 14 place der en tête : le tableau vaut 5, 4, 9, 2, 7.

Le même décalage, parcouru dans l’autre sens, détruit le tableau :

n ← 5
T : tableau[1..n] d'entiers
T ← [4, 9, 2, 7, 5]
der ← T[n]
Pour i de 2 à n Faire
  T[i] ← T[i - 1]
FinPour
T[1] ← der
Pas Ligne Instruction n der i T[1] T[2] T[3] T[4] T[5] Test Écrit
1 1 n ← 5 5
2 2 T : tableau[1..n] déntiers 5
3 3 T ← [4, 9, 2, 7, 5] 5 4 9 2 7 5
4 4 der ← T[n] 5 5 4 9 2 7 5
5 5 Pour i de 2 à n Faire 5 5 2 4 9 2 7 5 vrai
6 6 T[i] ← T[i - 1] 5 5 2 4 4 2 7 5
7 5 Pour i de 2 à n Faire 5 5 3 4 4 2 7 5 vrai
8 6 T[i] ← T[i - 1] 5 5 3 4 4 4 7 5
9 5 Pour i de 2 à n Faire 5 5 4 4 4 4 7 5 vrai
10 6 T[i] ← T[i - 1] 5 5 4 4 4 4 4 5
11 5 Pour i de 2 à n Faire 5 5 5 4 4 4 4 5 vrai
12 6 T[i] ← T[i - 1] 5 5 5 4 4 4 4 4
13 5 Pour i de 2 à n Faire 5 5 6 4 4 4 4 4 faux
14 8 T[1] ← der 5 5 5 4 4 4 4

Au pas 6, T[2] reçoit T[1] \(=4\). Au pas 8, T[3] reçoit T[2], qui vient d’être écrasée et vaut déjà 4 : l’ancienne valeur 9 est perdue. La valeur 4 se propage alors de case en case, et le tableau final vaut 5, 4, 4, 4, 4. La figure montre le pas 12 : la case lue (orange) est celle que le tour précédent vient d’écrire, et la case écrite (rouge) reçoit une copie de la copie.

AvertissementLe sens d’un décalage

Un décalage vers la droite (T[i] \(\leftarrow\) T[i - 1]) se parcourt de la dernière case vers la première ; un décalage vers la gauche (T[i] \(\leftarrow\) T[i + 1]) de la première vers la dernière. Dans les deux cas, chaque case doit être lue avant d’être écrasée.

Les erreurs d’indice

Les erreurs de boucle de la Séance 3 ont, dans un tableau, une conséquence nouvelle : un tour de trop ou de moins se traduit par une case qui n’existe pas, ou par une case qui n’a pas été remplie. Selon le langage, l’exécution s’arrête alors sur une erreur, ou se poursuit avec une valeur quelconque ; dans les deux cas, l’algorithme est faux.

Exemple pas à pas : l’indice hors bornes

L’algorithme suivant compte les hausses de température d’un jour au suivant : chaque tour compare la case \(i+1\) à la case \(i\).

n ← 4
T : tableau[1..n] d'entiers
T ← [31, 35, 33, 38]
c ← 0
Pour i de 1 à n Faire
  Si T[i + 1] > T[i] Alors
    c ← c + 1
  FinSi
FinPour
Écrire "hausses :", c
Pas Ligne Instruction n c i T[1] T[2] T[3] T[4] Test Écrit
1 1 n ← 4 4
2 2 T : tableau[1..n] déntiers 4
3 3 T ← [31, 35, 33, 38] 4 31 35 33 38
4 4 c ← 0 4 0 31 35 33 38
5 5 Pour i de 1 à n Faire 4 0 1 31 35 33 38 vrai
6 6 Si T[i + 1] > T[i] Alors 4 0 1 31 35 33 38 vrai
7 7 c ← c + 1 4 1 1 31 35 33 38
8 5 Pour i de 1 à n Faire 4 1 2 31 35 33 38 vrai
9 6 Si T[i + 1] > T[i] Alors 4 1 2 31 35 33 38 faux
10 5 Pour i de 1 à n Faire 4 1 3 31 35 33 38 vrai
11 6 Si T[i + 1] > T[i] Alors 4 1 3 31 35 33 38 vrai
12 7 c ← c + 1 4 2 3 31 35 33 38
13 5 Pour i de 1 à n Faire 4 2 4 31 35 33 38 vrai
14 6 Si T[i + 1] > T[i] Alors 4 2 4 31 35 33 38 erreur arrêt : T[5] hors bornes

Les trois premiers tours comparent les paires de cases (1, 2), (2, 3) et (3, 4) : deux hausses, aux pas 6 et 11. Au quatrième tour, \(i=4\) et l’expression T[i + 1] désigne T[5] : le tableau n’a que 4 cases, l’indice est hors bornes et l’exécution s’arrête au pas 14, avant d’écrire quoi que ce soit. Un tableau de \(n\) cases contient \(n-1\) paires de cases voisines : la borne correcte est \(n-1\). La figure montre l’arrêt : la case demandée, d’indice 5, est dessinée en pointillés à droite du tableau, et la ligne fautive est surlignée en rouge.

n ← 4
T : tableau[1..n] d'entiers
T ← [31, 35, 33, 38]
c ← 0
Pour i de 1 à n - 1 Faire
  Si T[i + 1] > T[i] Alors
    c ← c + 1
  FinSi
FinPour
Écrire "hausses :", c
Pas Ligne Instruction n c i T[1] T[2] T[3] T[4] Test Écrit
1 1 n ← 4 4
2 2 T : tableau[1..n] déntiers 4
3 3 T ← [31, 35, 33, 38] 4 31 35 33 38
4 4 c ← 0 4 0 31 35 33 38
5 5 Pour i de 1 à n - 1 Faire 4 0 1 31 35 33 38 vrai
6 6 Si T[i + 1] > T[i] Alors 4 0 1 31 35 33 38 vrai
7 7 c ← c + 1 4 1 1 31 35 33 38
8 5 Pour i de 1 à n - 1 Faire 4 1 2 31 35 33 38 vrai
9 6 Si T[i + 1] > T[i] Alors 4 1 2 31 35 33 38 faux
10 5 Pour i de 1 à n - 1 Faire 4 1 3 31 35 33 38 vrai
11 6 Si T[i + 1] > T[i] Alors 4 1 3 31 35 33 38 vrai
12 7 c ← c + 1 4 2 3 31 35 33 38
13 5 Pour i de 1 à n - 1 Faire 4 2 4 31 35 33 38 faux
14 10 Écrire “hausses :”, c 4 2 31 35 33 38 hausses : 2

Le test du pas 13 trouve \(i=4>3\) et la boucle s’arrête ; l’algorithme écrit hausses : 2.

Exemple pas à pas : la case non remplie

Dans l’algorithme suivant, la boucle de remplissage s’arrête une case trop tôt, et la somme lit une case qui n’a jamais reçu de valeur. Les entrées sont 4, puis 12, 8 et 15.

Lire n
T : tableau[1..n] d'entiers
Pour i de 1 à n - 1 Faire
  Lire T[i]
FinPour
s ← 0
Pour i de 1 à n Faire
  s ← s + T[i]
FinPour
Écrire "somme :", s
Pas Ligne Instruction n s i T[1] T[2] T[3] T[4] Test Écrit
1 1 Lire n 4
2 2 T : tableau[1..n] déntiers 4
3 3 Pour i de 1 à n - 1 Faire 4 1 vrai
4 4 Lire T[i] 4 1 12
5 3 Pour i de 1 à n - 1 Faire 4 2 12 vrai
6 4 Lire T[i] 4 2 12 8
7 3 Pour i de 1 à n - 1 Faire 4 3 12 8 vrai
8 4 Lire T[i] 4 3 12 8 15
9 3 Pour i de 1 à n - 1 Faire 4 4 12 8 15 faux
10 6 s ← 0 4 0 12 8 15
11 7 Pour i de 1 à n Faire 4 0 1 12 8 15 vrai
12 8 s ← s + T[i] 4 12 1 12 8 15
13 7 Pour i de 1 à n Faire 4 12 2 12 8 15 vrai
14 8 s ← s + T[i] 4 20 2 12 8 15
15 7 Pour i de 1 à n Faire 4 20 3 12 8 15 vrai
16 8 s ← s + T[i] 4 35 3 12 8 15
17 7 Pour i de 1 à n Faire 4 35 4 12 8 15 vrai
18 8 s ← s + T[i] 4 35 4 12 8 15 ? erreur arrêt : T[4] non remplie

La première boucle va de 1 à \(n-1=3\) : elle remplit trois cases sur quatre et s’arrête au pas 9. La seconde boucle somme les cases 1 à 3 (pas 12, 14 et 16), puis, au pas 18, lit T[4], vide depuis la déclaration : sa valeur n’est pas définie et l’exécution s’arrête. Les deux boucles sont correctes séparément ; c’est leur désaccord sur la borne qui produit l’erreur.

Vérifier les indices

Un indice calculé (\(i+1\), \(i-1\), \(n-i+1\)) sort de l’intervalle 1 à \(n\), quand il en sort, au premier ou au dernier tour : ce sont donc ces deux tours qu’il faut examiner.

AstuceMéthode de vérification des accès
  1. Relever chaque accès T[...] du corps de la boucle.
  2. Calculer son indice pour la première et pour la dernière valeur du compteur : dans Pour \(i\) de 1 à \(n\), T[i + 1] va de 2 à \(n+1\) (hors bornes), T[i - 1] de 0 à \(n-1\) (hors bornes), T[n - i + 1] de \(n\) à 1 (correct).
  3. Pour chaque case lue, vérifier qu’une instruction précédente l’a écrite.
  4. Tracer l’algorithme sur un petit tableau (3 ou 4 cases), puis sur le cas limite d’une seule case.

Exercices corrigés

Les trois exercices suivants reprennent les trois gestes de la séance : dérouler un parcours avec un compteur et un accumulateur, suivre une recherche du minimum et de sa position, raisonner sur la borne d’une boucle qui modifie un tableau. Chaque correction énonce la règle appliquée, donne la trace complète, résume la trace dans un tableau, conclut et signale l’erreur la plus répandue.

Exercice 1 : compter et sommer dans un tableau

Le tableau P contient la pluie, en millimètres, relevée à Ziguinchor pendant six jours.

n ← 6
P : tableau[1..n] d'entiers
P ← [0, 12, 5, 0, 30, 8]
nb ← 0
total ← 0
Pour j de 1 à n Faire
  Si P[j] > 0 Alors
    nb ← nb + 1
    total ← total + P[j]
  FinSi
FinPour
Écrire nb, total, total / nb
  1. Dresser la trace complète, puis relever, pour chaque tour, P[j], le résultat du test de la ligne 7, nb et total après le tour.
  2. Qu’écrit la ligne 12 ?
  3. Combien de fois les lignes 7 et 8 sont-elles exécutées ?
  4. Que se passe-t-il si les six cases valent 0 ? Comment corriger l’algorithme ?
AstuceCorrection

(a) Règle appliquée. Le parcours Pour \(j\) de 1 à \(n\) fait 6 tours ; au tour \(j\), le test du Si lit la case P[j]. S’il est vrai, les lignes 8 et 9 sont exécutées : nb est un compteur (il augmente de 1), total un accumulateur (il augmente de P[j]). S’il est faux, l’exécution revient à l’en-tête.

Pas Ligne Instruction n nb total j P[1] P[2] P[3] P[4] P[5] P[6] Test Écrit
1 1 n ← 6 6
2 2 P : tableau[1..n] déntiers 6
3 3 P ← [0, 12, 5, 0, 30, 8] 6 0 12 5 0 30 8
4 4 nb ← 0 6 0 0 12 5 0 30 8
5 5 total ← 0 6 0 0 0 12 5 0 30 8
6 6 Pour j de 1 à n Faire 6 0 0 1 0 12 5 0 30 8 vrai
7 7 Si P[j] > 0 Alors 6 0 0 1 0 12 5 0 30 8 faux
8 6 Pour j de 1 à n Faire 6 0 0 2 0 12 5 0 30 8 vrai
9 7 Si P[j] > 0 Alors 6 0 0 2 0 12 5 0 30 8 vrai
10 8 nb ← nb + 1 6 1 0 2 0 12 5 0 30 8
11 9 total ← total + P[j] 6 1 12 2 0 12 5 0 30 8
12 6 Pour j de 1 à n Faire 6 1 12 3 0 12 5 0 30 8 vrai
13 7 Si P[j] > 0 Alors 6 1 12 3 0 12 5 0 30 8 vrai
14 8 nb ← nb + 1 6 2 12 3 0 12 5 0 30 8
15 9 total ← total + P[j] 6 2 17 3 0 12 5 0 30 8
16 6 Pour j de 1 à n Faire 6 2 17 4 0 12 5 0 30 8 vrai
17 7 Si P[j] > 0 Alors 6 2 17 4 0 12 5 0 30 8 faux
18 6 Pour j de 1 à n Faire 6 2 17 5 0 12 5 0 30 8 vrai
19 7 Si P[j] > 0 Alors 6 2 17 5 0 12 5 0 30 8 vrai
20 8 nb ← nb + 1 6 3 17 5 0 12 5 0 30 8
21 9 total ← total + P[j] 6 3 47 5 0 12 5 0 30 8
22 6 Pour j de 1 à n Faire 6 3 47 6 0 12 5 0 30 8 vrai
23 7 Si P[j] > 0 Alors 6 3 47 6 0 12 5 0 30 8 vrai
24 8 nb ← nb + 1 6 4 47 6 0 12 5 0 30 8
25 9 total ← total + P[j] 6 4 55 6 0 12 5 0 30 8
26 6 Pour j de 1 à n Faire 6 4 55 7 0 12 5 0 30 8 faux
27 12 Écrire nb, total, total / nb 6 4 55 0 12 5 0 30 8 4 55 13,75

Le résumé par tour se lit aux pas où la ligne 7 est exécutée :

\(j\) P[j] P[j] \(>0\) nb après total après
1 0 faux 0 0
2 12 vrai 1 12
3 5 vrai 2 17
4 0 faux 2 17
5 30 vrai 3 47
6 8 vrai 4 55

Les jours secs (1 et 4) ne changent ni nb ni total : le test est faux et le bloc est sauté.

(b) Après la boucle, nb \(=4\) et total \(=55\). La ligne 12 calcule \(55/4=13{,}75\) et écrit 4 55 13,75 : il est tombé en moyenne 13,75 mm par jour de pluie.

(c) La ligne 7 est exécutée une fois par tour, soit 6 fois (pas 7, 9, 13, 17, 19 et 23) ; la ligne 8 une fois par test vrai, soit 4 fois.

(d) Si les six cases valent 0, les six tests sont faux et nb reste 0 : la ligne 12 divise par zéro et l’exécution s’arrête.

Pas Ligne Instruction n nb total j P[1] P[2] P[3] P[4] P[5] P[6] Test Écrit
1 1 n ← 6 6
2 2 P : tableau[1..n] déntiers 6
3 3 P ← [0, 0, 0, 0, 0, 0] 6 0 0 0 0 0 0
4 4 nb ← 0 6 0 0 0 0 0 0 0
5 5 total ← 0 6 0 0 0 0 0 0 0 0
6 6 Pour j de 1 à n Faire 6 0 0 1 0 0 0 0 0 0 vrai
7 7 Si P[j] > 0 Alors 6 0 0 1 0 0 0 0 0 0 faux
8 6 Pour j de 1 à n Faire 6 0 0 2 0 0 0 0 0 0 vrai
9 7 Si P[j] > 0 Alors 6 0 0 2 0 0 0 0 0 0 faux
10 6 Pour j de 1 à n Faire 6 0 0 3 0 0 0 0 0 0 vrai
11 7 Si P[j] > 0 Alors 6 0 0 3 0 0 0 0 0 0 faux
12 6 Pour j de 1 à n Faire 6 0 0 4 0 0 0 0 0 0 vrai
13 7 Si P[j] > 0 Alors 6 0 0 4 0 0 0 0 0 0 faux
14 6 Pour j de 1 à n Faire 6 0 0 5 0 0 0 0 0 0 vrai
15 7 Si P[j] > 0 Alors 6 0 0 5 0 0 0 0 0 0 faux
16 6 Pour j de 1 à n Faire 6 0 0 6 0 0 0 0 0 0 vrai
17 7 Si P[j] > 0 Alors 6 0 0 6 0 0 0 0 0 0 faux
18 6 Pour j de 1 à n Faire 6 0 0 7 0 0 0 0 0 0 faux
19 12 Écrire nb, total, total / nb 6 0 0 0 0 0 0 0 0 erreur arrêt : division par zéro

La correction consiste à tester nb avant de diviser : Si \(\texttt{nb}>0\) Alors Écrire nb, total, total / nb Sinon Écrire "aucun jour de pluie" FinSi.

Conclusion. Un compteur et un accumulateur peuvent partager le même parcours et le même test ; une moyenne calculée après la boucle doit tenir compte du cas où le compteur est nul.

AvertissementErreur fréquente

Confondre le compteur et l’indice : nb compte les jours de pluie (4), j parcourt tous les jours (1 à 6). Écrire total / j après la boucle n’a pas de sens, car la valeur du compteur d’un Pour n’est pas définie après FinPour ; et total / n donne la moyenne sur les six jours (\(55/6\)), une autre grandeur.

Exercice 2 : le minimum et sa position

Le tableau T contient le prix, en francs CFA, du kilo de mangues chez cinq vendeuses du marché Tilène, à Dakar.

n ← 5
T : tableau[1..n] d'entiers
T ← [700, 500, 900, 500, 600]
mini ← T[1]
pos ← 1
Pour i de 2 à n Faire
  Si T[i] < mini Alors
    mini ← T[i]
    pos ← i
  FinSi
FinPour
Écrire mini, pos
  1. Dresser la trace complète, puis relever, pour chaque tour, T[i], le résultat du test de la ligne 7, mini et pos après le tour.
  2. Qu’écrit la ligne 12 ?
  3. Qu’écrit l’algorithme si la ligne 7 devient Si T[i] \(\leq\) mini Alors ?
  4. Combien de comparaisons la ligne 7 fait-elle pour un tableau de \(n\) cases ? Que donnerait l’initialisation mini \(\leftarrow 0\) ?
AstuceCorrection

(a) Règle appliquée. Le minimum part de la première case (pas 4) et sa position de 1 (pas 5) ; la boucle examine les cases 2 à \(n\). À chaque tour, la case est comparée au minimum provisoire ; si elle est plus petite, le minimum et sa position sont mis à jour.

Pas Ligne Instruction n mini pos i T[1] T[2] T[3] T[4] T[5] Test Écrit
1 1 n ← 5 5
2 2 T : tableau[1..n] déntiers 5
3 3 T ← [700, 500, 900, 500, 600] 5 700 500 900 500 600
4 4 mini ← T[1] 5 700 700 500 900 500 600
5 5 pos ← 1 5 700 1 700 500 900 500 600
6 6 Pour i de 2 à n Faire 5 700 1 2 700 500 900 500 600 vrai
7 7 Si T[i] < mini Alors 5 700 1 2 700 500 900 500 600 vrai
8 8 mini ← T[i] 5 500 1 2 700 500 900 500 600
9 9 pos ← i 5 500 2 2 700 500 900 500 600
10 6 Pour i de 2 à n Faire 5 500 2 3 700 500 900 500 600 vrai
11 7 Si T[i] < mini Alors 5 500 2 3 700 500 900 500 600 faux
12 6 Pour i de 2 à n Faire 5 500 2 4 700 500 900 500 600 vrai
13 7 Si T[i] < mini Alors 5 500 2 4 700 500 900 500 600 faux
14 6 Pour i de 2 à n Faire 5 500 2 5 700 500 900 500 600 vrai
15 7 Si T[i] < mini Alors 5 500 2 5 700 500 900 500 600 faux
16 6 Pour i de 2 à n Faire 5 500 2 6 700 500 900 500 600 faux
17 12 Écrire mini, pos 5 500 2 700 500 900 500 600 500 2
\(i\) T[i] T[i] \(<\) mini mini après pos après
2 500 vrai 500 2
3 900 faux 500 2
4 500 faux 500 2
5 600 faux 500 2

Un seul test est vrai, au tour \(i=2\) (pas 7). Au tour \(i=4\), la case vaut 500, autant que le minimum : \(500<500\) est faux (pas 13), et la position ne change pas.

(b) La ligne 12 écrit 500 2 : le prix le plus bas est 500 F, pratiqué d’abord par la deuxième vendeuse.

(c) Avec \(\leq\), le test du tour \(i=4\) devient vrai : mini reçoit encore 500 et pos passe à 4.

Pas Ligne Instruction n mini pos i T[1] T[2] T[3] T[4] T[5] Test Écrit
1 1 n ← 5 5
2 2 T : tableau[1..n] déntiers 5
3 3 T ← [700, 500, 900, 500, 600] 5 700 500 900 500 600
4 4 mini ← T[1] 5 700 700 500 900 500 600
5 5 pos ← 1 5 700 1 700 500 900 500 600
6 6 Pour i de 2 à n Faire 5 700 1 2 700 500 900 500 600 vrai
7 7 Si T[i] ≤ mini Alors 5 700 1 2 700 500 900 500 600 vrai
8 8 mini ← T[i] 5 500 1 2 700 500 900 500 600
9 9 pos ← i 5 500 2 2 700 500 900 500 600
10 6 Pour i de 2 à n Faire 5 500 2 3 700 500 900 500 600 vrai
11 7 Si T[i] ≤ mini Alors 5 500 2 3 700 500 900 500 600 faux
12 6 Pour i de 2 à n Faire 5 500 2 4 700 500 900 500 600 vrai
13 7 Si T[i] ≤ mini Alors 5 500 2 4 700 500 900 500 600 vrai
14 8 mini ← T[i] 5 500 2 4 700 500 900 500 600
15 9 pos ← i 5 500 4 4 700 500 900 500 600
16 6 Pour i de 2 à n Faire 5 500 4 5 700 500 900 500 600 vrai
17 7 Si T[i] ≤ mini Alors 5 500 4 5 700 500 900 500 600 faux
18 6 Pour i de 2 à n Faire 5 500 4 6 700 500 900 500 600 faux
19 12 Écrire mini, pos 5 500 4 700 500 900 500 600 500 4

L’algorithme écrit 500 4 : le test strict rend la première position du minimum, le test large la dernière.

(d) Une comparaison par tour, pour \(i\) de 2 à \(n\) : \(n-1\) comparaisons, ici 4. La première case n’est comparée à rien : elle sert d’initialisation. Avec mini \(\leftarrow 0\), aucun prix (tous positifs) n’est inférieur à 0 : mini resterait 0, une valeur absente du tableau, et pos resterait 1.

Conclusion. Un minimum et sa position s’initialisent sur la première case, se mettent à jour ensemble, et le choix entre \(<\) et \(\leq\) décide de la position rendue quand le minimum apparaît plusieurs fois.

AvertissementErreur fréquente

Mettre à jour mini sans pos (ou l’inverse) : les deux variables doivent changer dans le même bloc Alors. Autre erreur répandue : écrire pos \(\leftarrow\) T[i] au lieu de pos \(\leftarrow\) i, qui range une valeur à la place d’un indice.

Exercice 3 : la borne d’une inversion

L’algorithme suivant doit inverser le tableau T.

n ← 4
T : tableau[1..n] d'entiers
T ← [2, 4, 6, 8]
Pour i de 1 à n Faire
  tmp ← T[i]
  T[i] ← T[n - i + 1]
  T[n - i + 1] ← tmp
FinPour
  1. Dresser la trace complète et donner le contenu de T après chaque tour.
  2. Que contient T à la fin ? Expliquer.
  3. Corriger la ligne 4. Combien de tours fait la boucle corrigée pour \(n=4\) ? pour \(n=5\) ?
  4. Pour \(n=5\), quelle case ne bouge pas ? Pourquoi ?
AstuceCorrection

(a) Règle appliquée. Le tour \(i\) échange les cases \(i\) et \(n-i+1\) par trois affectations : sauvegarde de T[i] dans tmp, copie de la case symétrique dans la case \(i\), copie de tmp dans la case symétrique.

Pas Ligne Instruction n i tmp T[1] T[2] T[3] T[4] Test Écrit
1 1 n ← 4 4
2 2 T : tableau[1..n] déntiers 4
3 3 T ← [2, 4, 6, 8] 4 2 4 6 8
4 4 Pour i de 1 à n Faire 4 1 2 4 6 8 vrai
5 5 tmp ← T[i] 4 1 2 2 4 6 8
6 6 T[i] ← T[n - i + 1] 4 1 2 8 4 6 8
7 7 T[n - i + 1] ← tmp 4 1 2 8 4 6 2
8 4 Pour i de 1 à n Faire 4 2 2 8 4 6 2 vrai
9 5 tmp ← T[i] 4 2 4 8 4 6 2
10 6 T[i] ← T[n - i + 1] 4 2 4 8 6 6 2
11 7 T[n - i + 1] ← tmp 4 2 4 8 6 4 2
12 4 Pour i de 1 à n Faire 4 3 4 8 6 4 2 vrai
13 5 tmp ← T[i] 4 3 4 8 6 4 2
14 6 T[i] ← T[n - i + 1] 4 3 4 8 6 6 2
15 7 T[n - i + 1] ← tmp 4 3 4 8 4 6 2
16 4 Pour i de 1 à n Faire 4 4 4 8 4 6 2 vrai
17 5 tmp ← T[i] 4 4 2 8 4 6 2
18 6 T[i] ← T[n - i + 1] 4 4 2 8 4 6 8
19 7 T[n - i + 1] ← tmp 4 4 2 2 4 6 8
20 4 Pour i de 1 à n Faire 4 5 2 2 4 6 8 faux
\(i\) cases échangées T après le tour
1 1 et 4 8, 4, 6, 2
2 2 et 3 8, 6, 4, 2
3 3 et 2 8, 4, 6, 2
4 4 et 1 2, 4, 6, 8

(b) T contient 2, 4, 6, 8, son état de départ. Après deux tours, le tableau est inversé (8, 6, 4, 2). Les tours 3 et 4 échangent de nouveau les mêmes paires, (3, 2) puis (4, 1), et défont l’inversion : chaque paire est échangée deux fois.

(c) Chaque paire ne doit être échangée qu’une fois : la boucle doit s’arrêter à la moitié du tableau, Pour \(i\) de 1 à \(n\) div 2. Pour \(n=4\), \(4\) div \(2=2\) tours :

Pas Ligne Instruction n i tmp T[1] T[2] T[3] T[4] Test Écrit
1 1 n ← 4 4
2 2 T : tableau[1..n] déntiers 4
3 3 T ← [2, 4, 6, 8] 4 2 4 6 8
4 4 Pour i de 1 à n div 2 Faire 4 1 2 4 6 8 vrai
5 5 tmp ← T[i] 4 1 2 2 4 6 8
6 6 T[i] ← T[n - i + 1] 4 1 2 8 4 6 8
7 7 T[n - i + 1] ← tmp 4 1 2 8 4 6 2
8 4 Pour i de 1 à n div 2 Faire 4 2 2 8 4 6 2 vrai
9 5 tmp ← T[i] 4 2 4 8 4 6 2
10 6 T[i] ← T[n - i + 1] 4 2 4 8 6 6 2
11 7 T[n - i + 1] ← tmp 4 2 4 8 6 4 2
12 4 Pour i de 1 à n div 2 Faire 4 3 4 8 6 4 2 faux

Le tableau final est 8, 6, 4, 2. Pour \(n=5\), \(5\) div \(2=2\) tours également : sur 2, 4, 6, 8, 10, la boucle corrigée donne 10, 8, 6, 4, 2.

(d) Pour \(n=5\), la case 3 est sa propre symétrique (\(5-3+1=3\)) : elle n’a pas à bouger, et la borne \(5\) div \(2=2\) arrête la boucle avant elle. Le quotient entier écarte justement la case du milieu quand \(n\) est impair.

Conclusion. Une boucle qui traite des paires de cases fait autant de tours qu’il y a de paires, et non de cases : \(n\) div 2 pour une inversion, \(n-1\) pour des cases voisines.

AvertissementErreur fréquente

Échanger sans variable auxiliaire, par T[i] \(\leftarrow\) T[n - i + 1] puis T[n - i + 1] \(\leftarrow\) T[i] : la seconde affectation recopie la valeur qui vient d’être écrite, et les deux cases finissent égales. Autre erreur répandue : arrêter la trace à la fin du deuxième tour, quand le tableau « semble » inversé, alors que la boucle continue jusqu’à sa borne.

À retenir

Traitement Boucle Tours Point de vigilance
somme, comptage Pour \(i\) de 1 à \(n\) \(n\) accumulateur et compteur initialisés avant
recherche avec arrêt TantQue \(i\leq n\) ET \(\texttt{pos}=0\) de 1 à \(n\) \(\texttt{pos}=0\) : absent ; case lue dans le corps
maximum et position Pour \(i\) de 2 à \(n\) \(n-1\) départ sur T[1] ; \(>\) : première position
inversion Pour \(i\) de 1 à \(n\) div 2 \(n\) div 2 échange par une variable auxiliaire
décalage vers la droite Pour \(i\) de \(n\) à 2 pas \(-1\) \(n-1\) lire chaque case avant de l’écraser
  • Un tableau de \(n\) cases a les indices 1 à \(n\) ; T[i] est le contenu de la case d’indice \(i\).
  • Parcourir un tableau, c’est une boucle Pour sur ses indices ; une recherche qui s’arrête est un TantQue.
  • Une case doit être écrite avant d’être lue ; un indice doit rester entre 1 et \(n\).
  • Les erreurs d’indice se cherchent aux tours extrêmes, \(i=1\) et \(i=n\), et sur un tableau d’une seule case.

Prochaine séance

La Séance 5 écrit une fois, sous forme de fonctions et de procédures, les traitements de cette séance (maximum, recherche, inversion), avec le tableau et sa taille en paramètres, et les appelle depuis l’algorithme principal.

Références

  • Cormen — Algorithms Unlocked, MIT Press, 2013 (ch. 2, « How to Describe and Evaluate Computer Algorithms » : recherche dans un tableau \(A[1..n]\)).
  • Cormen, Leiserson, Rivest, Stein — Introduction to Algorithms, 4e éd., MIT Press, 2022 (ch. 2, « Getting Started », § 2.1 : tableaux \(A[1:n]\), recherche linéaire en exercice).
  • Bhargava — Grokking Algorithms, 2e éd., Manning, 2024 (ch. 2, « Selection Sort » : tableaux).
  • Notes de cours en ligne : CS50 (Harvard), 6.100A (MIT), CS106A (Stanford), séances sur les tableaux.

Pour cette séance

Les slides

À lire en ligne

Retour au sommet