Compteurs et accumulateurs

On souhaite calculer la factorielle de 7 : $7!=1 \cdot 2 \cdot 3 \cdots 7$

Cela peut s’écrire de la façon suivante :

résultat = 1

résultat = résultat * 2
résultat = résultat * 3
résultat = résultat * 4
résultat = résultat * 5
résultat = résultat * 6
résultat = résultat * 7

résultat

La variable résultat sert d’accumulateur : on y accumule les entiers $1, 2, 3, ...$ par produit et elle vaut successivement :

• 1

• $1\cdot2$

• $1\cdot2\cdot3$

• ...

• $1\cdot2\cdot3\cdot4\cdot5\cdot6\cdot7$

Problèmes :

• Ce code sent mauvais : il y a beaucoup de répétitions!

• Et si on veut calculer $10!$ ou $100!$ ?

Des instructions répétées ? Cela suggère une boucle. On compte de 1 à 7 ? C’est une mission pour la boucle for!

n = 10

résultat = 1
for i in range(2, n + 1):
    résultat = résultat * i

résultat

Nous avons donc vu deux techniques classiques de boucles :

• L’utilisation d’un compteur : i qui parcours les valeurs de ... à ... par pas de ...

• L’utilisation d’un accumulateur : résultat qui accumule progressivement des valeurs par produit, somme, ...

Exercices¶

• Observez les deux cellules suivantes et devinez la valeur finale de la variable c; puis exécutez les pour vérifier.

c = 0
for i in range(6):
    c = i + c

c

Entre c et i quelle variable sert de compteur? d’accumulateur?

BEGIN SOLUTION

• i sert de compteur

• c sert d’accumulateur

END SOLUTION

• Recopiez la boucle ci-dessous puis modifiez la condition d’arrêt pour que la variable c soit égale à 36 après l’exécution :

c = 0
### BEGIN SOLUTION
for i in range(9):
    ### END SOLUTION
    c = c + i

c  # doit valoir 36

La cellule suivante contient des tests automatisés ; nous reviendrons dessus plus en détails par la suite; pour le moment, vous pouvez juste exécuter la cellule et vérifier qu’il n’y a pas de message d’erreur.

assert c == 36

• En vous inspirant des exemples ci-dessus, écrivez ci-dessous un programme qui calcule la valeur de la somme des entiers de 1 à n : 1 + 2 + ... + n, en utilisant une variable s comme accumulateur :

n = 5

### BEGIN SOLUTION
s = 0
for i in range(n + 1):
    s = s + i
### END SOLUTION

s  # 15 pour n = 5

assert s == 15

• Reprendre votre programme pour le mettre sous la forme d’une fonction qui calcule la somme des entiers de 1 à $n$ :

def somme(n):
    ### BEGIN SOLUTION
    s = 0
    for i in range(n + 1):
        s = s + i
    ### END SOLUTION
    return s

L’appel suivant à votre fonction devrait renvoyer 15 :

somme(5)

Vérifiez votre fonction grâce aux tests suivants (ils doivent tous afficher true) :

somme(5) == 15

somme(63) == 2016

somme(100) == 5050

somme(1) == 1

Tests automatisés :

assert somme(0) == 0
assert somme(1) == 1
assert somme(2) == 3
assert somme(3) == 6
assert somme(4) == 10
assert somme(5) == 15
### BEGIN HIDDEN TESTS
assert somme(100) == 5050
### END HIDDEN TESTS

Exercices supplémentaires¶

Pour vous entraîner aux boucles for, aux compteurs et aux accumulateurs, sélectionnez le thème “07 - Boucles For”.

import os

os.chdir("../exercices")
from entraîneur import entraîneur

entraîneur