Les itérations

Date de publication : 16/03/2002 , Date de mise à jour : 27/01/2007

Quoi de plus énervant que de dupliquer du code !

Ce tutoriel vous initie aux deux types de boucles qu'il existe : l'itération inconditionnelle et l'autre dite conditionnelle.

Introduction
1. Répétitions inconditionnelles
1.1. Exemple 1 (cas simple, compteur croisant)
1.2. Exemple 2
1.3. Exemple 3 (calcul de la récurrence : cas de la somme)
1.4. Exemple 4 (calcul par récurrence d'un maximum, initialisation à un terme artificiel)
1.5. Exemple 5 (calcul par récurrence, initialisation à un terme utile)
2. Répétitions conditionnelles
2.1. Exemple 1
2.2. Exemple 2
3. Boucles imbriquées
3.1. Exemple

Introduction

Il arrive souvent dans un algorithme que dans la même action soit répétée plusieurs fois, avec éventuellement quelques variations dans les paramètres qui précisent le déroulement de l'action. Il est alors fastidieux d'écrire un algorithme qui contient de nombreuses fois la même instruction. De plus, ce nombre peut dépendre du déroulement de l'algorithme. Il est alors impossible de savoir à l'avance combien de fois la même instruction doit être décrite. Pour gérer ces cas, on fait appel à des instructions en boucle qui ont pour effet de répéter plusieurs fois une même instruction. Deux formes existent : la première, si le nombre de répétitions est connu avant l'exécution de l'instruction de répétition, la seconde s'il n'est pas connu. On appellera itération l'exécution de la liste des instructions.

1. Répétitions inconditionnelles

Il est fréquent que le nombre de répétitions soit connu à l'avance, et que l'on ait besoin d'utiliser le numéro de l'itération afin d'effectuer des calculs ou des tests. Le mécanisme permettant cela est la boucle Pour.

Forme de la boucle Pour :

Pour variable de valeur initiale à valeur finale faire
    liste d'instructions
fpour

La variable dont on donne le nom va prendre successivement toutes les valeurs entières entre valeur initiale et valeur finale. Pour chaque valeur prise par la variable, la liste des instructions est exécutée. La valeur utilisée pour énumérer les itérations est appelée valeur d'itération, indice d'itération ou compteur. L'incrémentation par 1 de la variable est implicite.

Autre forme de la boucle Pour :

Pour variable décroissante de valeur initiale à valeur finale faire
    liste d'instructions
fpour

La variable d'itération est décrémentée de 1 après chaque itération.

1.1. Exemple 1 (cas simple, compteur croisant)

Ecrire l'algorithme permettant d'afficher la table de multiplication par 9.

Un algorithme possible est le suivant :

Algorithme
    début
        écrire(1*9)
        écrire(2*9)
        écrire(3*9)
        écrire(4*9)
        écrire(5*9)
        écrire(6*9)
        écrire(7*9)
        écrire(8*9)
        écrire(9*9)
        écrire(10*9)
    fin

Il est plus simple d'utiliser une boucle avec un compteur prenant d'abord la valeur 1, puis augmentant peu à peu jusqu'à atteindre 10.

Algorithme
    début
        pour i de 1 à 10 faire
            écrire(i*9)
        fpour
    fin

Lexique
    - i : entier, indice d'itération

1.2. Exemple 2

Compte à rebours : écrire l'algorithme de la fonction qui, à partir d'un nombre entier positif n, affiche tous les nombres par ordre décroissant jusqu'à 0.

Exemple : pour n=5, le résultat sera 5 4 3 2 1 0.

Algorithme
    fonction compteARebours (n:entier)
        début
            pour i décroissant de n à O faire
                écrire(i)
            fpour
        fin

Lexique
    - n : entier
    - i : entier, indice d'itération

1.3. Exemple 3 (calcul de la récurrence : cas de la somme)

On veut imprimer, pour n donné, la somme des carrés des n premiers entiers.

Cette somme, notée s, est obtenue en calculant le n-ième terme d'une suite définie par récurrence :

s_n=s_n-1+i²

Algorithmiquement, le calcul d'une telle suite se fait en deux étapes :
- initialisation (ici, s₀=0)
- répétition de : calcul du i^ème terme en fonction du terme d'indice i-1

Algorithme
    début 	
        n <- lire()           // 1
        s <- 0                // 2
        pour i de 1 à n faire // 3
            s <- s + i2       // 4
        fpour 	
        écrire(s)             // 5
    fin

Lexique
    - s : entier, somme des carré des n premiers entiers
    - n : entier
    - i : entier, indice d'itération

Schéma de l'évolution de l'état des variables instruction par instruction :

On suppose que la valeur introduite par l'utilisateur est 4.

Instructions	n	s	i
1	4
2		0
3			1
4		1
3			2
4		5
3			3
4		14
3			4
4		30
3			(fin)
5		écrire()

1.4. Exemple 4 (calcul par récurrence d'un maximum, initialisation à un terme artificiel)

Ecrire l'algorithme qui permet d'imprimer le maximum de n entiers positifs donnés au fur et à mesure.

Comment trouver ce maximum ? C'est le plus grand des 2 nombres : maximum des n-1 premiers entiers positifs donnés, n-ème entier donné. Ceci est une définition par récurrence :

Si nombre_n > maximum_n-1 alors maximum_n <- nombre_n sinon nombre_n <- maximum_n-1 fsi

Comment initialiser la suite maximum ? Il faut que maximum₁ prenne la valeur nombre₁. Il suffit alors de choisir une valeur de maximum₀ plus petite que tout entier positif, par exemple maximum₀ = -1, de manière à assurer que maximum₁ aura bien nombre₁ pour valeur. Il s'agit d'une initialisation à un terme artificiel.

Algorithme
	début 	
        n <- lire()                   // 1
        maximum <- -1                 // 2
        pour i de 1 à n faire         // 3
            nombre <- lire()          // 4
            si nombre > maximum alors // 5
                maximum <- nombre     // 6
            fsi
        fpour
        écrire(maximum)               // 7
    fin
	
Lexique
    - n : entier, nombre d'entiers positifs donné
    - maximum : entier, maximum des i premiers entiers
    - nombre : entier, ième nombre lu
    - i : entier, indice d'itération

Schéma de l'évolution de l'état des variables instruction par instruction :

On suppose que les valeurs introduites par l'utilisateur sont : 4 (nombre d'entiers à comparer), 2, 0, 8, 7.

Instructions	n	maximum	i	nombre	nombre > maximum
1	4
2		-1
3			1
4				2
5					vrai
6		2
3			2
4				0
5					faux
3			3
4				8
5					vrai
6		8
3			4
4				7
5					faux
3			(fin)
7		écrire()

1.5. Exemple 5 (calcul par récurrence, initialisation à un terme utile)

Ecrire l'algorithme qui permet d'imprimer le maximum de n entiers donnés.

L'initialisation à un terme artificiel n'est plus possible ici car les valeurs ne sont plus bornées inférieurement. Une solution consiste alors à initialiser au premier terme et à commencer la formule générale de récurrence à 2. Il s'agit d'une initialisation à un terme utile.

Algorithme
    début 	
        n <- lire()                   // 1
        maximum <- lire()             // 2
        pour i de 2 à n faire         // 3
            nombre <- lire()          // 4
            si nombre > maximum alors // 5
                maximum <- nombre     // 6
            fsi
        fpour
        écrire(maximum)               // 7
    fin

Lexique
    - n : entier, nombre d'entiers positifs donné
    - maximum : entier, maximum des i premiers entiers
    - nombre : entier, ième entier positif donné
    - i : entier, indice d'itération

Schéma de l'évolution de l'état des variables instruction par instruction :

On suppose que les valeurs introduites par l'utilisateur sont : 4 (nombre d'entiers à comparer), 2, 0, 8, 7.

