Structures itératives

Le principe des structures itératives (répétitives) est de répéter plusieurs fois (en boucle) un ensemble d’instructions.

On distingue deux principaux types de boucles : bornées (for) dont le nombre d’itérations (de tours) est déterminé ou non bornées (while) dont l’arrêt dépend d’une condition, comme pour la structure alternative (if).

Programme exemple

Le programme suivant fait le travail d’une caisse enregistreuse : il cumule les prix des articles, jusqu’à ce qu’il n’y en ait plus. Le programme affiche alors le prix total.

total = 0
prix = input("Prix : ")
while prix != "": #tant que l’utilisateur a saisi un prix
    total = total + int(prix)
    prix = input("Prix : ")

print("Total : " + str(total))

Organigramme exemple

Syntaxe

instructions avant
n = …
for i in range(n): #faire n fois - i vaut 0, puis 1… jusqu’à n - 1
    instructions répétées
instructions après

• Comme pour la structure alternative, le code qui est répété doit être indenté.
• Par convention, la variable qui sert à contrôler ces boucles s’appelle i pour indice ; Le nom de la variable n signifie ici “nombre de tours”.
• La variable i est initialisée à 0 puis incrémentée (augmentée) automatiquement à la fin de chaque tour, pour atteindre la valeur n - 1.

Organigramme

Exemple

for i in range(10):        #faire 10 fois
    print("i = " + str(i)) #remarquer que i commence à 0 et s’arrête à 9

Généralisation

C’est l’instruction range qui génère les valeurs que i va prendre. Cette fonction prend normalement trois paramètres :

• à partir de quelle valeur de i (0 par défaut) ;
• jusqu’à quelle valeur de i (exclue) ;
• le pas, c’est-à-dire de combien i est augmenté à la fin de chaque tour (1 par défaut).

Ainsi, la syntaxe complète est :

n = int(input("Saisir le nombre de tours : "))
for i in range (0, n, 1): #identique à range(n)
    print(str(i))

Ce qui permet des boucles qui avancent de 2 en 2 (par exemple) :

s = int(input("Début : ")) #s, pour start
e = int(input("Fin : "))   #e, pour end
for i in range (s, e, 2):  #il y aura (e - s) // 2 tours
    print(str(i))

Ou des boucles qui comptent à rebours :

n = 10
for i in range (n, -1, -1):
    print(str(i))

Syntaxe

instructions avant
initialisation
while (condition pour continuer):
    instructions répétées
    passage au suivant
traitement des cas de sortie
instructions après

• Comme pour la structure alternative, le code qui est répété doit être indenté.
• Par rapport au for, il faut coder explicitement les instructions suivantes :
  • l’initialisation des variables utilisées dans la condition ;
  • le passage à l’élément suivant (incrémentation ou autre).
• La condition pour continuer est souvent une expression booléenne qui combine plusieurs conditions (avec and ou or). Plusieurs cas de sortie sont alors possibles, et il faut les traiter (souvent avec une alternative if).

Organigramme

Exemple

Le programme suivant tire un nombre aléatoire au hasard entre 1 et 10 que l’utilisateur doit deviner en moins de 5 essais (soit 50% de chances de gagner) :

from random import randint #nécessaire pour utiliser randint
secret = randint(1, 10)     #tirage d’un nombre aléatoire entre 1 et 10
found = False               #initialisation
i = 0                       #initialisation
while i < 5 and not found:  #tant qu’il reste des essais et non trouvé
    nombre = int(input("Saisir un nombre : "))
    if nombre == secret:
        found = True
    else:
        print("Ce n’est pas " + str(nombre))
    i = i + 1               #passage au suivant (incrémentation)
if found:                   #traitement des cas de sortie
    print("Gagné : c’était bien " + str(secret) + " !")
else:
    print("Perdu : nombre d’essais épuisés.")

Remplacer “for” par “while”

Une boucle for peut toujours être écrite avec un while mais ce n’est pas réciproque : la structure itérative while est universelle, tandis-que dans le cas du for, il est nécessaire que le nombre d’itérations soit déterminé.

Ainsi, l’itérative for suivante :

