Cours d'algorithmique - Instructions itératives: les boucles

Instructions itératives: les boucles

Les boucles servent à répéter l'exécution d'un groupe d'instructions  un certain nombre de fois
On distingue trois sortes de boucles en langages de programmation :

Les boucles tant que : on y répète des instructions tant qu'une certaine condition est réalisée
Les boucles jusqu'à : on y répète des instructions jusqu'à ce qu'une certaine condition soit réalisée
Les boucles pour ou avec compteur : on y répète des instructions en faisant évoluer un compteur (variable particulière) entre une valeur initiale et une valeur finale 

Les boucles Tant que

Syntaxe Générale

            TantQue     (condition)
                      instructions
            FinTantQue

la condition (dite condition de contrôle de la boucle) est évaluée avant chaque itération
si la condition est vraie, on exécute instructions (corps de la boucle), puis, on retourne tester la condition.
Si elle est encore vraie, on répète l'exécution, …
si la condition est fausse, on sort de la boucle et on exécute l'instruction  qui est après FinTantQue

Les boucles Tant que : remarques

Le nombre d'itérations dans une boucle TantQue n'est pas connu au moment d'entrée dans la boucle. Il dépend de l'évolution de la valeur de condition
Une des instructions du corps de la boucle doit absolument changer la valeur de condition de vrai à faux (après un certain nombre d'itérations), sinon le programme tourne indéfiniment

Attention aux boucles infinies

Exemple de boucle infinie : 

i ← 2
TantQue   (i > 0)
i ←  i+1        (attention aux erreurs de frappe : + au lieu de -)
FinTantQue

Boucle Tant que : Exemple1

Contrôle de saisie d'une lettre majuscule jusqu’à ce que le caractère entré soit valable

Variable C : caractère
Debut
            Ecrire (" Entrez une lettre majuscule ")
Lire (C)
TantQue (C < 'A' ou C > 'Z')
                           Ecrire ("Saisie erronée. Recommencez")
                           Lire (C)
           FinTantQue
          Ecrire ("Saisie valable")
Fin

Boucle Tant que : Exemple2 (version 1)

Un algorithme qui détermine le premier nombre entier N tel que la somme de 1 à N dépasse strictement 100

Variables som, i : entier
 Debut
i ← 0
som← 0
TantQue (som <=100)
    i ←  i+1
som ←  som+i
FinTantQue
         Ecrire (" La valeur cherchée est N=  ", i)
Fin

Boucle Tant que : exemple2  (version2)

Un algorithme qui détermine le premier nombre entier N tel que la somme de 1 à N dépasse strictement 100
version 2: attention à l'ordre des instructions et aux valeurs initiales

Variables som, i : entier
 Debut
            som ← 0
          i ← 1
           TantQue (som <=100)
                    som ← som + i
                    i ←  i+1
FinTantQue
Ecrire (" La valeur cherchée est N=  ", i-1)
Fin

Les boucles Pour

Syntaxe Générale

Pour compteur allant de  valeur initiale à finale par pas valeur du pas
           instructions
FinPour

Remarque : le nombre d'itérations dans une boucle Pour est connu avant le début de la boucle

Compteur est une variable de type entier (ou caractère). Elle doit être déclarée
Pas est un entier qui peut être positif ou négatif. Pas peut ne pas être mentionné, car par défaut sa valeur est égal à 1. Dans ce cas, le nombre d'itérations est égal à finale - initiale+ 1
valeur initiale et finale peuvent être des valeurs, des variables définies avant le début de la boucle ou des expressions de même type que compteur 

Déroulement des boucles Pour

La valeur initiale est affectée à la variable compteur
On compare la valeur du compteur et la valeur de finale :

• Si la valeur du compteur est > à la valeur finale dans le cas d'un pas positif (ou si compteur est <  à finale pour un pas négatif), on sort de la boucle et on continue avec l'instruction qui suit FinPour
• Si compteur est <= à finale dans le cas d'un pas positif (ou si compteur est >=  à finale pour un pas négatif), instructions seront exécutées

Ensuite, la valeur de compteur est incrémentée de la valeur du pas  si pas est positif (ou décrémenté si pas est négatif)
On recommence l'étape 2 : La comparaison entre compteur et finale est de nouveau effectuée, et ainsi de suite  …

Boucle Pour : exemple1

Calcul de x à la puissance n où x est un réel non nul et n un entier positif ou nul

Variables x, puiss : réel
                        n, i : entier
Debut
                Ecrire (" Entrez la valeur de x ")
Lire (x)
Ecrire (" Entrez la valeur de n ")
Lire (n)
puiss ← 1 Pour i allant de 1 à n
    puiss← puiss*x
                FinPour
Ecrire (x, " à la puissance  ", n, "  est égal à  ", puiss)
Fin

Boucle Pour : exemple1 (version 2)

Calcul de x à la puissance n où x est un réel non nul et n un entier positif ou nul (version 2 avec un pas négatif)

Variables x, puiss : réel
                       n, i : entier
Debut
                Ecrire (" Entrez respectivement les valeurs de x et n ")
Lire (x, n)
puiss ← 1 Pour i allant de n à 1 par pas -1
    puiss← puiss*x
                FinPour
                Ecrire (x, " à la puissance  ", n, "  est égal à  ", puiss)
Fin

Boucle Pour : remarque

Il faut éviter de modifier la valeur du compteur (et de finale) à l'intérieur de la boucle. En effet, une telle action :

• perturbe le nombre d'itérations prévu par la boucle Pour
• rend difficile la lecture de l'algorithme
• présente le risque d'aboutir à une boucle infinie

Exemple : 

   Pour i allant de 1 à 5
      i ← i -1
           écrire(" i =  ", i)
Finpour

Lien entre Pour et TantQue

La boucle Pour est un cas particulier de Tant Que (cas où le nombre d'itérations est connu et fixé) . Tout ce qu'on peut écrire avec Pour peut être remplacé avec TantQue (la réciproque est fausse)

  Pour compteur allant de initiale à finale par pas valeur du pas
                          instructions          
   FinPour

peut être remplacé par :

compteur ← initiale

(cas d'un pas positif)

TantQue   compteur <= finale
instructions
compteur ←  compteur+pas
FinTantQue

Lien entre Pour et TantQue : exemple

Calcul de x à la puissance n où x est un réel non nul et n un entier positif ou nul (version avec TantQue)

Variables x, puiss : réel
                        n, i : entier
Debut
                Ecrire (" Entrez la valeur de x ")
Lire (x)
Ecrire (" Entrez la valeur de n ")
Lire (n)
puiss ← 1
  i ← 1
TantQue (i<=n)
    puiss← puiss*x
                        i ← i+1
FinTantQue
Ecrire (x, " à la puissance  ", n, "  est égal à  ", puiss)
Fin

Boucles imbriquées

Les instructions d'une boucle peuvent être des instructions itératives. Dans ce cas, on aboutit à des boucles imbriquées
Exemple :

Pour i allant de 1 à 5
    Pour j allant de 1 à i
                            écrire("O")
  FinPour
écrire("X")
FinPour

Exécution

OX
    OOX
OOOX
  OOOOX
  OOOOOX

Les boucles Répéter … jusqu’à …

Syntaxe Générale

Répéter
           instructions
Jusqu'à condition

Condition est évaluée après chaque itération
les instructions entre Répéter et jusqu’à sont exécutées au moins une fois et leur exécution est répétée jusqu’à ce que condition soit vrai (tant qu'elle est fausse)

Boucle Répéter  jusqu’à  : exemple

Un algorithme qui détermine le premier nombre entier N tel que la somme de 1 à N dépasse strictement 100 (version avec répéter jusqu'à)

Variables som, i : entier
        Debut
                 som ← 0
               i ← 0                
                 Répéter
    i ←  i+1
som ←  som+i
Jusqu'à ( som > 100)
Ecrire (" La valeur cherchée est N=  ", i)
Fin

Choix d'un type de boucle

Si on peut déterminer le nombre d'itérations avant l'exécution de la boucle, il est plus naturel d'utiliser la boucle Pour
S'il n'est pas possible de connaître le nombre d'itérations avant l'exécution de la boucle, on fera appel à l'une des boucles TantQue ou répéter jusqu'à
Pour le choix entre TantQue et jusqu'à :

• Si on doit tester la condition de contrôle avant de commencer les instructions de la boucle, on utilisera  TantQue
• Si la valeur de la condition de contrôle dépend d'une première exécution des instructions de la boucle, on utilisera répéter jusqu'à