Instructions	n	maximum	i	nombre	nombre > maximum
1	4
2		2
3			2
4				0
5					faux
3			3
4				8
5					vrai
6		8
3			4
4				7
5					faux
3			(fin)
7		écrire()

2. Répétitions conditionnelles

L'utilisation d'une boucle pour nécessite de connaître à l'avance le nombre d'itérations désiré, c'est-à-dire la valeur finale du compteur. Dans beaucoup de cas, on souhaite répéter une instruction tant qu'une certaine condition est remplie, alors qu'il est à priori impossible de savoir à l'avance au bout de combien d'itérations cette condition cessera d'être satisfaite. Le mécanisme permettant cela est la boucle Tant que.

Syntaxe de la boucle Tant que :

tant que condition faire
    liste d'instructions
ftant

Cette instruction a une condition de poursuite dont la valeur est de type booléen et une liste d'instructions qui est répétée si la valeur de la condition de poursuite est vraie : la liste d'instructions est répétée autant de fois que la condition de poursuite a la valeur vraie. Le déroulement pas à pas de cette instruction équivaut à :

si condition
    alors liste d'instructions
        si condition
            alors liste d'instructions
                si condition
                    alors liste d'instructions
                        ...

Etant donné que la condition est évaluée avant l'exécution des instructions à répéter, il est possible que celles-ci ne soient jamais exécutées. Il faut que la liste des instructions ait une incidence sur la condition afin qu'elle puisse être évaluée à faux et que la boucle se termine. Il faut toujours s'assurer que la condition devient fausse au bout d'un temps fini.

