Counters and accumulators

Counters and accumulators#

We want to calculate the factorial of \(7\): \(7!=1 \cdot 2 \cdot 3 \cdots 7\)

This can be written as follows:

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

The variable résultat serves as an accumulator: we accumulate the integers \(1, 2, 3, ...\) by product and its successive values are:

  • \(1\)

  • \(1\cdot2\)

  • \(1\cdot2\cdot3\)

  • …

  • \(1\cdot2\cdot3\cdot4\cdot5\cdot6\cdot7\)

Problems:

  • This code smells: there are many repetitions!

  • And what if we want to calculate \(10!\) or \(100!\)?

Repeated instructions? That suggests a loop. Counting from 1 to 7? That’s a

mission for the for loop!

n = 10

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

résultat

3628800

So, we have seen two classic loop techniques:

  • The use of a compteur (counter): i which iterates through the values from … to … in steps of …

  • The use of an accumulateur (accumulator): résultat which progressively accumulates values by product, sum, …

Exercises#

  • Observe the two following cells and guess the final value of the variable c; then run them to check.

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

c

15

Between c and i, which variable serves as a counter? As an accumulator?

BEGIN SOLUTION

  • i serves as a counter

  • c serves as an accumulator

END SOLUTION

  • Copy the loop below, then modify the stop condition so that the variable c is equal to \(36\) after execution:

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

c   # doit valoir 36

36

The following cell contains automated tests; we will come back to it in more

detail later; for the moment, you can just run the cell and check

that there is no error message.

assert( c == 36 )

  • Inspired by the examples above, write a program below that calculates the value of the sum of integers from 1 to n: 1 + 2 + … + n, using a variable s as an accumulator:

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 )

  • Rewrite your program to put it in the form of a function that calculates the sum of integers from 1 to \(n\):

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

The next call to your function should return 120:

somme(5)

15

Check your function using the following tests (they should all display true):

somme(5) == 15

True

somme(63) == 2016

True

somme(100) == 5050

True

somme(1) == 1

True

Automated tests:

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

Additional exercises#

To practice for loops, counters, and accumulators, select

the “07 - For Loops” theme.

import sys
sys.path.append('..')
from Exercices.entraîneur import entraîneur
entraîneur
Contents