Compteurs et accumulateurs

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

5040

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

3628800

Nous avons donc vu deux techniques classiques de boucles :

  • L’utilisation d’un compteur (counter) : i qui parcours les valeurs de … à … par pas de …

  • L’utilisation d’un accumulateur (accumulator) : 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

15

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

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

15

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 120 :

somme(5)

15

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

somme(5) == 15

True

somme(63) == 2016

True

somme(100) == 5050

True

somme(1) == 1

True

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 sys
sys.path.append('..')
from Exercices.entraîneur import entraîneur
entraîneur
Contenu