Répéter efficacement un traitement tout en maîtrisant sa terminaison

Fiche pédagogique du chapitre

Objectifs d’apprentissage

À la fin de ce chapitre, l’étudiant devra être capable de :

• expliquer le principe d’une structure répétitive ;
• identifier le compteur, la condition d’arrêt et les variables mises à jour dans une boucle ;
• choisir la boucle Pour lorsqu’un nombre de répétitions est connu ;
• utiliser correctement l’incrémentation, la décrémentation et le pas d’une boucle ;
• construire une boucle TantQue avec une initialisation et une mise à jour correctes ;
• utiliser Répéter…Jusqu’à lorsqu’un traitement doit être exécuté au moins une fois ;
• concevoir des boucles imbriquées pour produire des tableaux de valeurs ou des motifs ;
• détecter et corriger une boucle infinie ;
• effectuer le traçage manuel d’une boucle ;
• résoudre des problèmes classiques de somme, factorielle, primalité, PGCD et Fibonacci.

Prérequis

• connaître les variables, les constantes et les types simples ;
• savoir écrire des affectations et des expressions arithmétiques ;
• maîtriser les opérateurs relationnels et logiques ;
• savoir utiliser les structures conditionnelles ;
• comprendre le principe du traçage manuel d’un algorithme.

Plan du chapitre

6.1 Principe d’une boucle

6.2 Boucle Pour

6.3 Boucle TantQue

6.4 Boucle Répéter…Jusqu’à

6.5 Boucles imbriquées

6.6 Choix de la boucle appropriée

Applications, exercices, corrigés et synthèse

Organisation pédagogique indicative

Introduction aux structures répétitives

De nombreux traitements algorithmiques nécessitent la répétition d’une même opération : afficher une série de nombres, saisir plusieurs notes, parcourir un tableau, calculer une somme, vérifier progressivement un résultat ou recommencer une saisie jusqu’à ce qu’elle soit valide. Écrire plusieurs fois les mêmes instructions serait long, peu lisible et difficile à modifier.

Les structures répétitives, également appelées boucles ou itérations, permettent de regrouper les instructions répétées dans un bloc unique. Une boucle contrôle ensuite le nombre de répétitions ou la condition qui autorise leur poursuite.

6.1 Principe d’une boucle

6.1.1 Répétition d’un ensemble d’instructions

Une boucle exécute plusieurs fois un bloc appelé corps de la boucle. Chaque exécution du corps constitue une itération. Les instructions peuvent être identiques à chaque passage, mais les valeurs manipulées évoluent généralement d’une itération à l’autre.

Schéma conceptuel d’une répétition

6.1.2 Compteur

Un compteur est une variable entière utilisée pour compter les itérations, parcourir un intervalle ou représenter une position. Il est généralement initialisé avant la boucle, consulté dans la condition et modifié dans le corps de la boucle.

6.1.3 Condition d’arrêt

La condition d’arrêt détermine le moment où la répétition prend fin. Selon la structure utilisée, elle peut être formulée comme une condition de continuation, par exemple « tant que i <= N », ou comme une condition de terminaison, par exemple « jusqu’à saisie_valide ».

• Condition de continuation : la boucle s’exécute tant que la condition est vraie.
• Condition de terminaison : la boucle s’arrête lorsque la condition devient vraie.
• Progression : une variable utilisée dans la condition doit évoluer vers la fin de la boucle.
• Cas initial : il faut vérifier si la condition est vraie ou fausse avant la première itération.

6.1.4 Boucle finie et boucle infinie

Une boucle est finie lorsqu’elle atteint nécessairement sa condition d’arrêt après un nombre limité d’itérations. Elle est infinie lorsque cette condition ne peut jamais être atteinte, ou lorsque la variable qui la contrôle n’est pas correctement modifiée.

6.1.5 Accumulateur

Un accumulateur est une variable qui mémorise progressivement un résultat obtenu au fil des itérations. Il peut contenir une somme, un produit, un minimum, un maximum ou une chaîne construite progressivement.

La valeur initiale dépend de l’opération : 0 pour une somme, 1 pour un produit, une première donnée pour un minimum ou un maximum.

6.2 Boucle Pour

6.2.1 Syntaxe générale

