Ruban de Möbius

Boucle

Dans un algorithme, il arrive souvent que l'on doive répéter un même ensemble d'instructions.

Pour cela, on utilise une boucle.

Il existe deux sortes de boucles : la boucle pour (ou for, en anglais) et la boucle tant que (ou boucle while).

La boucle pour

On utilise une boucle pour quand on peut prévoir le nombre de répétitions qui seront nécessaires.

Une boucle pour utilise une variable appelée compteur. La valeur contenue dans cette variable augmente automatiquement de 1 après chaque répétition. On contrôle le nombre de répétitions en fixant les valeurs initiale et finale du compteur.

Considérons, par exemple, pour un nombre entier N supérieur ou égal à 2, la puissance de 2 :

p = 2 N

Ce nombre s'obtient en multipliant 2 par lui-même N − 1 fois.

Un algorithme de calcul de 2 N utiliserait donc une boucle pour.

Voici comment s'écrirait cette boucle en langage naturel :

p prend la valeur 2

Pour k allant de 1 à N − 1

p prend la valeur p × 2

Fin de Pour

A l'issue de ces instructions, la variable p est passée de la valeur initiale 2 à la valeur 2 N.

L'instruction p prend la valeur 2 constitue une étape de l'algorithme qui s'appelle l'initialisation.

On peut imaginer un algorithme avec une initialisation différente, comme ci-dessous :

p prend la valeur 1

Pour k allant de 1 à N

p prend la valeur p × 2

Fin de Pour

Le résultat est le même : la valeur finale de p est égale à 2 N.

La boucle tant que

Parfois, il n'est pas possible de prévoir combien de répétitions seront nécessaires.

Reprenons, par exemple, la suite des puissances de 2 et imaginons que l'on recherche à partir de quelle valeur de N le nombre p = 2 N dépasse la valeur 1000.

On peut demander à un algorithme de calculer successivement les différentes puissances de 2, et prévoir que cet algorithme s'arrête dès que le résultat dépasse 1000.

Ceci peut se faire au moyen d'une boucle Tant que :

N prend la valeur 1

p prend la valeur 2

Tant que p ≤ 1000

p prend la valeur p × 2

N prend la valeur N + 1

Fin de Tant que

La valeur finale de N est égale à la plus petite valeur de N telle que 2 N > 1000.

Autre exemple : dans l'algorithme d'Euclide, on ne sait pas combien de divisions euclidiennes seront nécessaires pour le calcul du PGCD.

L'instruction : effectuer la division euclidienne du diviseur par le reste de la division euclidienne précédente doit être répétée tant que le reste obtenu est non nul.

Exercices

Ecrire l'algorithme d'Euclide en langage naturel.

Voir la correction

Ecrire l'algorithme d'Euclide avec Algobox.

Voir la correction