Séance 3 — Les boucles

Répéter une action, compter, accumuler, s’arrêter

Séance 3 d’Algorithmique : répéter une action, compter, accumuler, s’arrêter.
Auteur

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

NoteNavigation conceptuelle

Amont. Les variables, l’affectation et la trace d’exécution (Séance 1) ; les conditions Si … Alors … Sinon et les booléens ET, OU, NON (Séance 2). Une boucle n’ajoute qu’une chose : une condition testée à nouveau après chaque passage dans un bloc.

Aval. Parcourir un tableau (Séance 4), c’est une boucle Pour sur ses indices, avec les compteurs et les accumulateurs de cette séance.

ImportantObjectifs
  • Dérouler à la main une boucle TantQue, Pour ou Répéter dans un tableau d’état des variables.
  • Repérer l’initialisation, la condition, le corps et la progression d’une boucle.
  • Écrire un compteur et un accumulateur avec la bonne valeur initiale.
  • Contrôler une saisie au clavier jusqu’à obtenir une valeur valide.
  • Reconnaître, par une trace, une boucle infinie et une erreur de décalage d’une unité (off-by-one error).
  • Compter les tours de deux boucles imbriquées.

Les conventions du pseudo-code

Tout le cours écrit ses algorithmes dans un même pseudo-code français, indépendant de tout langage de programmation. Les séances précédentes en ont fixé les instructions de base ; la présente séance y ajoute les trois boucles. Le tableau ci-dessous rassemble les conventions utilisées dans la suite.

É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\)) ; pas de 1 par défaut
Répéter … Jusqu’à \(C\) corps exécuté, puis test ; sortie quand \(C\) est vraie ; au moins un tour
retrait de deux espaces, mot de fin délimitent le corps d’une boucle ou d’un Si

Les lignes des algorithmes sont numérotées. Une trace d’exécution les suit dans l’ordre où elles sont exécutées : chaque ligne du tableau de trace est un pas, qui donne le numéro de la ligne exécutée, l’état des variables après ce pas (la valeur qui vient de changer est en gras), le résultat d’un test quand la ligne en contient un, et ce qu’écrit Écrire.

La boucle TantQue

Pourquoi répéter

Une condition exécute un bloc d’instructions au plus une fois. Or beaucoup de tâches demandent de refaire le même travail un nombre de fois qui n’est pas connu à l’écriture de l’algorithme : écrire les nombres de 1 à \(n\) pour un \(n\) lu au clavier, verser une cotisation chaque semaine jusqu’à atteindre un objectif, relire une note tant qu’elle est invalide. Écrire chaque répétition est impossible quand leur nombre dépend des données. La boucle répond à ce besoin : elle décrit le travail une seule fois, et une condition décide s’il faut le refaire.

À la borne-fontaine du quartier, à Thiès, Khadim remplit les bidons de la famille. Personne ne lui dicte vingt fois le geste ; on lui dit le geste une fois, et quand s’arrêter : tant qu’il reste un bidon vide sur la charrette.

NoteBoucle TantQue

TantQue \(C\) Faire \(B\) FinTantQue évalue la condition \(C\) ; si elle est vraie, le corps \(B\) est exécuté (c’est un tour), puis l’exécution revient au test ; si elle est fausse, l’exécution passe à l’instruction qui suit FinTantQue.

Une boucle a quatre éléments. L’initialisation, placée avant la boucle, donne leur valeur de départ aux variables de la condition. La condition est évaluée avant chaque tour. Le corps fait le travail. La progression, une instruction du corps, modifie une variable de la condition pour que celle-ci finisse par devenir fausse. L’organigramme ci-dessous dessine ces quatre éléments pour l’algorithme de la section 2.2 ; la seule sortie est la branche « faux » du test.

Exemple pas à pas : le comptage de 1 à \(n\)

L’algorithme suivant lit un entier \(n\), écrit « tour » suivi du numéro du tour pour chaque valeur de \(i\) de 1 à \(n\), puis écrit la valeur de \(i\) après la boucle. L’entrée au clavier est 3.

Lire n
i ← 1
TantQue i ≤ n Faire
  Écrire "tour", i
  i ← i + 1
FinTantQue
Écrire "fin, i =", i
Pas Ligne Instruction n i Test Écrit
1 1 Lire n 3
2 2 i ← 1 3 1
3 3 TantQue i ≤ n Faire 3 1 vrai
4 4 Écrire “tour”, i 3 1 tour 1
5 5 i ← i + 1 3 2
6 3 TantQue i ≤ n Faire 3 2 vrai
7 4 Écrire “tour”, i 3 2 tour 2
8 5 i ← i + 1 3 3
9 3 TantQue i ≤ n Faire 3 3 vrai
10 4 Écrire “tour”, i 3 3 tour 3
11 5 i ← i + 1 3 4
12 3 TantQue i ≤ n Faire 3 4 faux
13 7 Écrire “fin, i =”, i 3 4 fin, i = 4

La trace se lit ligne par ligne. Les pas 1 et 2 initialisent \(n\) et \(i\). Le pas 3 est le premier test : \(1\leq3\) est vrai, l’exécution entre dans le corps, écrit tour 1 (pas 4), puis la progression porte \(i\) à 2 (pas 5). La ligne 6, FinTantQue, ne produit pas de pas : elle renvoie au test de la ligne 3. Le même enchaînement se répète pour \(i=2\) et \(i=3\). Au pas 12, \(i\) vaut 4 et \(4\leq3\) est faux : la boucle s’arrête et l’exécution passe à la ligne 7, qui écrit fin, i = 4.

Deux faits se lisent sur ce tableau. La boucle a fait trois tours mais quatre tests (pas 3, 6, 9 et 12) : une boucle TantQue de \(k\) tours fait \(k+1\) tests, le dernier étant celui qui échoue. Après la boucle, \(i\) vaut 4, c’est-à-dire la première valeur qui rend la condition fausse, et non la dernière valeur utilisée dans le corps. La figure suivante montre deux pas successifs : la ligne exécutée surlignée, l’état des variables à droite.

À gauche, le pas 4 : la ligne 4 vient d’écrire tour 1, et l’état des variables n’a pas changé. À droite, le pas 5 : la progression a porté \(i\) à 2, la seule case modifiée du tableau, encadrée. Chaque tour de la boucle reproduit ce motif de trois pas : test, écriture, progression. Les deux derniers pas de la trace montrent la sortie de boucle.

Au pas 12, le test de la ligne 3 rend « faux » : la ligne surlignée passe directement de la ligne 3 à la ligne 7, sans repasser par le corps. La ligne 6, FinTantQue, n’est pas exécutée comme une instruction : elle marque seulement la fin du corps.

La sortie de l’algorithme est :

tour 1
tour 2
tour 3
fin, i = 4

Le cas de zéro tour

Le test a lieu avant le corps. Avec l’entrée 0, le premier test trouve \(i=1\) et \(1\leq0\) faux : le corps n’est jamais exécuté.

Pas Ligne Instruction n i Test Écrit
1 1 Lire n 0
2 2 i ← 1 0 1
3 3 TantQue i ≤ n Faire 0 1 faux
4 7 Écrire “fin, i =”, i 0 1 fin, i = 1

