Les structures itératives

Le principes des structures itératives est d'effectuer un bloc d'instructions plusieurs fois. Il existe deux types de structures :

  • la boucle for qui permet de faire un travail un nombre de fois connu avant le début de la boucle ;
  • la boucle while qui permet faire un travail tant qu'une certaine condition est vérifiée.

Ces répétitions ne sont pas identiques : à chaque répétition, l'état du programme évolue, notamment les valeurs des variables.

Boucle for

La syntaxe de la boucle for est la suivante :

for i in range(a,b):
   <bloc d'instructions>

Le bloc d'instructions est exécuté plusieurs fois.

La première fois la variable i vaut a, la seconde fois i vaut a+1, etc. La dernière fois la variable i vaut b-1 (retenez que la valeur b est exclue). On peut utiliser cette valeur dans le bloc d'instructions... ou pas !

Exemple : affichage répété

Dans cet exemple, on affiche 10 fois le même texte, sans rien modifier.

In [1]:
for i in range(0,10):
    print("Bonjour tout le monde !")
Bonjour tout le monde !
Bonjour tout le monde !
Bonjour tout le monde !
Bonjour tout le monde !
Bonjour tout le monde !
Bonjour tout le monde !
Bonjour tout le monde !
Bonjour tout le monde !
Bonjour tout le monde !
Bonjour tout le monde !

Mais on peut aussi utiliser la valeur de i, par exemple pour l'afficher.

In [2]:
for i in range(0,10):
    print(i, "- Bonjour tout le monde !")
0 - Bonjour tout le monde !
1 - Bonjour tout le monde !
2 - Bonjour tout le monde !
3 - Bonjour tout le monde !
4 - Bonjour tout le monde !
5 - Bonjour tout le monde !
6 - Bonjour tout le monde !
7 - Bonjour tout le monde !
8 - Bonjour tout le monde !
9 - Bonjour tout le monde !

Exemple : calcul de la somme des n premiers entiers.

La boucle suivante permet de calculer la somme des entiers entre 1 et 10.

In [3]:
s = 0
for i in range(1,11):
    s = s + i
s
Out[3]:
55

On a utilisé ici toute la puissance des boucles. On initialise d'abord une variable s avec la valeur 0. Elle est destinée à contenir la somme des entiers.

Puis on utilise une boucle : les valeurs successives de i sont ajoutées à la variable s. À la sortie de la boucle, s va donc contenir la valeur demandée.

Pour illustrer ce comportement, demandons l'affichage de i et de s au début de l'exécution de la boucle.

In [4]:
s = 0
for i in range(1,11):
    print('i vaut ', i, 'et s vaut ',s)
    s = s + i
    
print('À la sortie de la boucle, i vaut ', i, 'et s vaut ',s)
i vaut  1 et s vaut  0
i vaut  2 et s vaut  1
i vaut  3 et s vaut  3
i vaut  4 et s vaut  6
i vaut  5 et s vaut  10
i vaut  6 et s vaut  15
i vaut  7 et s vaut  21
i vaut  8 et s vaut  28
i vaut  9 et s vaut  36
i vaut  10 et s vaut  45
À la sortie de la boucle, i vaut  10 et s vaut  55

Exercices

  1. Écrire une fonction somme_entiers(n) qui renvoie la somme des entiers entre 1 et n.
  2. Écrire une fonction factorielle(n) qui renvoie la factorielle de l'entier n.
  3. Écrire une fonction Fibonacci(n) qui renvoie le $n$--ième terme de la suite de Fibonacci.
  4. Écrire une fonction arithmetico_geometrique(a, b, n) qui renvoie le terme d'ordre $n$ des suites $u$ et $v$ définies par :
$$ u_0 = \min(a,b), \qquad v_0 = \max(a,b)$$$$\forall n, \quad \quad u_{n+1} = \sqrt{u_n v_n} \quad v_{n+1}= \frac{u_n + v_n}{2}$$
In [5]:
def somme_entiers(n):
    s=0
    for i in range(1, n+1):
        s = s + i
    return(s)

somme_entiers(100)
Out[5]:
5050
In [6]:
def factorielle(n):
    f = 1
    for i in range(1, n+1):
        f = f*i
    return(f)

factorielle(0)
Out[6]:
1
In [9]:
def Fibonacci(n):
    if n<=1:
        return n
    else:
        a, b = 0, 1
        for i in range(0, n):
            a, b = b, a + b
        return(b)

Fibonacci(100)
Out[9]:
573147844013817084101

Boucle while

La boucle while est plus générale et plus puissante que la boucle for. Sa syntaxe est la suivante :

while <condition>:
    <bloc d'instructions>

Le <bloc d'instructions> est exécuté tant que la <condition> est vérifiée. Il est donc essentiel que la valeur de la condition soit modifiée au cours de l'exécution.

In [10]:
def reste(a,b):
    """ Renvoie le reste de de la division euclidienne de a par b"""
    while a >=b:
        a = a -b
    return a
In [11]:
reste(1907, 7)
Out[11]:
3
In [12]:
reste(190.7, 7)
Out[12]:
1.6999999999999886

Exemple

On cherche à trouver le plus petit entier $n$ tel que la somme des entiers $S_n = \sum_{k=0}^n k^{10}$ soit supérieure à 10000.

Pour cela, on peut utiliser une boucle while qui calcule cette somme tant que la condition précédente n'est pas vérifiée. Le programme à l'allure suivante.

