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 :

resultat = 1

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

resultat

5040

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

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) : resultat qui accumule progressivement des valeurs par produit, somme, …

Exercices#

  • Observez les cellules suivantes et devinez la valeur finale de la variable c; puis exécutez 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

---------------------------------------------------------------------------
ModuleNotFoundError                       Traceback (most recent call last)
Cell In[20], line 3
      1 import sys
      2 sys.path.append('..')
----> 3 from Exercices.entraîneur import entraîneur
      4 entraîneur

File /builds/IntroductionProgrammationPython/introductionprogrammationpython.pages.centralesupelec.fr/Sources/Boucles/../Exercices/entraîneur.py:3
      1 import glob
      2 from ipywidgets import interactive         # type: ignore
----> 3 from jupylates.jupylates import Exerciser  # type: ignore
      4 from IPython.display import display        # type: ignore
      7 thèmes = {
      8     'Fonctions': '../Exercices/fonctions/*.md',
      9     'Conditions': '../Exercices/conditions/*.md',
   (...)
     13     'Listes': '../Exercices/listes/*.md'
     14 }

ModuleNotFoundError: No module named 'jupylates'

Retourner à l’index

Contenu