La boucle n’a rien écrit et \(i\) garde sa valeur initiale ; la seule ligne écrite est fin, i = 1. Ce comportement est voulu : pour \(n=0\), « écrire les nombres de 1 à \(n\) » ne doit rien écrire. Toute boucle se vérifie sur ce cas limite.

AvertissementUne boucle ne s’arrête qu’à un test

L’arrêt n’a lieu qu’au moment du test, jamais au milieu du corps, et seulement si une instruction du corps a modifié une variable de la condition. Sans progression, la condition garde sa valeur : vraie, la boucle ne s’arrête jamais (section 6) ; fausse, elle ne fait aucun tour.

Compteur et accumulateur

Les variables d’une boucle survivent d’un tour au suivant. Cette propriété permet de construire, tour après tour, un résultat global : une somme, un nombre d’éléments, un produit, un maximum. Deux schémas reviennent dans presque tous les algorithmes du cours.

NoteCompteur et accumulateur

Un compteur est une variable augmentée de 1 à chaque tour où un événement se produit. Un accumulateur est une variable qui combine, à chaque tour, sa valeur avec une nouvelle donnée : par \(+\) pour une somme, par \(\times\) pour un produit, par « le plus grand des deux » pour un maximum. Les deux sont initialisés avant la boucle, mis à jour dans le corps et lus après la boucle.

Dans un car rapide de Dakar, le receveur fait un trait sur son carnet à chaque passager qui monte et glisse le prix du ticket dans sa sacoche. Au départ du garage, le carnet est vierge et la sacoche vide ; au terminus, le carnet donne le nombre de passagers, la sacoche la recette.

Exemple pas à pas : la somme \(1+2+\dots+n\)

L’accumulateur \(s\) reçoit à chaque tour la valeur de \(i\). L’entrée est 4.

Lire n
s ← 0
i ← 1
TantQue i ≤ n Faire
  s ← s + i
  i ← i + 1
FinTantQue
Écrire "somme :", s
Pas Ligne Instruction n s i Test Écrit
1 1 Lire n 4
2 2 s ← 0 4 0
3 3 i ← 1 4 0 1
4 4 TantQue i ≤ n Faire 4 0 1 vrai
5 5 s ← s + i 4 1 1
6 6 i ← i + 1 4 1 2
7 4 TantQue i ≤ n Faire 4 1 2 vrai
8 5 s ← s + i 4 3 2
9 6 i ← i + 1 4 3 3
10 4 TantQue i ≤ n Faire 4 3 3 vrai
11 5 s ← s + i 4 6 3
12 6 i ← i + 1 4 6 4
13 4 TantQue i ≤ n Faire 4 6 4 vrai
14 5 s ← s + i 4 10 4
15 6 i ← i + 1 4 10 5
16 4 TantQue i ≤ n Faire 4 10 5 faux
17 8 Écrire “somme :”, s 4 10 5 somme : 10

Les tests vrais des pas 4, 7, 10 et 13 ouvrent les quatre tours de la boucle ; à chaque tour, \(s\) augmente de la valeur courante de \(i\) (pas 5, 8, 11 et 14) : \(0+1=1\), \(1+2=3\), \(3+3=6\), \(6+4=10\). Le test du pas 16 trouve \(i=5\) et la boucle s’arrête ; la ligne 8 écrit somme : 10. Après \(k\) tours, \(s\) contient exactement \(1+2+\dots+k\) : c’est vrai dès \(k=0\), puisque \(s\) part de 0.

Exemple pas à pas : le compteur des notes d’au moins 10

Le compteur admis n’augmente qu’aux tours où la note lue vaut au moins 10. La variable k compte tous les tours et commande la boucle. Les entrées sont : 3 notes, puis 12, 8 et 15.

Lire n
admis ← 0
k ← 0
TantQue k < n Faire
  Lire note
  Si note ≥ 10 Alors
    admis ← admis + 1
  FinSi
  k ← k + 1
FinTantQue
Écrire "admis :", admis
Pas Ligne Instruction n admis k note Test Écrit
1 1 Lire n 3
2 2 admis ← 0 3 0
3 3 k ← 0 3 0 0
4 4 TantQue k < n Faire 3 0 0 vrai
5 5 Lire note 3 0 0 12
6 6 Si note ≥ 10 Alors 3 0 0 12 vrai
7 7 admis ← admis + 1 3 1 0 12
8 9 k ← k + 1 3 1 1 12
9 4 TantQue k < n Faire 3 1 1 12 vrai
10 5 Lire note 3 1 1 8
11 6 Si note ≥ 10 Alors 3 1 1 8 faux
12 9 k ← k + 1 3 1 2 8
13 4 TantQue k < n Faire 3 1 2 8 vrai
14 5 Lire note 3 1 2 15
15 6 Si note ≥ 10 Alors 3 1 2 15 vrai
16 7 admis ← admis + 1 3 2 2 15
17 9 k ← k + 1 3 2 3 15
18 4 TantQue k < n Faire 3 2 3 15 faux
19 11 Écrire “admis :”, admis 3 2 3 15 admis : 2

La différence entre les deux variables se lit dans la colonne du test : k augmente à chaque tour (pas 9, 13 et 17), tandis que admis n’augmente qu’aux pas où le test du Si est vrai (pas 7 et 16, pour les notes 12 et 15). Au pas 11, la note 8 rend ce test faux et la ligne 7 est sautée. L’algorithme écrit admis : 2.

Exemple pas à pas : le maximum d’une suite saisie

Le maximum est un accumulateur dont l’opération est « le plus grand des deux ». Il ne part pas d’une constante mais de la première valeur lue. Les entrées sont : 3 nombres, puis 31, 35 et 33.

Lire n
Lire x
maxi ← x
k ← 1
TantQue k < n Faire
  Lire x
  Si x > maxi Alors
    maxi ← x
  FinSi
  k ← k + 1
FinTantQue
Écrire "maximum :", maxi
Pas Ligne Instruction n x maxi k Test Écrit
1 1 Lire n 3
2 2 Lire x 3 31
3 3 maxi ← x 3 31 31
4 4 k ← 1 3 31 31 1
5 5 TantQue k < n Faire 3 31 31 1 vrai
6 6 Lire x 3 35 31 1
7 7 Si x > maxi Alors 3 35 31 1 vrai
8 8 maxi ← x 3 35 35 1
9 10 k ← k + 1 3 35 35 2
10 5 TantQue k < n Faire 3 35 35 2 vrai
11 6 Lire x 3 33 35 2
12 7 Si x > maxi Alors 3 33 35 2 faux
13 10 k ← k + 1 3 33 35 3
14 5 TantQue k < n Faire 3 33 35 3 faux
15 12 Écrire “maximum :”, maxi 3 33 35 3 maximum : 35

Au pas 3, maxi reçoit la première valeur, 31. Au premier tour, 35 est plus grand : maxi passe à 35 (pas 8). Au second, \(33>35\) est faux et maxi ne change pas. À tout moment, maxi est le plus grand des nombres déjà lus ; l’algorithme écrit maximum : 35.

La valeur initiale

