Aller au contenu
Topos Uranos
Français

Boucles

Résumé

La leçon Du problème à l’algorithme a reconnu trois façons de composer des étapes : la séquence, la décision et la répétition. Les deux premières ont déjà leur écriture en C++ ; cette leçon donne la sienne à la troisième. Elle étudie les trois formes de la boucle : while, qui évalue sa condition avant chaque itération et peut ne jamais exécuter son corps ; do, qui l’évalue après et exécute le corps au moins une fois ; et for, qui réunit sur une ligne l’initialisation, la condition et l’incrément de la variable qui gouverne la répétition. Elle montre que les trois expriment un même mécanisme, de sorte que chacune se transforme en les autres, et elle apprend à choisir la plus claire ; elle présente break et continue, qui modifient le cours d’une itération ; et elle se termine par les boucles imbriquées, dont le corps interne s’exécute un nombre de fois qui se calcule par une somme. L’instrument qui accompagne toute la leçon est le tableau de suivi : suivre une boucle à la main, itération par itération, est la manière de prévoir combien de fois son corps s’exécute et ce qu’elle laisse en sortant.

Objectifs d’apprentissage

  1. Écrire une boucle while, do ou for pour une répétition donnée, en choisissant la forme la plus claire.
  2. Suivre une boucle à la main avec son tableau de suivi et prévoir combien de fois le corps s’exécute.
  3. Transformer une boucle d’une forme en une autre en conservant sa signification.
  4. Écrire des boucles imbriquées et calculer combien de fois le corps interne s’exécute.

while

La forme d’un while

Un while s’écrit ainsi :

Code C++
while (condition) {    corps}

Sa signification s’énonce en trois étapes : on évalue la condition ; si elle est fausse, la boucle se termine et l’exécution continue après l’accolade qui la ferme ; si elle est vraie, on exécute le corps et on revient à la première étape. Chaque exécution du corps s’appelle une itération (ou tour). La condition est une expression booléenne comme celles de la leçon Relations et logique, et le corps est un bloc ; la règle des accolades que la leçon Décisions a fixée vaut aussi ici : le corps d’une boucle porte toujours des accolades, même s’il ne contient qu’une seule instruction.

Deux conséquences découlent de la définition. La première : la condition est évaluée avant chaque itération, de sorte que, si elle est fausse dès le début, le corps n’est exécuté aucune fois. La seconde : pour que la boucle se termine, le corps doit changer quelque chose de ce que lit la condition ; si rien ne change, la condition qui a été vraie une fois le sera toujours. Or changer ne suffit pas : la leçon Du problème à l’algorithme a montré qu’il faut une quantité à valeurs naturelles qui décroisse à chaque itération, le variant, et la leçon Concevoir des boucles correctes en fera une méthode.

La division par soustractions successives

Le premier algorithme avec répétition du cours a été la division par soustractions successives : tant que le reste est au moins égal au diviseur, on lui soustrait le diviseur et on ajoute un au quotient. Écrit en C++, l’algorithme se transpose presque mot pour mot.

ExempleLe quotient et le reste par soustractions
Programme en C++
#include <iostream>#include <print>​int main(){    int a{};    int b{};    std::cin >> a >> b;    int q{0};    int r{a};    while (r >= b) {        r -= b;        ++q;    }    std::println("{} = {} · {} + {}", a, b, q, r);}
Entrée du programme
23 7
Sortie
23 = 7 · 3 + 2

Les lignes 9 et 10 donnent aux variables leur valeur initiale : on n’a encore rien soustrait, de sorte que le quotient vaut 0 et le reste est tout le dividende. La ligne 11 est la condition de l’étape 2 de l’algorithme ; les lignes 12 et 13, le corps. Le programme suppose, comme l’algorithme, que a≥0a \geq 0 et b>0b > 0 : avec b=0b = 0, la ligne 12 ne changerait pas r et la boucle ne se terminerait pas.

Le tableau de suivi

Suivre la boucle à la main, c’est remplir un tableau : une ligne par itération, une colonne par variable et une pour la condition, évaluée au début de l’itération. La ligne 0 enregistre l’état avant la première évaluation ; la dernière, l’évaluation qui se révèle fausse et termine la boucle.

ExempleLe suivi de 23 divisé par 7

Démonstration

  1. Avant la boucle, on exécute les lignes 9 et 10 : q=0q = 0 et r=23r = 23. C’est la ligne 0 du tableau ; la condition n’a pas encore été évaluée.

  2. Première itération. La condition 23≥723 \geq 7 est vraie, de sorte qu’on exécute le corps : rr passe à 16 et qq à 1. Ensuite l’exécution revient à la ligne 11.

  3. Deuxième itération. 16≥716 \geq 7 est vraie : rr passe à 9 et qq à 2.

  4. Troisième itération. 9≥79 \geq 7 est vraie : rr passe à 2 et qq à 3.

  5. La quatrième évaluation, 2≥72 \geq 7, est fausse : le corps n’est pas exécuté, la boucle se termine et la ligne 15 écrit 23=7⋅3+223 = 7 \cdot 3 + 2.

Le suivi apprend à compter. Le corps a été exécuté trois fois, autant que le quotient, et la condition a été évaluée quatre fois : une par itération et une de plus, celle qui échoue. Cette relation vaut pour tout while qui se termine par sa condition : si le corps est exécuté kk fois, la condition est évaluée k+1k + 1 fois. Et le cas extrême le confirme : avec l’entrée 5 7, la première évaluation, 5≥75 \geq 7, est déjà fausse, le corps est exécuté zéro fois, et le programme écrit 5=7⋅0+55 = 7 \cdot 0 + 5, ce qui est correct. Un while bien écrit traite sans code supplémentaire le cas où il n’y a rien à répéter.