Les itérations

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.

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'intructions

fpour




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




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




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




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, sommme 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()





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()





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 a 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 supppose que les valeurs introduites par l'utilisateur sont : 4 (nombre d'entiers à comparer), 0, 2, 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()

 

 

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 instuction é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.




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




Exemple 2

Un poissonier 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_poison	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()

 

 

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.




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 à imrimer
- 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)

© Aflo Informatique , 2003-2004