Après \(k\) tours, un accumulateur contient le résultat de son opération sur les \(k\) premières données : \(s_k=x_1+\dots+x_k\). Pour que cette phrase soit vraie dès le départ (\(k=0\), ou \(k=1\) pour un maximum), il faut partir de l’élément neutre de l’opération : 0 pour une somme (\(0+x=x\)), 1 pour un produit (\(1\times x=x\)), ou, pour un maximum, de la première donnée, car aucun entier ne joue le rôle d’élément neutre du maximum. C’est aussi ce qui donne le bon résultat quand la boucle ne fait aucun tour.

AvertissementMauvaise valeur initiale

Un produit initialisé à 0 reste nul à chaque tour, puisque \(0\times x=0\). Un maximum initialisé à 0 donne un résultat faux sur des nombres tous négatifs (section 3.5). Enfin, une initialisation placée dans le corps remet l’accumulateur à sa valeur de départ à chaque tour : il ne garde que la dernière donnée.

Exemple pas à pas : un maximum initialisé à 0

Le relevé des températures minimales d’une nuit d’harmattan à Kédougou ne comporte, dans cet exemple, que des valeurs négatives : \(-3\), \(-7\) et \(-2\). Dans l’algorithme suivant, le maximum part de la constante 0 au lieu de la première valeur lue. Les entrées sont 3, puis \(-3\), \(-7\) et \(-2\).

Lire n
maxi ← 0
k ← 0
TantQue k < n Faire
  Lire x
  Si x > maxi Alors
    maxi ← x
  FinSi
  k ← k + 1
FinTantQue
Écrire "maximum :", maxi
Pas Ligne Instruction n maxi k x Test Écrit
1 1 Lire n 3
2 2 maxi ← 0 3 0
3 3 k ← 0 3 0 0
4 4 TantQue k < n Faire 3 0 0 vrai
5 5 Lire x 3 0 0 \(-3\)
6 6 Si x > maxi Alors 3 0 0 \(-3\) faux
7 9 k ← k + 1 3 0 1 \(-3\)
8 4 TantQue k < n Faire 3 0 1 \(-3\) vrai
9 5 Lire x 3 0 1 \(-7\)
10 6 Si x > maxi Alors 3 0 1 \(-7\) faux
11 9 k ← k + 1 3 0 2 \(-7\)
12 4 TantQue k < n Faire 3 0 2 \(-7\) vrai
13 5 Lire x 3 0 2 \(-2\)
14 6 Si x > maxi Alors 3 0 2 \(-2\) faux
15 9 k ← k + 1 3 0 3 \(-2\)
16 4 TantQue k < n Faire 3 0 3 \(-2\) faux
17 11 Écrire “maximum :”, maxi 3 0 3 \(-2\) maximum : 0

Les trois tests du Si (pas 6, 10 et 14) comparent une valeur négative à 0 et rendent tous « faux » : la ligne 7 n’est jamais exécutée et maxi garde sa valeur initiale jusqu’au bout. L’algorithme écrit maximum : 0, une valeur qui ne figure même pas parmi les données. La version correcte lit la première valeur avant la boucle et en fait la valeur initiale du maximum ; le compteur k part alors de 1, puisqu’une valeur est déjà lue.

Lire n
Lire x
maxi ← x
k ← 1
TantQue k < n Faire
  Lire x
  Si x > maxi Alors
    maxi ← x
  FinSi
  k ← k + 1
FinTantQue
Écrire "maximum :", maxi
Pas Ligne Instruction n x maxi k Test Écrit
1 1 Lire n 3
2 2 Lire x 3 \(-3\)
3 3 maxi ← x 3 \(-3\) \(-3\)
4 4 k ← 1 3 \(-3\) \(-3\) 1
5 5 TantQue k < n Faire 3 \(-3\) \(-3\) 1 vrai
6 6 Lire x 3 \(-7\) \(-3\) 1
7 7 Si x > maxi Alors 3 \(-7\) \(-3\) 1 faux
8 10 k ← k + 1 3 \(-7\) \(-3\) 2
9 5 TantQue k < n Faire 3 \(-7\) \(-3\) 2 vrai
10 6 Lire x 3 \(-2\) \(-3\) 2
11 7 Si x > maxi Alors 3 \(-2\) \(-3\) 2 vrai
12 8 maxi ← x 3 \(-2\) \(-2\) 2
13 10 k ← k + 1 3 \(-2\) \(-2\) 3
14 5 TantQue k < n Faire 3 \(-2\) \(-2\) 3 faux
15 12 Écrire “maximum :”, maxi 3 \(-2\) \(-2\) 3 maximum : -2

maxi vaut \(-3\) dès le pas 3. Au premier tour, \(-7>-3\) est faux ; au second, \(-2>-3\) est vrai et maxi passe à \(-2\) (pas 12). L’algorithme écrit maximum : -2. La boucle fait \(n-1=2\) tours, et non 3 : la première valeur est traitée par l’initialisation.

La boucle Pour

Dans la somme, trois lignes font varier un compteur de 1 à \(n\) : \(i\leftarrow1\) avant la boucle, le test \(i\leq n\), et la progression \(i\leftarrow i+1\). Quand le nombre de tours est connu avant d’entrer dans la boucle, la boucle Pour réunit ces trois éléments dans son en-tête.

À Saint-Louis, Aïssatou rend les copies corrigées aux 30 étudiants d’un groupe en suivant la liste d’appel, du numéro 1 au numéro 30 : elle sait avant de commencer combien de copies elle rendra.

NoteBoucle Pour

Pour \(i\) de \(a\) à \(b\) Faire \(B\) FinPour exécute \(B\) une fois pour chaque valeur entière de \(i\) de \(a\) à \(b\), bornes incluses, dans l’ordre croissant. Avec pas \(p\), \(i\) avance de \(p\) et la boucle continue tant que \(i\leq b\) (tant que \(i\geq b\) si \(p<0\)). Elle équivaut à \[i\leftarrow a~;\ \textbf{TantQue}\ i\leq b\ \textbf{Faire}\ \big(B~;\ i\leftarrow i+1\big)\ \textbf{FinTantQue}\] et fait, pour un pas de 1, \(\max(0,\ b-a+1)\) tours.

Le « \(+1\) » du nombre de tours vient des bornes incluses : de 3 à 7, la boucle prend les valeurs 3, 4, 5, 6 et 7, soit \(7-3+1=5\) valeurs, et non \(7-3=4\). De 1 à 10, elle fait 10 tours ; de 1 à 0, aucun. Comme l’en-tête fait lui-même la progression, l’oubli de celle-ci, cause principale des boucles infinies, devient impossible.

AvertissementLe compteur d’un Pour

Le corps ne modifie pas le compteur ; la valeur du compteur après FinPour n’est pas définie et un algorithme ne doit pas s’en servir ; deux boucles Pour imbriquées ont deux compteurs différents. Dans les traces de ce document, le compteur disparaît du tableau après la fin de son Pour.

Exemple pas à pas : la factorielle

La factorielle \(n!=1\times2\times\dots\times n\) est un accumulateur multiplicatif, initialisé à 1. L’entrée est 4.

Lire n
f ← 1
Pour i de 1 à n Faire
  f ← f × i