2.1. Exemple 1

On veut laisser un utilisateur construire des rectangles de taille quelconque, à condition que les largeurs qu'il saisit soient supérieures à 1 pixel. On peut utiliser une répétition conditionnelle qui permet de redemander à l'utilisateur de saisir une nouvelle valeur tant que celle-ci n'est pas valide.

Algorithme
    fonction saisirLargeurRectangle
        début
            écrire("indiquez la largeur du rectangle :")
            largeur <- lire()
            tant que largeur < 1 faire
                écrire("erreur : indiquez une valeur strictement positive")
                écrire("indiquez la largeur du rectangle :")
                largeur <- lire()
            ftant
            retourne largeur
        fin

Lexique
    - largeur : entier, largeur courante saisie

2.2. Exemple 2

Un poissonnier sert un client qui a demandé 1Kg de poisson. Il pèse successivement différents poissons et s'arrête dès que le poids total égale ou dépasse 1Kg. Donner le nombre de poissons servis.

Remarque sur la terminaison :
Ce problème est typique des cas où le dernier terme (celui qui fait basculer le test) doit être retenu.

Algorithme
    début 	
        poids_total <- 0                              // 1
        nb_poisson <- 0                               // 2
        tant que poids_total < 1000 faire             // 3 (itération i)
            poids_poisson <- lire()                   // 4
            poids_total < poids_total + poids_poisson // 5
            nb_poisson <- nb_poisson + 1              // 6
        ftant
        écrire(nb_poisson)                            // 7
	fin

Lexique
    - poids_total : réel, poids total des i premiers poissons
    - poids_poisson : réel, poids du ième poisson en grammes
    - nb_poisson : entier, nombre de poissons vendus après la ième itération

Schéma de l'état des variables instruction par instruction :

On suppose que les valeurs introduites par l'utilisateur sont : 350, 280, 375.

Instructions	poids_total	nb_poisson	poids_poisson	poids_total < 1000
1	0
2		0
3				vrai
4			350
5	350
6		1
3				vrai
4			280
5	630
6		2
3				vrai
4			375
5	1005
6		3
3				faux
7		écrire()

3. Boucles imbriquées

Le corps d'une boucle est une liste d'instructions. Mais cette boucle est elle-même une instruction. Donc le corps d'une boucle peut contenir une boucle dite imbriquée, qui utilise un compteur différent. Il faut alors faire attention à l'ordre d'exécution des instructions : à chaque passage dans le corps de la boucle principale, la boucle imbriquée va être exécutée totalement.

3.1. Exemple

Ecrire l'algorithme permettant d'imprimer le triangle suivant, le nombre de lignes étant donné par l'utilisateur :

1
12
123
1234
12345
...

Algorithme
    début
        nblignes <- lire()           // 1
        Pour i de 1 à nblignes faire // 2
            Pour j de 1 à i faire    // 3
                écrire(j)            // 4
            fpour
            retour à la ligne        // 5
        fpour
    fin

Lexique
    - nblignes : entier, nombre de lignes à imprimer
    - i : entier, indice d'itération sur les lignes
    - j : entier, indice d'itération sur les éléments de la ième ligne

Schéma d'évolution de l'état des variables instruction par instruction :

On suppose que la valeur introduite pas l'utilisateur est 3.

Instructions	nblignes	i	j
1	3
2		1
3			1
4			écrire()
3			(fin)
5				retour à la ligne
2		2
3			1
4			écrire()
3			2
4			écrire()
3			(fin)
5				retour à la ligne
2		3
3			1
4			écrire()
3			2
4			écrire()
3			3
4			écrire()
3			(fin)
5				retour à la ligne
2		(fin)

Copyright © 2007 . Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à 3 ans de prison et jusqu'à 300 000 E de dommages et intérêts. Cette page est déposée à la SACD.