CHAPITRE 6 : CHOISIR SA BOUCLE : COMPARAISON ET INVARIANTS

Les trois structures repetitives ont le meme objectif, mais ne s'emploient pas dans les memes situations. Ce chapitre vous donne une methode pour choisir sans hesiter.

1. Comparaison complete

Critere	POUR	TANTQUE	REPETER
Nombre d'iterations connu	Oui	Non	Non
Test de la condition	Automatique	Avant	Apres
Execution minimale	Depend des bornes	0 fois possible	1 fois obligatoire
Variable de controle	Automatique	Manuelle	Manuelle
Usage principal	Comptage, parcours	Attente d'une condition	Condition d'arret

2. L'arbre de decision

Le nombre de repetitions est-il connu ?

            Oui  ──────────────▶  POUR

            Non
             │
             ▼
La premiere execution est-elle obligatoire ?

        Oui  ─────▶  REPETER

        Non  ─────▶  TANTQUE

Cet arbre suffit, dans la grande majorite des cas, a choisir des la lecture de l'enonce.

3. Trois situations typiques

Nombre d'iterations connu

Pour i de 1 a 100 Faire
    Lire(T[i]);
FinPour

Nombre d'iterations inconnu

Lire(x);

TantQue(x <> 0) Faire
    ...
    Lire(x);
FinTantQue

Premiere execution obligatoire

Repeter
    Lire(note);
Jusqu'a(note >= 0 ET note <= 20)

4. L'invariant de boucle

Un invariant est une propriete qui reste vraie :

avant la premiere iteration ;
apres chaque iteration ;
lorsque la boucle se termine.

Il permet de demontrer qu'un algorithme est correct.

Les trois proprietes

Propriete	Signification
Initialisation	L'invariant est vrai avant le premier passage
Maintenance	S'il est vrai avant une iteration, il le reste apres
Terminaison	A l'arret, il permet de conclure que le resultat est correct

Un exemple

s <- 0;

Pour i de 1 a n Faire
    s <- s + i;
FinPour

Invariant : avant chaque iteration, s contient deja la somme 1 + 2 + … + (i-1).

Verifions : avant l'iteration ou i = 4, on a s = 6, et en effet 1 + 2 + 3 = 6. Apres cette iteration, s = 10 : l'invariant reste vrai. Quand la boucle s'arrete, i = n+1 et s contient 1 + 2 + … + n. La demonstration est faite.

5. Les tableaux de trace

Un tableau de trace suit l'evolution des variables. C'est l'outil a degainer des qu'un algorithme resiste.

s <- 0;

Pour i de 1 a 4 Faire
    s <- s + i;
FinPour

i	s avant	s apres
1	0	1
2	1	3
3	3	6
4	6	10

6. Les boucles imbriquees

Pour i de 1 a 3 Faire
    Pour j de 1 a 2 Faire
        Ecrire(i, j);
    FinPour
FinPour

(1,1) (1,2) (2,1) (2,2) (3,1) (3,2)

Elles servent aux matrices, aux tableaux a deux dimensions, a certains tris et a certaines recherches. Le tri a bulles, que nous verrons plus loin, utilise une boucle TANTQUE contenant une boucle POUR.

7. Les pieges a connaitre

Confondre = et <- : Si(x = 5) pour tester, x <- 5; pour affecter
Oublier d'initialiser la variable
Ne jamais modifier la variable de controle → boucle infinie
Choisir la mauvaise boucle : pour lire un tableau de taille connue, c'est POUR
Confondre condition d'entree et condition de sortie

8. Les questions classiques

Question	Reponse attendue
Difference entre TANTQUE et REPETER ?	TANTQUE a une condition d'entree, REPETER une condition de sortie
Une boucle TANTQUE peut-elle ne jamais s'executer ?	Oui, si la condition est fausse au depart
Une boucle REPETER peut-elle ne jamais s'executer ?	Non, elle s'execute au moins une fois
Qu'est-ce qu'une boucle infinie ?	Une boucle dont la condition d'arret n'est jamais satisfaite
A quoi sert un invariant ?	A demontrer que la boucle est correcte

A retenir

POUR → nombre d'iterations connu
TANTQUE → condition d'entree
REPETER…JUSQU'A → condition de sortie
L'invariant demontre la correction d'un algorithme
Le tableau de trace suit l'evolution des variables

Exercices d'application

Exercice 1. Choisir la bonne bouclePour chacun de ces cas, indiquez la boucle adaptee et justifiez : lire 50 notes ; lire jusqu'a la valeur 0 ; demander un mot de passe jusqu'a ce qu'il soit correct ; afficher une table de multiplication.

Exercice 2. Tableau de traceDressez le tableau de trace de : s <- 1; Pour i de 1 a 5 Faire s <- s * i; FinPour. Que calcule cet algorithme ?

Exercice 3. InvariantPour l'algorithme qui cherche le maximum d'un tableau, enoncez l'invariant de boucle et verifiez les trois proprietes.

Cherchez avant de regarder la solution : c'est en butant sur les difficultes que l'on progresse.