FinPour
Écrire "factorielle :", f
Pas Ligne Instruction n f i Test Écrit
1 1 Lire n 4
2 2 f ← 1 4 1
3 3 Pour i de 1 à n Faire 4 1 1 vrai
4 4 f ← f × i 4 1 1
5 3 Pour i de 1 à n Faire 4 1 2 vrai
6 4 f ← f × i 4 2 2
7 3 Pour i de 1 à n Faire 4 2 3 vrai
8 4 f ← f × i 4 6 3
9 3 Pour i de 1 à n Faire 4 6 4 vrai
10 4 f ← f × i 4 24 4
11 3 Pour i de 1 à n Faire 4 24 5 faux
12 6 Écrire “factorielle :”, f 4 24 factorielle : 24

La ligne 3 apparaît à cinq pas : au pas 3, Pour donne à \(i\) sa première valeur, 1, et teste \(1\leq4\) ; aux pas 5, 7 et 9, il augmente \(i\) puis teste de nouveau ; au pas 11, \(i\) vaut 5, le test est faux et la boucle se termine. Quatre tours, cinq tests, comme pour TantQue. Le produit vaut successivement 1, 2, 6 et 24 ; l’algorithme écrit factorielle : 24. Le compteur n’apparaît plus au pas 12 : sa valeur après la boucle n’est pas définie.

La boucle Répéter … Jusqu’à

Pour lire une note valide, il faut d’abord la lire, puis décider s’il faut recommencer : la condition porte sur une valeur que seul le corps produit. Cheikh, qui prépare l’ataya pour ses amis à Tivaouane, goûte le thé, ajoute du sucre s’il le faut, goûte encore… jusqu’à ce qu’il soit à son goût : il goûte toujours au moins une fois.

NoteBoucle Répéter … Jusqu’à

Répéter \(B\) Jusqu’à \(C\) exécute \(B\), puis évalue \(C\) : si \(C\) est vraie, la boucle s’arrête ; sinon, \(B\) recommence. Le corps est exécuté au moins une fois, et \(C\) est une condition de sortie. La boucle équivaut à \(B\) suivi de TantQue NON \(C\) Faire \(B\) FinTantQue.

Les deux boucles à condition diffèrent sur deux points. TantQue teste avant le corps et peut faire zéro tour ; Répéter teste après et fait au moins un tour. TantQue écrit la condition pour continuer ; Jusqu’à écrit la condition pour sortir. Recopier l’une à la place de l’autre fait sortir la boucle exactement dans le cas où elle devait continuer.

Exemple pas à pas : la saisie contrôlée d’une note

L’algorithme lit une note jusqu’à ce qu’elle soit comprise entre 0 et 20, et signale chaque note invalide. Les entrées sont 25, \(-3\) et 14.

Répéter
  Lire note
  Si note < 0 OU note > 20 Alors
    Écrire "invalide :", note
  FinSi
Jusqu'à note ≥ 0 ET note ≤ 20
Écrire "note retenue :", note
Pas Ligne Instruction note Test Écrit
1 1 Répéter
2 2 Lire note 25
3 3 Si note < 0 OU note > 20 Alors 25 vrai
4 4 Écrire “invalide :”, note 25 invalide : 25
5 6 Jusqu'à note ≥ 0 ET note ≤ 20 25 faux
6 1 Répéter 25
7 2 Lire note \(-3\)
8 3 Si note < 0 OU note > 20 Alors \(-3\) vrai
9 4 Écrire “invalide :”, note \(-3\) invalide : -3
10 6 Jusqu'à note ≥ 0 ET note ≤ 20 \(-3\) faux
11 1 Répéter \(-3\)
12 2 Lire note 14
13 3 Si note < 0 OU note > 20 Alors 14 faux
14 6 Jusqu'à note ≥ 0 ET note ≤ 20 14 vrai
15 7 Écrire “note retenue :”, note 14 note retenue : 14

Chaque tour commence à la ligne 1 sans aucun test. Au premier tour, la note 25 rend vrai le test de la ligne 3 et la ligne 4 écrit invalide : 25 ; la condition de sortie de la ligne 6 est fausse et un deuxième tour commence. Le deuxième tour refuse \(-3\) de la même façon. Au troisième, 14 rend faux le test du Si et vraie la condition de sortie (pas 14) : la boucle s’arrête et la ligne 7 écrit note retenue : 14.

La variable note n’a pas de valeur avant le premier tour : avec TantQue, il faudrait la lire une première fois avant la boucle, puis une seconde fois dans le corps, et écrire deux fois la même instruction Lire. Répéter évite cette répétition, parce que la valeur testée est produite par le corps lui-même. C’est l’usage typique de cette boucle : la saisie contrôlée, le menu qui s’affiche au moins une fois, le jeu qui propose une nouvelle partie.

Le choix d’une boucle

Les trois boucles ont la même puissance : chacune peut s’écrire avec TantQue, comme le montrent les équivalences des définitions. Le choix porte donc sur la lisibilité, et il se fait par deux questions posées dans l’ordre.

NoteDeux questions pour choisir
  1. Le nombre de tours est-il connu avant d’entrer dans la boucle ? Si oui : Pour. C’est le cas de « pour chacun des \(n\) étudiants », de « pour chaque mois de l’année », de « pour \(i\) de 1 à \(n\) ».
  2. Sinon, faut-il exécuter le corps avant de pouvoir tester ? Si oui : Répéter ; si non : TantQue. La tontine, qui s’arrête quand le total atteint l’objectif, appelle TantQue : si l’objectif est nul, aucun versement n’est nécessaire. La saisie d’une note appelle Répéter : aucune note n’existe avant la première lecture.

Un nombre de tours « connu » signifie connu au moment où l’exécution arrive sur la boucle, pas à l’écriture de l’algorithme : dans la factorielle, \(n\) est lu au clavier, mais il est fixé avant la ligne 3, et la boucle Pour convient.

Les boucles qui ne s’arrêtent pas, ou mal

Une boucle peut ne jamais s’arrêter, ou s’arrêter un tour trop tôt, sans qu’aucun message d’erreur ne le signale : l’algorithme fait exactement ce qui est écrit. Seule une trace, faite sur une petite entrée dont on connaît le résultat, révèle ces erreurs. Un chauffeur de taxi qui attend, au rond-point de la place de l’Obélisque, la sortie numérotée 10 alors que les sorties portent les numéros 1, 3, 5, 7, 9, 11… fait le tour sans fin : la règle qu’il suit ne peut jamais lui dire de sortir.

La boucle infinie

NoteBoucle infinie

Une boucle infinie est une boucle dont le test ne devient jamais faux : soit aucune instruction du corps ne modifie la condition (progression oubliée), soit la progression passe à côté de la valeur d’arrêt.

Dans l’algorithme suivant, la progression \(i\leftarrow i+1\) a été oubliée.

i ← 1
TantQue i ≤ 3 Faire
  Écrire "tour", i
FinTantQue
Écrire "fin"
Pas Ligne Instruction i Test Écrit
1 1 i ← 1 1
2 2 TantQue i ≤ 3 Faire 1 vrai
3 3 Écrire “tour”, i 1 tour 1
4 2 TantQue i ≤ 3 Faire 1 vrai
5 3 Écrire “tour”, i 1 tour 1
6 2 TantQue i ≤ 3 Faire 1 vrai
7 3 Écrire “tour”, i 1 tour 1
8 2 TantQue i ≤ 3 Faire 1 vrai
9 3 Écrire “tour”, i 1 tour 1
… … … …

