Structures répétitives

1Boucles bornees et non bornees

Repeter un traitement est le second mecanisme de controle. Python offre deux boucles de natures differentes, et savoir laquelle choisir est deja la moitie du travail.

La fonction range

range(n)            # 0, 1, ..., n-1          (n valeurs)
range(a, b)         # a, a+1, ..., b-1        (b-a valeurs si b > a)
range(a, b, p)      # a, a+p, a+2p, ...       tant que l'on reste avant b

La borne superieure est toujours exclue. Le pas p peut etre negatif.

list(range(5))            # [0, 1, 2, 3, 4]
list(range(2, 9, 3))      # [2, 5, 8]
list(range(10, 0, -2))    # [10, 8, 6, 4, 2]
list(range(5, 5))         # []          borne atteinte : aucun tour
list(range(5, 0))         # []          pas de tour, et surtout pas d'erreur

La boucle for

for i in range(1, 6):
    print(i, i*i)

for c in "MPSI":            # une chaine est iterable
    print(c)

for x in [3, 1, 4, 1, 5]:   # une liste aussi
    print(x)

Trois motifs de parcours a connaitre par coeur :

t = [10, 20, 30]

for x in t:                      # par ELEMENT : quand l'indice est inutile
    print(x)

for i in range(len(t)):          # par INDICE : quand on doit modifier t
    t[i] = t[i] * 2

for i, x in enumerate(t):        # les DEUX a la fois
    print(f"t[{i}] = {x}")

La boucle while

n = 100
compteur = 0
while n > 1:                 # condition testee AVANT chaque tour
    n = n // 2
    compteur += 1
print(compteur)              # 6 : nombre de divisions par 2 pour atteindre 1

Le squelette d'une boucle while correcte comporte toujours trois elements :

1. une initialisation avant la boucle ;
2. une condition portant sur les variables initialisees ;
3. une progression dans le corps, qui fait avancer vers l'arret.

i = 0
while i < 10:
    print(i)        # i n'est jamais modifie : boucle infinie

2Motifs algorithmiques et controle de boucle

Accumulation

Le motif le plus frequent : une variable est initialisee a l'element neutre, puis enrichie a chaque tour.

def somme_carres(n):
    """Somme des carres des entiers de 1 a n."""
    s = 0                      # element neutre de l'addition
    for k in range(1, n+1):
        s += k*k
    return s

def factorielle(n):
    """n! pour n >= 0."""
    p = 1                      # element neutre de la multiplication
    for k in range(2, n+1):
        p *= k
    return p

assert somme_carres(3) == 14
assert factorielle(0) == 1 and factorielle(5) == 120

Verification : \(\sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}\), soit 14 pour \(n=3\).

Recherche d'un extremum

def maximum(t):
    """Plus grand element de la liste non vide t, sans utiliser max."""
    m = t[0]                   # initialiser avec un element de la liste !
    for x in t[1:]:
        if x > m:
            m = x
    return m

def indice_du_max(t):
    """Indice du premier maximum de la liste non vide t."""
    imax = 0
    for i in range(1, len(t)):
        if t[i] > t[imax]:
            imax = i
    return imax

Comptage et test d'existence

def compte(t, v):
    """Nombre d'occurrences de v dans t."""
    c = 0
    for x in t:
        if x == v:
            c += 1
    return c

def appartient(t, v):
    """v figure-t-il dans t ? Sortie anticipee."""
    for x in t:
        if x == v:
            return True        # inutile de continuer
    return False               # atteint seulement si la boucle est finie

break, continue et la clause else

for k in range(2, 20):
    if k % 3 == 0:
        continue          # on saute les multiples de 3
    if k > 10:
        break             # on arrete completement
    print(k, end=" ")     # 2 4 5 7 8 10

def est_premier(n):
    """n >= 2 est-il premier ?"""
    if n < 2:
        return False
    for d in range(2, int(n**0.5) + 1):
        if n % d == 0:
            return False       # diviseur trouve
    return True                # aucun diviseur : n est premier

Boucles imbriquees

for i in range(1, 4):
    for j in range(1, 4):
        print(f"{i*j:3}", end="")
    print()                # retour a la ligne apres chaque ligne du tableau

  1  2  3
  2  4  6
  3  6  9

Le corps interne est execute \(3 \times 3 = 9\) fois. En general, deux boucles imbriquees de \(n\) tours chacune donnent \(n^2\) executions : c'est l'origine des complexites quadratiques des tris elementaires (chapitre 12).

# triangle de Pascal, motif de boucle "triangulaire"
n = 5
for i in range(n):
    for j in range(i + 1):        # borne dependant de i
        print("*", end="")
    print()

Ici le nombre total d'executions vaut \(1+2+\cdots+n = \frac{n(n+1)}{2}\), toujours quadratique en \(n\), mais avec une constante deux fois plus petite.

3Variant, invariant et trace interactive

Une boucle while n'est pas evidemment correcte : il faut prouver qu'elle s'arrete et qu'elle calcule ce qu'on veut. Ces deux notions, developpees au chapitre 15, s'introduisent naturellement ici.

def division(a, b):
    """Quotient et reste de la division euclidienne de a >= 0 par b > 0."""
    q, r = 0, a
    while r >= b:
        r = r - b
        q = q + 1
    return q, r