Cours 3: les structures itératives :
Par Ahmed Fessi

1. Introduction.
L'intérêt d'utiliser un ordinateur n'apparaît clairement que lors de la manipulation de données nombreuses ou traitées de manière répétitive.
Exemple 1: Chercher dans une liste de noms et d'adresses, l'adresse d'une personne à partir de son nom. Le nombre de fois qu'il faudra comparer le nom donné aux noms de la liste est dans ce cas inconnu.
Exemple 2 : Calculer la Nème puissance entière d'un nombre x par multiplications successives du nombre par lui-même. Ici, le nombre de répétition (N) de l'instruction de multiplication est connu.
S'il est théoriquement possible de se contenter d'une seule structure de répétition, bien choisie, pour exprimer tous les algorithmes, l'expérience a montré l'utilité d'en définir plusieurs, chacune bien adaptée à des circonstances particulières. Ce sont les boucles tant que, répéter ... jusqu'à et pour.

2. La boucle " tant que ".
Résolvons l'exemple 1:
lire nom_donné
lire nom1
si nom1 = nom_donné alors écrire adresse1
sinon lire nom2
si nom2 = nom_donné alors écrire adresse2
sinon lire nom3
si nom3 = nom_donné alors ...

L'inconvénient de cet algorithme (en dehors de l'empiètement inévitable sur la marge de droite) tient au fait que l'auteur ne sait pas quand il doit s'arrêter d'écrire. Plus précisément, il lui est impossible de savoir combien de fois il doit écrire l'instruction de comparaison au nom_donné.
Un problème identique surgit dans l'écriture d'un algorithme qui décrit comment calculer le premier nombre premier qui soit plus grand qu'un nombre entier positif donné N.

lire (N)
i <-- N+1
si i est premier alors écrire i
sinon i <-- i+1
si i est premier alors écrire i
sinon i <-- i+1
si i est premier alors écrire i
sinon i <-- i+1
si ...

Le test "si i est premier alors" ne sera exécuté qu'une fois si N=4, il le sera quatre fois si N=13, mais combien de fois faudra-t-il réécrire le test si N=7394485?
Ces exemples montrent que la séquence et l'alternative ne sont pas en elles-mêmes suffisantes pour exprimer des algorithmes dont la longueur peut varier selon les circonstances. Il est donc nécessaire d'introduire le moyen de répéter certaines instructions d'un algorithme un nombre quelconque de fois. La structure qui permet cela est appelée structure répétitive.
L'exemple avec le nombre premier s'écrira avec la boucle tant que :
lire (N)
i <-- N+1
Tant que NON (i est premier) Répéter
i <-- i+1
FinTantQue
écrire (i)

Notons qu'il faudra exprimer autrement les conditions " (i est premier) ", ces formes n'étant pas compréhensibles par l’ordinateur.
Considérons aussi l'exemple suivant: étant donnés deux nombres entiers m et n positifs ou nuls, on demande d'en calculer le PGCD. L'algorithme d'Euclide permet de résoudre ce problème en prenant d'abord le reste de la division de m par n, puis le reste de la division de n par ce premier reste, etc jusqu'à ce qu'on trouve un reste nul. Le dernier diviseur utilisé est le PGCD de m et n. Pour m=1386 et n=140, on a successivement:
1386 modulo 140 = 126 140 modulo 126 = 14 126 modulo 14 = 0
et le PGCD de 1386 et 126 est bien 14.
Remarquons que par définition, si un des nombres est nul, l'autre nombre est le PGCD.
Si nous avions pris m=140 et n=1386, nous aurions obtenu la suite de calculs suivants:
140 modulo 1386 = 140 1386 modulo 140 = 126 ...

et le PGCD est le même. L'ordre de m et n n'a donc pas d'importance.
Dans cet exemple, nous devons répéter le calcul du reste de la division d'un nombre par un autre. Pour fixer les idées, appelons a le dividende, b le diviseur et r le reste. Le calcul du reste de la division de a par b se fait simplement au moyen de l'instruction :
r <-- a mod b
L'algorithme s'écrit donc:
entier m,n,a,b,r,PGCD
lire (m, n)
a <-- m
b <-- n
tant que NON(b = 0) Répéter
r <-- a mod b
a <-- b
b <-- r
FinTantQue
PGCD <-- a
écrire ("Le PGCD de",m,"et",n,"est",PGCD)

Commentaires
1) Les mots Répéter et FinTantQue encadrent les instructions qui doivent être exécutées plusieurs fois. On indique entre Tant que et Répeter les conditions dans lesquelles on doit exécuter le corps de la boucle.
2) Une boucle "Tant que" se présente donc comme suit:
tant que expression logique Répéter
séquence d'instructions
FinTantQue
En premier lieu, l'expression logique est évaluée (il faut donc veiller à sa valeur lors de l'entrée dans la boucle): si sa valeur est vrai, le corps de la boucle est exécuté puis l'expression logique est réévaluée (il faut donc qu'elle puisse changer de valeur pour sortir de la boucle) et si elle a la valeur faux, on exécute l'instruction qui suit FinTantQue
3) Il est à noter qu'il est préférable d'exprimer l'expression logique sous la forme NOT (condition(s) d'arrêt). Il est en effet plus simple de déterminer les raisons d'arrêter le processus répétitif que celles de continuer.
La forme de ce type de boucle devient donc:
tant que NON condition(s) d'arrêt Répéter
séquence d'instructions
FinTantQue