Le pas 9 a exactement le même état que le pas 3 : \(i\) vaut toujours 1 et le test reste vrai. L’algorithme écrit tour 1 sans fin, et la ligne 5 n’est jamais atteinte ; la trace est interrompue après neuf pas. Dès que deux tests successifs trouvent exactement le même état, la boucle est infinie : rien ne peut plus la faire évoluer.

Dans le second cas, la progression existe mais passe à côté de la valeur d’arrêt. L’algorithme suivant part de \(i=1\), avance de 2 et attend \(i=10\).

i ← 1
TantQue i ≠ 10 Faire
  i ← i + 2
FinTantQue
Pas Ligne Instruction i Test Écrit
1 1 i ← 1 1
2 2 TantQue i ≠ 10 Faire 1 vrai
3 3 i ← i + 2 3
4 2 TantQue i ≠ 10 Faire 3 vrai
5 3 i ← i + 2 5
6 2 TantQue i ≠ 10 Faire 5 vrai
7 3 i ← i + 2 7
8 2 TantQue i ≠ 10 Faire 7 vrai
9 3 i ← i + 2 9
10 2 TantQue i ≠ 10 Faire 9 vrai
11 3 i ← i + 2 11
12 2 TantQue i ≠ 10 Faire 11 vrai
13 3 i ← i + 2 13
14 2 TantQue i ≠ 10 Faire 13 vrai
15 3 i ← i + 2 15
… … … …

\(i\) prend les valeurs 1, 3, 5, 7, 9, 11, 13, 15…, toutes impaires : au pas 11, il passe de 9 à 11 sans jamais valoir 10, et le test \(i\neq10\) reste vrai à chaque passage. La trace ne présente que ses quinze premiers pas. Avec la condition \(i<10\), la boucle s’arrêterait au test qui trouve \(i=11\) : une condition d’arrêt écrite avec \(<\) ou \(\leq\) plutôt qu’avec \(\neq\) protège de ce cas.

L’erreur de décalage d’une unité

Une erreur de décalage d’une unité (off-by-one error) fait faire à la boucle un tour de trop ou de moins. Dans la somme de la section 3, la condition \(i\leq n\) a été remplacée par \(i<n\) ; l’entrée est encore 4.

Lire n
s ← 0
i ← 1
TantQue i < n Faire
  s ← s + i
  i ← i + 1
FinTantQue
Écrire "somme :", s
Pas Ligne Instruction n s i Test Écrit
1 1 Lire n 4
2 2 s ← 0 4 0
3 3 i ← 1 4 0 1
4 4 TantQue i < n Faire 4 0 1 vrai
5 5 s ← s + i 4 1 1
6 6 i ← i + 1 4 1 2
7 4 TantQue i < n Faire 4 1 2 vrai
8 5 s ← s + i 4 3 2
9 6 i ← i + 1 4 3 3
10 4 TantQue i < n Faire 4 3 3 vrai
11 5 s ← s + i 4 6 3
12 6 i ← i + 1 4 6 4
13 4 TantQue i < n Faire 4 6 4 faux
14 8 Écrire “somme :”, s 4 6 4 somme : 6

La trace est celle de la somme jusqu’au pas 12, puis le test du pas 13 trouve \(i=4\) et \(4<4\) faux : le tour \(i=n\) manque. L’algorithme écrit somme : 6, soit \(1+2+3\), au lieu de 10. Rien ne signale l’erreur ; seule la comparaison avec la trace de la somme, ou avec la valeur attendue \(n(n+1)/2=10\), la révèle. Vérifier une boucle sur ses deux bornes, la première et la dernière valeur du compteur, détecte ce décalage.

AvertissementUn réel comme compteur

En machine, les réels sont rangés en base 2 sur 64 bits : \(0{,}1\) n’a pas d’écriture binaire finie, et \(0{,}1\) ajouté dix fois à 0 donne \(0{,}9999999999999999\), et non 1. Une boucle qui attend \(x=1\) par la condition \(x\neq1\) ne s’arrête donc jamais. Un compteur de boucle doit être entier.

L’invariant de boucle

Une trace vérifie une boucle sur une entrée. Pour se convaincre qu’elle est correcte sur toutes les entrées, on énonce une propriété des variables vraie à chaque test de la condition : un invariant de boucle (Cormen et al., § 2.1).

NoteInvariant de boucle

Un invariant d’une boucle est une propriété des variables qui est vraie au premier test (initialisation), qui reste vraie d’un test au suivant quand un tour est exécuté (conservation), et qui, jointe à la condition devenue fausse, donne le résultat attendu (terminaison).