for i in range(n):
    …

peut s’écrire :

i = 0           #automatique dans le cas du for
while i < n:
    …
    i = i + 1   #automatique dans le cas du for

Préférer un for lorsque c’est possible : cela élimine le risque de boucle infinie et il y a moins de risques d’erreurs de syntaxe.

Instructions “break” et “continue”

Cette syntaxe est déconseillée, mais de nombreux programmeurs utilisent l’instruction break pour sortir d’une boucle :

instructions avant
while (True): #faire indéfiniment
    …
    if condition de sortie:
        break #sort de la boucle
    …
instructions après

Le break est aussi utilisé dans une boucle for, pour en sortir avant le nombre de tours prévu.

L’instruction continue est similaire au break, mais elle termine seulement le tour en cours, sans mettre fin aux itérations.

Compteur

Cet algorithme sert à dénombrer le nombre de fois qu’une condition est vérifiée.

compteur = 0
for i in range(n):
    if condition:
        compteur = compteur + 1

Cumul

Très similaire au compteur, mais au lieu d’ajouter 1, il cumule des valeurs. Ces deux itératives sont souvent combinées ; exemple : pour calculer une moyenne, il faut compter le nombre de notes et les additionner.

cumul = 0
for i in range(n):
    if condition:
        cumul = cumul + valeur

Recherche

Bien que le for associé au break soit possible pour une recherche, le while associé à un booléen (found par exemple) est souvent préférable.

while i < n and not found:
    if condition:
        found = True
    i = i + 1
if found:
    …

Les structures alternatives et itératives peuvent être imbriquées les unes dans les autres.

Exemple

Le programme suivant dessine un damier :

for i in range(10):
    for j in range(10): #il faut une deuxième variable indice
        print("⬛" if i%2==0 and j%2==0 or i%2==1 and j%2==1 else "⬜", end="")
            #end="" évite le retour à la ligne à la fin ("\n" par défaut)
    print("")

Deux boucles imbriquées permettent ainsi de traiter des données en deux dimensions - les pixels d’une image (lignes, colonnes) par exemple.

Algorigramme

Terminaison

Par définition, la boucle for se termine.

Dans le cas de la boucle while, il y a un risque de boucle infinie, si la condition de sortie n’est jamais vérifiée. Une erreur classique est l’oubli (ou l’exécution non systématique) de l’instruction d’incrémentation i = i + 1.

Une technique pour éviter le risque de boucle infinie est de déterminer un variant de boucle pour prouver la terminaison. Le variant est une expression qui tend vers zéro, c’est-à-dire dont la valeur diminue à chaque tour.

Un cas typique est de prendre comme variant n - i, ou n est le nombre maximum de tours et i l’indice du tour actuel. Si i augmente systématiquement à chaque tour , n - i tend bien vers zéro, et la boucle se termine.

Preuve de correction

La preuve de correction (partielle) passe par la définition d’un invariant, c’est-à-dire une condition qui est vérifiée à chaque itération : exemples :

• pour le cumul, l’invariant est : “cumul est égal à la somme des éléments de 0 à i" ;
• pour la recherche, l’invariant est : “la valeur cherchée n’est pas entre 0 et i”.

Étant donné que l’invariant doit être vérifié à chaque itérative, il est souvent nécessaire d’initialiser les variables sur lequel il porte (i ou found par exemple) avant le début de la boucle. De même, après une itérative qui aurait plusieurs cas de sortie (il y en a deux pour la recherche : i ≥ n ou found == True), une instruction conditionnelle est souvent nécessaire pour les distinguer.

Une fois l’invariant déterminé, il faut s’attacher à démontrer qu’il est vérifié à chaque itération. Exemple pour la recherche :

• à l’initialisation, i = 0, donc la valeur cherchée ne peut avoir été trouvée ;
• à chaque itération, la valeur cherchée ne peut être entre 0 et i - 1, sinon, la condition aurait été satisfaite à l’itération précédente et found serait True.

Remarque : l’invariant serait plus formellement exprimé par une expression mathématique ; exemple pour la recherche : found ∨ rech ∉ valeurs⟦0..i-1⟧.