3. La boucle " pour".
Reprenons l'exemple 2 de l'introduction. Une boucle "tant que" permet de le résoudre:
entier N, i, x, puiss
lire (N, x)
puiss <-- 1
i <-- 1
tant que NOT(i > N) Répéter
puiss <-- puiss * x
i <-- i + 1
FinTantQue
écrire ("La puissance",N,"ème de",x,"est",puiss)
Cependant, le nombre d'exécutions du corps de la boucle étant connu à l'avance, une boucle "pour" est d'un emploi plus simple:
entier N, i, x, puiss
lire (N, x)
puiss <-- 1
pour i de 1 à N Répéter
puiss <-- puiss * x
FinPour
écrire ("La puissance",N,"ème de",x,"est",puiss)

Commentaires
1° Les mots faire et finpour encadrent les instructions qui doivent être exécutées plusieurs fois. On précise entre pour et Répéter comment seront contrôlées les répétitions. On y définit une variable appelée variable de contrôle (dite aussi compteur) (i dans l'exemple) et les valeurs que prendra cette variable: une première valeur ou valeur initiale indiquée après le mot de, une dernière valeur ou valeur finale indiquée après le mot à. La variable de contrôle est initialisée à la première valeur. Avant chaque exécution du corps de la boucle, la valeur de la variable de contrôle est comparée à la valeur finale. Si la variable de contrôle ne dépasse pas cette valeur, on exécute le corps de la boucle, sinon on passe à l'instruction qui suit le mot finpour. Après chaque exécution du corps de la boucle, la variable de contrôle est augmentée d'une unité.
2° Dans l'exemple ci-dessus, la variable de contrôle sert uniquement de compteur du nombre d'exécutions du corps de la boucle. Si on le souhaite, on peut utiliser cette valeur dans le corps de la boucle, entre autres pour faire un calcul fondé sur cette valeur. Dans tous les cas, il faut éviter de modifier la valeur de cette variable.
3° La première valeur, la dernière valeur et l'incrément peuvent être des expressions numériques. Les instructions du corps de la boucle ne peuvent en aucun cas modifier ces valeurs.
4° Il est théoriquement possible de modifier la valeur de la variable de contrôle à l'intérieur de la boucle mais cette technique est dangereuse et à ne pas utiliser.

4. La boucle " répéter ... jusqu'à ".
Comme la boucle "tant que", ce type de répétitive est utilisé lorsque le nombre de fois que la séquence d'instructions à répéter est inconnu au moment où cette séquence est abordée pour la première fois mais le corps de la boucle est toujours exécuté au moins une fois.
Sa formulation générale est:
répéter
séquence d'instructions
jusqu'à (expression logique)

L'expression logique est évaluée après l'exécution du corps de la boucle: si sa valeur est faux, le corps de la boucle est exécuté à nouveau puis l'expression logique est réévaluée (il faut donc qu'elle puisse changer de valeur pour sortir de la boucle) et si elle a la valeur vrai, on exécute l'instruction qui suit jusqu'à.
Il faut remarquer que dans
tant que expression logique faire
séquence d'instructions
fintantque

expression logique exprime les raisons de continuer et dans
répéter
séquence d'instructions
jusqu'à (expression logique)
expression logique exprime les raisons d'arrêter.

5. La répétitive en Pascal.
a) Forme Générale de la boucle Tant Que … Répéter en Pascal :
While (Condition) do
Begin
Instrunction(s) ;
End ;

b) Forme Générale de la boucle Pour en Pascal

For compteur :=Valeur_Initiale to Valeur_Finale do
Begin
Instruction(s) ;
End ;

c) Forme générale de la boucle Répéter … Jusqu’à en Pascal :

Repeat
Instruction(s) ;
Until (Condition)

6 . Résumé
Le problème principal est de bien choisir le type de boucle à utiliser.
Voilà les questions à se poser pour faire le bon choix:
Le nombre de répétitions est-il connu au moment du premier passage dans la boucle?
Oui et bien alors, il ne faut pas hésiter. Il faut utiliser une boucle pour...finpour
Non. Alors il faut se demander si on est sûr que le corps de la boucle sera effectué au moins une fois.
Oui et bien alors, il semble raisonnable d'utiliser la boucle répéter...jusqu'à.
Non. Alors pas d'hésitation, c'est la boucle tant que...fintantque qu'il faut utiliser.
Dernier conseil:
sachant que les conditions d'arrêt d'une boucle sont en général plus simples à trouver que les raisons de continuer, surtout parce qu'elles s'expriment souvent sous forme condition1 ou condition2 ou ..., il est préférable d'utiliser la boucle tant que sous la forme
tant que NON (condition1 ou condition2 ou ...)
....
fintantque.