In [13]:
s = 0
i = 0
while not(s>=100):
    i = i + 1
    s = s + i
print("La valeur de i trouvée est",i)
La valeur de i trouvée est 14

Concrètement, au début de la boucle la condition n'est pas vérifiée, donc le bloc d'instructions est exécuté : i est incrémenté d'une unité puis s est incrémenté de la valeur de i.

Ensuite on revient au début de la boucle : la condition est toujours vérifiée, donc le bloc d'instruction est exécuté une seconde fois (avec les valeurs actualisées de i et s, c'est-à-dire i=1 et s=1), etc.

À un moment donné, la valeur de s va dépasser 100. Comment le sait-on ? Par une étude mathématique de la suite $(S_n)$ on prouve qu'elle tend vers $+\infty$. Ainsi il est certain que la boucle s'arrête un jour.

Plusieurs remarques :

  • contrairement à la boucle for, ici il faut penser à incrémenter la variable i à la main ;
  • mais attention, la condition n'est pas sur i ! Elle est sur s!
  • très souvent la condition naturelle à laquelle on pense est la condition d'arrêt alors que while s'utilise avec une condition pour continuer l'éxecution. C'est pourquoi, personnellement, j'utilise souvent la forme while not(...): comme ci-dessus.

Boucles inutiles ou infinie

Le grand risque des boucles while est que la <condition> est toujours vérifiée, auquel cas la boucle est infini : le programme ne s'arrête jamais.

Il arrive aussi, mais c'est moins gênant, que la <condition> ne soit jamais vérifiée et donc que le <bloc d'instructions> ne soit pas exécuté.

Que se passe-t-il dans le cas suivant ?

a = 1
while a>=0:
    a = a/2

Et dans celui-ci ?

a = 1
while a>0:
   a = a/2

Et ici ?

a = 1
while a>1:
   a = a/2

Exemple : calcul de $\pi$ à une précision donnée

D'après le cours de math, on sait que la suite $$ u_n = \sum_{k=0}^n \frac{4(-1)^k}{2k+1}$$ converge vers $\pi$. Comment utiliser cette suite pour calculer $\pi$ avec un nombre de décimale $N$ donnée ?

Il faut donc calculer les termes de la suite $u_n$ jusqu'à ce que $|u_n - \pi|$ soit inférieur à $10^{-N}$... sans connaître $\pi$ !

Pour cela on a besoin d'un encadrement de $|u_n - \pi|$. Heureusement le cours de math en donne un : $$ \forall n \in N, \quad \quad |u_n - \pi| \leq \frac{16}{2n+3}$$ Ainsi, pour que $|u_n - \pi|$ soit inférieur à $10^{-N}$, il suffit que $\frac{16}{2n+3}$ le soit. Cela nous donne une condition commode pour écrire une programme.

In [14]:
def pi_Leibniz(N):
    '''Calcul de pi avec la formule de Leibniz, à la précision 10**(-N)'''
    
    p = 4
    n = 0
    while 16/(2*n+3) > 10**(-N):
        n = n + 1
        p = p + 4*((-1)**n)/(2*n+1)
        
    return n, p

pi_Leibniz(5)
Out[14]:
(799999, 3.1415914035897172)

Le problème informatique ici posée est celui de la terminaison d'un programme. On cherche à savoir si le programme s'arrête un jour.

Exercices

  1. Écrire une fonction partie_entiere(x) qui renvoie la partie entière du flottant x. Attention : le signe de x est quelconque.
  2. Écrire une fonction double_six() qui tire deux nombres au hasard entre 1 et 6, qui s'arrête quand elle obtient un double-six et qui renvoie le nombre de tirages qu'il a été nécessaire d'effectuer.
  3. Écrire une fonction premier(n) qui renvoie True si n est un nombre premier et False sinon.
In [15]:
def partie_entiere(x):
    i = 0
    if x>=0:
        while i<=x:
            i = i+1
        return(i-1)
    else:
        while i>x:
            i = i-1
        return(i)
In [16]:
partie_entiere(-45.76)
Out[16]:
-46
In [17]:
from math import *
floor(-45.76)
Out[17]:
-46
In [18]:
import random as rd
def doublesix():
    a = rd.randint(1,6)
    b = rd.randint(1,6)
    n = 1
    while not(a==6 and b==6):
        a = rd.randint(1,6)
        b = rd.randint(1,6)   
        n = n + 1
    return(n)

doublesix()
Out[18]:
28
In [19]:
doublesix() + doublesix()
Out[19]:
92
In [20]:
from math import *
def premier(n):
    premier = True
    for d in range(2, int(sqrt(n)) + 1):
        if n%d == 0:
            premier = False
    
    return premier

premier(1567)
Out[20]:
True

La même chose avec une boucle while

In [21]:
from math import *
def premier(n):
    d = 2
    while d<=sqrt(n):
        if n%d == 0:
            return False
        d = d + 1
    return True

premier(1567)
Out[21]:
True

Savoir-faire

  • D'abord identifier la condition de la boucle. Il est souvent plus facile de trouver la condition de sortie et de la nier ;
  • On écrit le corps de la boucle en vérifiant que la condition de sortie sera bien modifiée au cours de l'éxecution ;
  • on prévoit l'initialisation des variables avant l'entrée dans la boucle ;
  • enfin on procède au traitement à la sortie de la boucle.