La boucle Pour est adaptée lorsque le nombre de répétitions est connu ou peut être déterminé avant le début de la boucle. La variable i parcourt automatiquement les valeurs de début à fin, avec un pas généralement égal à 1.

6.2.2 Fonctionnement

6.2.3 Exemple : afficher de 1 à 5

6.2.4 Incrémentation

L’incrémentation consiste à augmenter une variable. Dans la forme standard de Pour, le compteur est automatiquement augmenté d’une unité après chaque itération. Il ne faut donc pas le modifier manuellement dans le corps de la boucle, sauf si le pseudo-code utilisé l’autorise explicitement et que le besoin est maîtrisé.

Incrémentation automatique de 1

6.2.5 Décrémentation

La décrémentation consiste à diminuer une variable. Pour parcourir des valeurs dans l’ordre décroissant, il faut préciser un pas négatif ou une forme dédiée « allant de début à fin par pas de -1 ».

Compte à rebours

6.2.6 Pas d’une boucle

Le pas indique la variation appliquée au compteur entre deux itérations. Un pas positif produit un parcours croissant ; un pas négatif produit un parcours décroissant. Un pas nul est interdit car le compteur ne progresserait jamais.

6.2.7 Bornes et nombre d’itérations

Lorsque les deux bornes sont incluses et que le pas vaut 1, le nombre d’itérations est fin - début + 1. Avec un pas positif p, le nombre dépend de l’écart entre les bornes et de la division entière par p. Il est essentiel de vérifier si les bornes appartiennent ou non au parcours dans le langage utilisé.

6.2.8 Exemple : somme des carrés

6.3 Boucle TantQue

6.3.1 Syntaxe générale

La boucle TantQue est utilisée lorsque le nombre de répétitions n’est pas nécessairement connu à l’avance. La répétition dépend d’une condition évaluée avant chaque itération.

6.3.2 Test avant exécution

La condition est testée avant l’exécution du corps. Si elle est fausse dès le début, le corps n’est jamais exécuté. Une boucle TantQue peut donc effectuer zéro, une ou plusieurs itérations.

Dans cet exemple, x < 5 est faux avant la première itération. Aucun affichage n’est produit.

6.3.3 Initialisation

Les variables utilisées dans la condition doivent recevoir une valeur avant le premier test. Une variable non initialisée rend le comportement de l’algorithme indéterminé ou provoque une erreur.

6.3.4 Mise à jour de la condition

Au moins une instruction du corps doit faire évoluer la situation vers la fin de la boucle. Cette évolution peut modifier directement le compteur, lire une nouvelle saisie, réduire un reste, changer un état booléen ou recevoir une réponse externe.

6.3.5 Exemple : demander un nombre strictement positif

La première lecture est nécessaire avant le test. Si la valeur est déjà valide, le corps de la boucle n’est pas exécuté. Dans le cas contraire, la lecture est répétée jusqu’à l’obtention d’une valeur positive.

6.3.6 Exemple : nombre de chiffres d’un entier positif

6.4 Boucle Répéter…Jusqu’à

6.4.1 Syntaxe générale

La boucle Répéter…Jusqu’à exécute d’abord le corps, puis évalue la condition de terminaison. Elle convient lorsque le traitement doit avoir lieu au moins une fois, notamment pour une saisie utilisateur ou un menu interactif.

6.4.2 Test après exécution

Le test est effectué après le corps. Lorsque la condition devient vraie, la boucle s’arrête. Tant qu’elle est fausse, une nouvelle itération commence. Cette logique est l’inverse de TantQue, qui continue tant que sa condition est vraie.

6.4.3 Exécution au moins une fois

La saisie est réalisée avant la vérification. Si la première note est valide, la condition est immédiatement vraie et la boucle s’arrête après une seule itération.

6.4.4 Exemple : menu simple

6.4.5 Transformation entre TantQue et Répéter

Une boucle Répéter peut souvent être réécrite avec TantQue, mais il faut ajouter une première exécution ou initialiser les variables avec prudence. La transformation doit respecter la différence entre condition de continuation et condition de terminaison.

6.5 Boucles imbriquées

6.5.1 Boucle à l’intérieur d’une autre boucle

Une boucle est imbriquée lorsqu’elle se trouve à l’intérieur du corps d’une autre boucle. Pour chaque itération de la boucle externe, la boucle interne effectue son parcours complet.

