Algorithmique · Chapitre 18 · Conditions et boucles

Comprendre les boucles imbriquées

Parcourez une grille avec deux boucles imbriquées. Tracez les couples ligne-colonne et distinguez les tours intérieurs des tours extérieurs.

Par Ali ZAINOUL · Cours gratuit

Ce que vous allez apprendre

Tracer une boucle intérieure pour chaque tour extérieur.
Distinguer coordonnées choisies et indices d'un tableau.
Calculer le nombre d'exécutions d'un corps imbriqué.

Prérequis. Savoir suivre une boucle POUR et un compteur.

Visiter une grille de deux lignes et trois colonnes

Nous voulons afficher les coordonnées de chaque case : d'abord toutes les colonnes de la ligne 1, puis toutes celles de la ligne 2. Les coordonnées choisies commencent à 1 dans les deux langages ; nous n'accédons pas ici à un tableau Python indexé à partir de zéro.

Finir un parcours intérieur avant de changer de ligne

La boucle extérieure fixe row. Pour cette ligne, la boucle intérieure fait varier column de 1 à 3. Ce n'est qu'après ces trois tours intérieurs que la ligne change. À la ligne suivante, le parcours des colonnes recommence à 1.

Comprendre une grille avant les deux boucles

Une grille organise des positions en lignes et colonnes. Un couple réunit ici deux nombres : le numéro de ligne et le numéro de colonne. Pour deux lignes et trois colonnes, les positions sont (1, 1), (1, 2), (1, 3), (2, 1), (2, 2) et (2, 3). Nous ne stockons pas encore un tableau à deux dimensions ; nous visitons ses positions.

Une boucle imbriquée est une boucle placée dans le corps d'une autre boucle. La boucle extérieure choisit une ligne ; la boucle intérieure parcourt toutes les colonnes de cette ligne. Quand la ligne change, un nouveau parcours intérieur commence à sa première colonne.

Le compteur count augmente pour chaque couple visité, et non pour chaque changement de ligne. Dans l'exemple, deux groupes de trois visites donnent six visites. La multiplication 2 × 3 compte cette opération précise ; elle ne mesure pas la durée réelle du programme ni toutes les instructions de gestion des boucles.

Pour examiner le cas limite, fixez le nombre de lignes ou de colonnes à zéro. Aucune position n'est alors visitée et le compteur reste nul. Un parcours diagonal, qui augmente ligne et colonne ensemble, ne donnerait que quelques couples : ce serait un autre problème que la visite complète de la grille.

Deux blocs, deux variables

1
2
3
4
5
6
7
8
9
10
11
12// example.pseudo
// visit_grid
rows <- 2
columns <- 3
count <- 0
FOR row FROM 1 TO rows INCLUSIVE DO
    FOR column FROM 1 TO columns INCLUSIVE DO
        PRINT row, column
        count <- count + 1
    END FOR
END FOR
PRINT count

1
2
3
4
5
6
7
8
9# visit_grid.py
rows = 2
columns = 3
count = 0
for row in range(1, rows + 1):
    for column in range(1, columns + 1):
        print(row, column)
        count = count + 1
print(count)  # 6

1
2
3
4
5
6
7
8
9
10
11% visit_grid.m
rows = 2;
columns = 3;
count = 0;
for row = 1:rows
    for column = 1:columns
        disp([row, column]);
        count = count + 1;
    end
end
disp(count); % 6

count est initialisé une seule fois pour toute la grille. L'initialiser à l'intérieur de la boucle extérieure compterait seulement les cases de la dernière ligne. Les deux niveaux d'indentation indiquent les instructions répétées à chaque case.

Énumérer les cases dans l’ordre

Six visites, regroupées par ligne
Tour extérieur : row	Tours intérieurs : column	count en fin de ligne
1	1, puis 2, puis 3	3
2	1, puis 2, puis 3	6

Les couples affichés sont (1,1), (1,2), (1,3), (2,1), (2,2), (2,3). Compter uniquement les deux tours extérieurs oublierait le travail de la boucle intérieure. Chaque ligne comporte trois visites, donc deux lignes donnent 2 × 3 = 6 visites.

Changer une dimension à la fois

Prévoyez les parcours pour une ligne et trois colonnes, puis pour deux lignes et une colonne. Avec zéro ligne, le corps intérieur n'est jamais atteint. Avec deux lignes et zéro colonne, la boucle extérieure parcourt deux lignes mais aucune case n'est visitée : count reste zéro.

Lire une autre organisation

Que change l'inversion des deux boucles ?

On visite d'abord toutes les lignes d'une colonne, puis on change de colonne. Pour la même grille, le nombre de cases reste six, mais l'ordre d'affichage devient (1,1), (2,1), (1,2), (2,2), (1,3), (2,3).

Combien de visites pour 4 lignes et 5 colonnes ?

Vingt : chacune des quatre lignes déclenche cinq tours intérieurs. Ce calcul ne s'appliquerait pas tel quel si la borne intérieure changeait selon la ligne ; il faudrait alors compter les visites ligne par ligne.

Décomposer le travail répété

Une boucle imbriquée exprime un parcours à plusieurs niveaux. Pour l'expliquer, commencez par un seul tour extérieur complet. Cette méthode de lecture reste utile lorsque les instructions deviennent plus longues et que l'on décide de les extraire dans une fonction.

À retenir - fiche mémo

Extérieure: La boucle extérieure choisit une ligne.
Intérieure: La boucle intérieure parcourt toutes les colonnes pour cette ligne.
Comptage: Deux lignes de trois colonnes produisent six couples visités.

Pseudo-code

// example.pseudo
// visit_grid
FOR row FROM 1 TO rows INCLUSIVE DO
    FOR column FROM 1 TO columns INCLUSIVE DO
        PRINT row, column
    END FOR
END FOR

Point de vigilance. Augmenter ligne et colonne ensemble ne parcourt pas toute la grille.

Consulter la cheatsheet : Conditions et boucles · Télécharger la fiche du thème en PDF