Pour la somme de la section 3.1, l’invariant est : « au test de la ligne 4, \(s=1+2+\dots+(i-1)\) ». La trace le confirme à chaque test : aux pas 4, 7, 10, 13 et 16, les couples \((i, s)\) valent \((1,0)\), \((2,1)\), \((3,3)\), \((4,6)\) et \((5,10)\), et l’on a bien \(0\), \(1\), \(1+2\), \(1+2+3\) et \(1+2+3+4\).

  • Initialisation. Au premier test, \(i=1\) et \(s=0\) : la somme \(1+\dots+(i-1)\) ne contient aucun terme et vaut 0.
  • Conservation. Un tour ajoute \(i\) à \(s\), puis augmente \(i\) de 1 : si \(s=1+\dots+(i-1)\) avant le tour, alors \(s=1+\dots+i\) après, ce qui s’écrit \(1+\dots+(i'-1)\) avec la nouvelle valeur \(i'=i+1\).
  • Terminaison. La boucle s’arrête au premier test où \(i\leq n\) est faux, c’est-à-dire \(i=n+1\), puisque \(i\) augmente de 1 à partir de 1 : l’invariant donne alors \(s=1+\dots+n\).

Le même raisonnement explique l’erreur de la section 6.2. Avec \(i<n\), l’invariant est inchangé, mais la boucle s’arrête à \(i=n\) : il donne \(s=1+\dots+(n-1)\), soit 6 pour \(n=4\), exactement la valeur observée. L’invariant désigne ainsi l’instruction fautive : la condition, et non le corps.

AstuceMéthode de vérification par trace
  1. Choisir une petite entrée dont le résultat est connu, et un cas limite (zéro tour, une seule valeur).
  2. Dérouler la boucle dans un tableau : une ligne par pas, une colonne par variable, le résultat de chaque test.
  3. Vérifier que la progression rapproche, à chaque tour, la condition de l’arrêt.
  4. Comparer la dernière ligne au résultat attendu ; la première ligne qui s’en écarte désigne l’instruction fautive.

Les boucles imbriquées

Le corps d’une boucle est un bloc quelconque ; il peut contenir lui-même une boucle. Pendant que la petite aiguille de l’horloge de la gare de Dakar passe d’une heure à la suivante, la grande fait un tour complet de 60 minutes, puis repart de zéro.

NoteBoucles imbriquées

Deux boucles sont imbriquées quand l’une, la boucle interne, est dans le corps de l’autre, la boucle externe. À chaque tour de la boucle externe, la boucle interne s’exécute en entier, depuis son initialisation.

Exemple pas à pas : l’ordre des tours

Pour i de 1 à 2 Faire
  Pour j de 1 à 3 Faire
    Écrire i, j
  FinPour
FinPour
Pas Ligne Instruction i j Test Écrit
1 1 Pour i de 1 à 2 Faire 1 vrai
2 2 Pour j de 1 à 3 Faire 1 1 vrai
3 3 Écrire i, j 1 1 1 1
4 2 Pour j de 1 à 3 Faire 1 2 vrai
5 3 Écrire i, j 1 2 1 2
6 2 Pour j de 1 à 3 Faire 1 3 vrai
7 3 Écrire i, j 1 3 1 3
8 2 Pour j de 1 à 3 Faire 1 4 faux
9 1 Pour i de 1 à 2 Faire 2 vrai
10 2 Pour j de 1 à 3 Faire 2 1 vrai
11 3 Écrire i, j 2 1 2 1
12 2 Pour j de 1 à 3 Faire 2 2 vrai
13 3 Écrire i, j 2 2 2 2
14 2 Pour j de 1 à 3 Faire 2 3 vrai
15 3 Écrire i, j 2 3 2 3
16 2 Pour j de 1 à 3 Faire 2 4 faux
17 1 Pour i de 1 à 2 Faire 3 faux

La ligne 1 donne \(i=1\). La boucle interne fait alors ses trois tours : aux pas 2, 4 et 6, \(j\) prend les valeurs 1, 2, 3, et la ligne 3 écrit 1 1, 1 2, 1 3. Au pas 8, \(j=4\) rend le test faux : la boucle interne se termine et l’exécution revient à l’en-tête de la ligne 1, qui porte \(i\) à 2 (pas 9). La boucle interne repart de \(j=1\) et refait ses trois tours. Au pas 17, \(i=3\) rend faux le test de la boucle externe et l’algorithme est terminé. Les six lignes écrites sont, dans l’ordre, 1 1, 1 2, 1 3, 2 1, 2 2, 2 3 : le compteur externe change le moins souvent.

Le nombre de tours

Quand les bornes de la boucle interne sont fixes, de 1 à \(m\), chacun des \(n\) tours externes déclenche \(m\) tours internes : le corps intérieur est exécuté \(n\times m\) fois. Quand la borne de la boucle interne dépend du compteur externe, comme dans Pour \(j\) de 1 à \(i\), le tour externe \(i\) déclenche \(i\) tours internes, et le total vaut \[1+2+\dots+n=\frac{n(n+1)}{2}.\] Cette somme se calcule en l’écrivant deux fois, à l’endroit puis à l’envers : chacune des \(n\) colonnes vaut \(n+1\), d’où \(2S=n(n+1)\). La figure montre les tours pour \(n=4\) : la ligne \(i\) compte \(i\) cases, et la ligne \(i=3\), encadrée, correspond à un tour externe pendant lequel la boucle interne fait trois tours.

Pour \(n=10\), le triangle compte 55 tours et le carré 100 ; pour \(n=1000\), \(500\,500\) et un million. Le nombre de tours d’une double boucle croît comme \(n^2\) : multiplier \(n\) par 10 multiplie ce nombre par environ 100. C’est un premier calcul de coût, que les séances sur la recherche, les tris et le coût des algorithmes reprendront.

Exercices corrigés

Les trois exercices suivants reprennent les trois gestes de la séance : dérouler une boucle dans un tableau de trace, compter ses tours et ses tests, raisonner sur les bornes d’une boucle, seule ou imbriquée. Chaque correction énonce la règle appliquée, donne la trace complète, conclut et signale l’erreur la plus répandue.

Exercice 1 : déroulement d’une boucle TantQue

Awa verse versement F chaque semaine dans une tontine, jusqu’à atteindre objectif F. Les entrées sont 7000 puis 30000.

Lire versement
Lire objectif
total ← 0
semaine ← 0
TantQue total < objectif Faire
  semaine ← semaine + 1
  total ← total + versement
FinTantQue
Écrire semaine, total
  1. Dresser la trace complète de l’algorithme, puis relever semaine, total et le résultat du test à chaque exécution de la ligne 5.
  2. Combien de tours la boucle fait-elle ? Qu’écrit la ligne 9 ?
  3. De combien le total dépasse-t-il l’objectif, et pourquoi ?
  4. Combien de fois la condition est-elle testée ?
AstuceCorrection

(a) Règle appliquée. Une trace exécute les lignes dans l’ordre où l’algorithme les atteint, une ligne de tableau par pas. Pour TantQue, trois règles fixent cet ordre : la condition est évaluée avant chaque tour ; si elle est vraie, les lignes du corps (6 et 7) sont exécutées, puis l’exécution revient à la ligne 5 ; si elle est fausse, l’exécution passe à la ligne qui suit FinTantQue, ici la ligne 9. La ligne 8 ne produit jamais de pas.

Déroulement. Les pas 1 et 2 lisent les entrées, les pas 3 et 4 initialisent l’accumulateur total et le compteur semaine. Au pas 5, \(0<30000\) est vrai : premier tour. Les pas 6 et 7 portent semaine à 1 et total à 7000, puis le pas 8 teste de nouveau la condition. Le même motif de trois pas (test, compteur, accumulateur) se répète jusqu’au pas 20, où total vaut 35000 et le test est faux.

Pas Ligne Instruction versement objectif total semaine Test Écrit
1 1 Lire versement 7000
2 2 Lire objectif 7000 30000
3 3 total ← 0 7000 30000 0
4 4 semaine ← 0 7000 30000 0 0
5 5 TantQue total < objectif Faire 7000 30000 0 0 vrai
6 6 semaine ← semaine + 1 7000 30000 0 1
7 7 total ← total + versement 7000 30000 7000 1
8 5 TantQue total < objectif Faire 7000 30000 7000 1 vrai
9 6 semaine ← semaine + 1 7000 30000 7000 2
10 7 total ← total + versement 7000 30000 14000 2
11 5 TantQue total < objectif Faire 7000 30000 14000 2 vrai
12 6 semaine ← semaine + 1 7000 30000 14000 3
13 7 total ← total + versement 7000 30000 21000 3
14 5 TantQue total < objectif Faire 7000 30000 21000 3 vrai
15 6 semaine ← semaine + 1 7000 30000 21000 4
16 7 total ← total + versement 7000 30000 28000 4
17 5 TantQue total < objectif Faire 7000 30000 28000 4 vrai
18 6 semaine ← semaine + 1 7000 30000 28000 5
19 7 total ← total + versement 7000 30000 35000 5
20 5 TantQue total < objectif Faire 7000 30000 35000 5 faux
21 9 Écrire semaine, total 7000 30000 35000 5 5 35000

La table demandée ne retient que les pas où la ligne 5 est exécutée (pas 5, 8, 11, 14, 17 et 20) :

Test semaine total total \(<\) 30000
1 0 0 vrai
2 1 7000 vrai
3 2 14000 vrai
4 3 21000 vrai
5 4 28000 vrai
6 5 35000 faux

À chaque test, total vaut \(7000\times\texttt{semaine}\) : cette relation, vraie dès le premier test, est un invariant de la boucle et permet de vérifier chaque ligne de la table.

(b) Un tour est compté à chaque test vrai : les tests 1 à 5 sont vrais, le sixième est faux. La boucle fait 5 tours, et la ligne 9 écrit 5 35000.

(c) Règle appliquée : l’arrêt n’a lieu qu’au test. Après la quatrième semaine, il manque \(30\,000-28\,000=2\,000\) F. Le cinquième tour s’exécute en entier et ajoute un versement complet de 7 000 F ; le test suivant constate le dépassement. Le total dépasse l’objectif de \(35\,000-30\,000=5\,000\) F. Il ne tombe exactement sur l’objectif que si l’objectif est un multiple du versement.

(d) La condition est testée 6 fois : 5 fois avec le résultat vrai, une dernière fois avec le résultat faux qui arrête la boucle.

Conclusion. Une boucle TantQue de \(k\) tours fait \(k+1\) tests, et la variable de la condition vaut, à la sortie, la première valeur qui rend le test faux (ici 35000), pas la valeur visée (30000).

AvertissementErreur fréquente

Arrêter la trace dès que le total « atteint » l’objectif, en écrivant 4 30000 ou 4 28000 : le corps n’est jamais interrompu, et seule la valeur trouvée au test décide. Autre erreur répandue : compter 5 tests, en oubliant le dernier, celui qui échoue.

Exercice 2 : une boucle Pour et un Si

s ← 0
Pour i de 1 à 6 Faire
  Si i mod 2 = 0 Alors
    s ← s + i
  FinSi
FinPour
Écrire s
  1. Dresser la trace complète, puis donner pour chaque tour la valeur de \(i\), le résultat du test \(i\) mod \(2=0\) et la valeur de \(s\) après le tour.
  2. Qu’écrit la ligne 7 ?
  3. Combien de fois le test du Si est-il évalué ? Combien de fois l’en-tête Pour est-il testé ?
  4. Écrire un algorithme qui lit un entier \(n\) et écrit la somme des entiers pairs de 2 à \(n\), avec une boucle Pour sans Si. Le tracer pour \(n=6\), puis pour le cas limite \(n=1\).
AstuceCorrection

(a) Règle appliquée. L’en-tête Pour \(i\) de 1 à 6 regroupe trois actions : au premier passage, il donne à \(i\) la valeur 1 ; aux passages suivants, il augmente \(i\) de 1 ; à chaque passage, il teste \(i\leq6\). Dans la trace, chaque exécution de la ligne 2 est donc un pas qui modifie \(i\) et donne un résultat de test. Dans le corps, le Si est évalué à chaque tour ; la ligne 4 n’est exécutée que s’il est vrai, c’est-à-dire quand le reste de la division de \(i\) par 2 est nul, donc quand \(i\) est pair.

Pas Ligne Instruction s i Test Écrit
1 1 s ← 0 0
2 2 Pour i de 1 à 6 Faire 0 1 vrai
3 3 Si i mod 2 = 0 Alors 0 1 faux
4 2 Pour i de 1 à 6 Faire 0 2 vrai
5 3 Si i mod 2 = 0 Alors 0 2 vrai
6 4 s ← s + i 2 2
7 2 Pour i de 1 à 6 Faire 2 3 vrai
8 3 Si i mod 2 = 0 Alors 2 3 faux
9 2 Pour i de 1 à 6 Faire 2 4 vrai
10 3 Si i mod 2 = 0 Alors 2 4 vrai
11 4 s ← s + i 6 4
12 2 Pour i de 1 à 6 Faire 6 5 vrai
13 3 Si i mod 2 = 0 Alors 6 5 faux
14 2 Pour i de 1 à 6 Faire 6 6 vrai
15 3 Si i mod 2 = 0 Alors 6 6 vrai
16 4 s ← s + i 12 6
17 2 Pour i de 1 à 6 Faire 12 7 faux
18 7 Écrire s 12 12

Elle se résume, tour par tour, dans la table suivante :

\(i\) \(i\) mod \(2=0\) \(s\) après le tour
1 faux 0
2 vrai 2
3 faux 2
4 vrai 6
5 faux 6
6 vrai 12

(b) La ligne 7 écrit 12, soit \(2+4+6\), la somme des entiers pairs de 1 à 6.

(c) Le test du Si est évalué une fois par tour, donc 6 fois, dont 3 avec le résultat vrai. L’en-tête est testé \(6+1=7\) fois (pas 2, 4, 7, 9, 12, 14 et 17) : la règle « \(k\) tours, \(k+1\) tests » vaut aussi pour Pour. Le dernier test trouve \(i=7\) ; après FinPour, la valeur de \(i\) n’est pas définie, et \(i\) disparaît de la trace au pas 18.

(d) Règle appliquée : choisir les bornes et le pas. Les seuls entiers utiles sont les pairs ; la boucle part donc de 2 et avance de 2. La borne \(n\) est incluse : si \(n\) est pair, le dernier tour se fait avec \(i=n\). L’algorithme attendu est :

Lire n
s ← 0
Pour i de 2 à n pas 2 Faire
  s ← s + i
FinPour
Écrire s

Pour \(n=6\), la trace est la suivante :

Pas Ligne Instruction n s i Test Écrit
1 1 Lire n 6
2 2 s ← 0 6 0
3 3 Pour i de 2 à n pas 2 Faire 6 0 2 vrai
4 4 s ← s + i 6 2 2
5 3 Pour i de 2 à n pas 2 Faire 6 2 4 vrai
6 4 s ← s + i 6 6 4
7 3 Pour i de 2 à n pas 2 Faire 6 6 6 vrai
8 4 s ← s + i 6 12 6
9 3 Pour i de 2 à n pas 2 Faire 6 12 8 faux
10 6 Écrire s 6 12 12

La boucle fait 3 tours (\(i=2\), 4, 6) au lieu de 6 et écrit 12 : le test du pas 9 trouve \(i=8>6\) et termine la boucle. Pour le cas limite \(n=1\) :

Pas Ligne Instruction n s i Test Écrit
1 1 Lire n 1
2 2 s ← 0 1 0
3 3 Pour i de 2 à n pas 2 Faire 1 0 2 faux
4 6 Écrire s 1 0 0

Le premier test trouve \(2>1\) : la boucle ne fait aucun tour et l’algorithme écrit 0, la somme d’aucun entier, grâce à l’initialisation \(s\leftarrow0\).

Conclusion. Un Si dans une boucle fait varier ce qui est exécuté à chaque tour, pas le nombre de tours ; ce nombre ne dépend que de l’en-tête. Un pas bien choisi supprime le test et divise ici le nombre de tours par deux.

AvertissementErreur fréquente

Ne pas compter les tours où le Si est faux : ce sont bien des tours, avec un test évalué, même si \(s\) ne change pas. Autre erreur répandue : vérifier l’algorithme sur la seule entrée de l’énoncé. Le cas limite \(n=1\), où la boucle ne fait aucun tour, valide l’initialisation de l’accumulateur.

Exercice 3 : une double boucle triangulaire

Pour i de 1 à 3 Faire
  Pour j de 1 à i Faire
    Écrire i, j
  FinPour
FinPour
  1. Dresser la trace complète et donner les lignes écrites, dans l’ordre.
  2. Combien de fois la ligne 3 est-elle exécutée ? Vérifier avec \(n(n+1)/2\), avec \(n=3\).
  3. Même question si la ligne 2 devient Pour \(j\) de 1 à \(i-1\).
  4. Pour \(i\) de 1 à \(n\), combien de tours dans chaque cas ?
AstuceCorrection

(a) Règle appliquée. À chaque tour de la boucle externe, la boucle interne s’exécute en entier, depuis son initialisation : son en-tête redonne à \(j\) la valeur 1, et la borne \(i\) est lue avec la valeur courante de \(i\). Quand le test de la ligne 2 échoue, l’exécution revient à l’en-tête de la ligne 1, qui augmente \(i\).

Pas Ligne Instruction i j Test Écrit
1 1 Pour i de 1 à 3 Faire 1 vrai
2 2 Pour j de 1 à i Faire 1 1 vrai
3 3 Écrire i, j 1 1 1 1
4 2 Pour j de 1 à i Faire 1 2 faux
5 1 Pour i de 1 à 3 Faire 2 vrai
6 2 Pour j de 1 à i Faire 2 1 vrai
7 3 Écrire i, j 2 1 2 1
8 2 Pour j de 1 à i Faire 2 2 vrai
9 3 Écrire i, j 2 2 2 2
10 2 Pour j de 1 à i Faire 2 3 faux
11 1 Pour i de 1 à 3 Faire 3 vrai
12 2 Pour j de 1 à i Faire 3 1 vrai
13 3 Écrire i, j 3 1 3 1
14 2 Pour j de 1 à i Faire 3 2 vrai
15 3 Écrire i, j 3 2 3 2
16 2 Pour j de 1 à i Faire 3 3 vrai
17 3 Écrire i, j 3 3 3 3
18 2 Pour j de 1 à i Faire 3 4 faux
19 1 Pour i de 1 à 3 Faire 4 faux

Les pas 2, 6 et 12 sont les premiers passages de la boucle interne pour \(i=1\), 2 et 3 : \(j\) y repart de 1. Les pas 4, 10 et 18 sont les tests qui échouent (\(j=2\), 3 et 4) et renvoient à la ligne 1. La trace se résume ainsi :

\(i\) valeurs de \(j\) lignes écrites
1 1 1 1
2 1, 2 2 1, 2 2
3 1, 2, 3 3 1, 3 2, 3 3

L’algorithme écrit donc six lignes : 1 1, 2 1, 2 2, 3 1, 3 2, 3 3.

(b) Règle appliquée : le tour externe \(i\) déclenche autant de tours internes que la boucle interne a de valeurs. De 1 à \(i\), il y en a \(i-1+1=i\). La ligne 3 est exécutée \(1+2+3=6\) fois, ce que donne bien \(n(n+1)/2=3\times4/2=6\) pour \(n=3\).

(c) Avec la borne \(i-1\), le tour \(i=1\) donne la boucle Pour \(j\) de 1 à 0, qui a \(\max(0,\,0-1+1)=0\) tour ; le tour \(i=2\) en fait un, le tour \(i=3\) deux. La ligne 3 est exécutée \(0+1+2=3\) fois et écrit 2 1, 3 1, 3 2 :

Pas Ligne Instruction i j Test Écrit
1 1 Pour i de 1 à 3 Faire 1 vrai
2 2 Pour j de 1 à i - 1 Faire 1 1 faux
3 1 Pour i de 1 à 3 Faire 2 vrai
4 2 Pour j de 1 à i - 1 Faire 2 1 vrai
5 3 Écrire i, j 2 1 2 1
6 2 Pour j de 1 à i - 1 Faire 2 2 faux
7 1 Pour i de 1 à 3 Faire 3 vrai
8 2 Pour j de 1 à i - 1 Faire 3 1 vrai
9 3 Écrire i, j 3 1 3 1
10 2 Pour j de 1 à i - 1 Faire 3 2 vrai
11 3 Écrire i, j 3 2 3 2
12 2 Pour j de 1 à i - 1 Faire 3 3 faux
13 1 Pour i de 1 à 3 Faire 4 faux

Au pas 2, le premier test de la boucle interne trouve \(j=1>0\) : la boucle interne ne fait aucun tour, et l’exécution revient aussitôt à l’en-tête de la ligne 1.

(d) Avec la borne \(i\), le corps intérieur est exécuté \(1+2+\dots+n=n(n+1)/2\) fois ; avec la borne \(i-1\), \(0+1+\dots+(n-1)=n(n-1)/2\) fois. La différence vaut \(n\) : une borne décalée d’une unité retire un tour à chacun des \(n\) tours externes.

Conclusion. Le nombre de tours d’une double boucle se calcule tour externe par tour externe, puis se somme ; quand la borne interne dépend du compteur externe, la somme est triangulaire.

AvertissementErreur fréquente

Faire continuer \(j\) d’un tour externe au suivant (2, 3, 4…) au lieu de le faire repartir de 1 ; ou compter un tour pour Pour \(j\) de 1 à 0, alors que son premier test est faux. Les deux erreurs se détectent en relevant, dans la trace, la valeur de \(j\) au premier passage de chaque boucle interne.

À retenir

Boucle Test Tours au moins Usage
TantQue \(C\) Faire … FinTantQue avant le corps 0 nombre de tours inconnu à l’entrée
Pour \(i\) de \(a\) à \(b\) Faire … FinPour avant le corps 0 nombre de tours connu : \(\max(0,b-a+1)\) (pas de 1)
Répéter … Jusqu’à \(C\) après le corps 1 condition portant sur ce que produit le corps
  • Une boucle a quatre éléments : initialisation, condition, corps, progression ; elle ne s’arrête qu’à un test faux.
  • Un compteur et un accumulateur s’initialisent avant la boucle : 0 pour une somme, 1 pour un produit, la première donnée pour un maximum.
  • Une boucle TantQue de \(k\) tours fait \(k+1\) tests.
  • Une trace à la main, sur une petite entrée et sur un cas limite, révèle la boucle infinie et le décalage d’une unité.
  • Deux boucles imbriquées font \(n\times m\) tours, ou \(n(n+1)/2\) quand la borne interne est le compteur externe.

Prochaine séance

La Séance 4 range plusieurs valeurs de même type dans un tableau et les parcourt par une boucle Pour sur leurs indices, avec les compteurs et les accumulateurs de cette séance.

Références

  • Cormen — Algorithms Unlocked, MIT Press, 2013 (ch. 2, « How to Describe and Evaluate Computer Algorithms »).
  • Bhargava — Grokking Algorithms, 2e éd., Manning, 2024.
  • Cormen, Leiserson, Rivest, Stein — Introduction to Algorithms, 4e éd., MIT Press, 2022 (ch. 2, « Getting Started », § 2.1 : invariant de boucle).
  • Notes de cours en ligne : CS50 (Harvard), 6.100A (MIT), CS106A (Stanford), séances sur les boucles.

Pour cette séance

Les slides

À lire en ligne

Retour au sommet