La boucle externe s’exécute 3 fois et, pour chacune de ses itérations, la boucle interne s’exécute 4 fois. Le bloc Écrire est donc exécuté 3 × 4 = 12 fois.

6.5.2 Traçage de deux boucles

6.5.3 Génération de tableaux de valeurs

Les boucles imbriquées permettent de générer des tables à deux dimensions. La boucle externe représente généralement les lignes et la boucle interne les colonnes.

Table de multiplication de 1 à 5

6.5.4 Construction de formes et de motifs

Pour construire une forme, la boucle externe contrôle le nombre de lignes et la boucle interne le nombre de caractères affichés sur chaque ligne.

Triangle croissant

6.5.5 Coût des boucles imbriquées

Le nombre total d’exécutions du corps interne est souvent le produit des nombres d’itérations. Deux boucles de N itérations chacune produisent environ N² exécutions. Cette observation sera approfondie dans le chapitre consacré à la complexité.

6.6 Choix de la boucle appropriée

6.6.1 Nombre de répétitions connu

Lorsque le nombre d’itérations est déterminé avant l’entrée dans la boucle, Pour est généralement le choix le plus simple et le plus lisible.

• parcourir les entiers de 1 à N ;
• saisir exactement 20 notes ;
• afficher une table de multiplication ;
• parcourir toutes les positions d’un tableau de taille connue.

6.6.2 Répétition dépendant d’une condition

Lorsque l’arrêt dépend d’un événement ou d’une condition dont on ne connaît pas à l’avance le moment de réalisation, TantQue est adapté. Le corps peut ne jamais s’exécuter si la condition initiale est fausse.

• continuer une recherche tant que l’élément n’est pas trouvé ;
• répéter un calcul jusqu’à obtenir une précision suffisante ;
• traiter des données tant qu’il en reste ;
• effectuer des soustractions tant que le reste est suffisant.

6.6.3 Validation d’une saisie utilisateur

Lorsqu’une valeur doit être demandée au moins une fois puis répétée tant qu’elle est invalide, Répéter…Jusqu’à est souvent la forme la plus naturelle. TantQue reste possible avec une première lecture avant la boucle.

6.6.4 Méthode de conception d’une boucle

1. Identifier exactement le traitement à répéter.

2. Choisir la variable ou l’événement qui contrôle la répétition.

3. Déterminer la valeur initiale de cette variable.

4. Formuler la condition de continuation ou de terminaison.

5. Définir la mise à jour qui garantit la progression.

6. Tracer les premières et les dernières itérations.

7. Tester le cas où la boucle ne s’exécute pas et le cas d’une seule itération.

8. Vérifier que la boucle se termine pour toutes les entrées valides.

6.6.5 Erreurs fréquentes

Applications guidées

Les applications suivantes montrent comment analyser un problème répétitif, choisir une boucle, initialiser les variables, effectuer la mise à jour et vérifier le résultat.

Application 1 — Afficher les nombres de 1 à N

Problème : lire un entier positif N puis afficher tous les entiers de 1 à N dans l’ordre croissant.

Application 2 — Calculer la somme des nombres de 1 à N

La variable somme est un accumulateur. Elle doit être initialisée à 0 avant la boucle.

Application 3 — Calculer une factorielle

La factorielle de N, notée N!, est le produit des entiers de 1 à N. Par convention, 0! = 1. La variable produit doit donc être initialisée à 1.

Application 4 — Afficher une table de multiplication

Le compteur représente le multiplicateur. Le nombre d’itérations est connu : onze lignes lorsque l’intervalle va de 0 à 10 inclus.

Application 5 — Compter les nombres pairs et impairs

On souhaite lire N nombres et compter séparément les valeurs paires et impaires. Deux compteurs sont initialisés à zéro.

Application 6 — Vérifier si un nombre est premier

Un entier supérieur ou égal à 2 est premier s’il ne possède aucun diviseur autre que 1 et lui-même. Il suffit de chercher un diviseur de 2 jusqu’à la racine carrée du nombre. Une version introductive peut tester jusqu’à nombre - 1, mais elle effectue davantage d’opérations.

Application 7 — Calculer le PGCD

Le PGCD de deux entiers positifs peut être calculé avec l’algorithme d’Euclide. À chaque étape, on remplace le couple (a, b) par (b, a MOD b) jusqu’à ce que b devienne nul.

