Compteurs et accumulateurs

Contenu

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 :

resultat = 1

resultat = resultat * 2
resultat = resultat * 3
resultat = resultat * 4
resultat = resultat * 5
resultat = resultat * 6
resultat = resultat * 7

resultat

La variable resultat sert d” accumulateur (accumulator) : 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

resultat = 1;
for i in range(2, n+1):
    resultat = resultat * i

resultat

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) : resultat 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

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

somme(5)

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

Retourner à l’index