Application 8 — Générer la suite de Fibonacci

La suite de Fibonacci commence généralement par 0 et 1. Chaque terme suivant est la somme des deux termes précédents. Il faut mémoriser les deux derniers termes et les mettre à jour sans perdre leur valeur.

Synthèse du chapitre

Règles essentielles à retenir

• initialiser toutes les variables avant leur première utilisation ;
• choisir une valeur neutre adaptée pour les accumulateurs ;
• formuler clairement la condition de continuation ou de terminaison ;
• prévoir une mise à jour qui rapproche de l’arrêt ;
• vérifier les bornes et le nombre d’itérations ;
• tester les cas zéro itération, une itération et plusieurs itérations ;
• ne pas modifier inutilement le compteur d’une boucle Pour ;
• contrôler le coût des boucles imbriquées ;
• utiliser l’indentation pour rendre les blocs visibles.

Table de choix rapide

Travaux dirigés

Exercice 1 — Traçage d’une boucle Pour

Tracer l’algorithme suivant et donner les valeurs affichées :

Exercice 2 — Corriger une boucle infinie

Identifier l’erreur et proposer une correction :

Exercice 3 — Somme des multiples

Écrire un algorithme qui calcule la somme de tous les multiples de 3 compris entre 1 et N.

Exercice 4 — Saisie contrôlée

Demander une note comprise entre 0 et 20. Répéter la saisie tant que la valeur est invalide, puis afficher « Note acceptée ». Proposer une version avec TantQue et une version avec Répéter…Jusqu’à.

Exercice 5 — Compter les chiffres pairs

Lire un entier positif et compter combien de ses chiffres sont pairs. Par exemple, 42037 contient trois chiffres pairs : 4, 2 et 0.

Exercice 6 — Inverser les chiffres d’un entier

Écrire un algorithme qui transforme 12340 en 4321 en utilisant DIV et MOD.

Exercice 7 — Triangle d’étoiles

Afficher un triangle décroissant de N lignes. Pour N = 4 : ****, ***, **, *. Chaque ligne doit être produite par une boucle interne.

Exercice 8 — Table complète de multiplication

Construire une table de multiplication de 1 à 10 sous forme de grille à l’aide de deux boucles imbriquées.

Exercice 9 — Plus grand diviseur propre

Lire un entier N > 1 et déterminer son plus grand diviseur strictement inférieur à N. Réfléchir à un parcours décroissant permettant de s’arrêter dès qu’un diviseur est trouvé.

Exercice 10 — Fibonacci inférieur à une limite

Afficher tous les termes de Fibonacci strictement inférieurs à une limite L. Le nombre de termes n’étant pas connu à l’avance, choisir une structure adaptée.

Corrigé indicatif des travaux dirigés

Corrigé de l’exercice 1

Corrigé de l’exercice 2

La variable i n’est jamais mise à jour. La condition i <= 10 reste donc toujours vraie.

Corrigé de l’exercice 3

Une autre solution consiste à parcourir tous les entiers de 1 à N et à ajouter uniquement ceux pour lesquels i MOD 3 = 0. La solution avec un pas de 3 évite les tests inutiles.

Corrigé de l’exercice 4

Corrigé de l’exercice 5

Corrigé de l’exercice 6

Corrigé de l’exercice 7

Corrigé de l’exercice 8

Corrigé de l’exercice 9

La boucle se termine au plus tard pour diviseur = 1, qui divise tout entier. Pour un nombre premier, le résultat est donc 1.

Corrigé de l’exercice 10

Glossaire

Auto-évaluation

L’étudiant peut considérer le chapitre acquis s’il sait répondre positivement aux questions suivantes :

• Puis-je identifier le corps, le compteur et la condition d’arrêt d’une boucle ?
• Puis-je expliquer pourquoi une boucle donnée se termine ?
• Puis-je détecter une boucle infinie ?
• Puis-je choisir entre Pour, TantQue et Répéter…Jusqu’à ?
• Puis-je initialiser correctement une somme et un produit ?
• Puis-je tracer l’évolution des variables à chaque itération ?
• Puis-je gérer les cas zéro et une itération ?
• Puis-je écrire une saisie contrôlée ?
• Puis-je construire un motif à l’aide de boucles imbriquées ?
• Puis-je résoudre les problèmes de factorielle, primalité, PGCD et Fibonacci ?