Lesson 03-07: Accumulator Algorithms¶

An Example of an Accumulator Algorithm¶

Accumulator comes from the word accumulate, which means “gradually gather or acquire”. In programming, we use accumulator algorithms for the same purpose. For example, if we wanted to use loops to add up all positive integers up to 10, how would we do that?

sum = 0

for num in range(1,21):

    sum = sum + num

​

print("The sum is {}".format(sum))

​

The sum is 210

(0307_ex_1)

Here is that same code, except with added print statements to detail the process:

print("# initialize the sum at zero")

sum = 0

print("# running a for loop from 1 to 11, which will end at 10")

for num in range(1,11):

    print("# adding {} to {}, resulting in {}".format(num,sum,num+sum))

    sum = sum + num

    print("# saved result {} in our running total (sum)".format(sum))

​

print("The sum is {}".format(sum))

​

# initialize the sum at zero
# running a for loop from 1 to 11, which will end at 10
# adding 1 to 0, resulting in 1
# saved result 1 in our running total (sum)
# adding 2 to 1, resulting in 3
# saved result 3 in our running total (sum)
# adding 3 to 3, resulting in 6
# saved result 6 in our running total (sum)
# adding 4 to 6, resulting in 10
# saved result 10 in our running total (sum)
# adding 5 to 10, resulting in 15
# saved result 15 in our running total (sum)
# adding 6 to 15, resulting in 21
# saved result 21 in our running total (sum)
# adding 7 to 21, resulting in 28
# saved result 28 in our running total (sum)
# adding 8 to 28, resulting in 36
# saved result 36 in our running total (sum)
# adding 9 to 36, resulting in 45
# saved result 45 in our running total (sum)
# adding 10 to 45, resulting in 55
# saved result 55 in our running total (sum)
The sum is 55

(0307_ex_2)

Breaking Down the Accumulator Algorithm¶

The accumulator algorithm can be broken down into three parts:

1. Variable Initialization - You will have to have a variable that keeps track of your running total. This variable has to be initialized outside the loop. If you initialize it inside the loop, you will be repeatedly setting it to 0.
2. The Iterator - You need to figure out what iterator (in these cases, a range) will work best for your loop. Need to look at all the even numbers between 2 and 100? Better use a range(2,101,2). Later on, we’ll learn how to iterate over strings and lists as well.
3. The Update Statement - Since this is an accumulator algorithm, you should probably be accumulating something! This statement is for updating your running total with the new total. This doesn’t have to happen every time the loop runs, for example, if it’s inside of an if statement.

Let’s do an example: Let’s get the product (multiplication) all the numbers that end in “4” from 1 to 100.

We start with our variable initialization - I’m gonna call mine total and set it to 1. I don’t want to set it to zero because I know I’m going to be multiplying, and if I multiply anything by zero, it will always be zero!

1

total = 1

Next, I have to think about what I want to look at - in this case, what numbers do I need to look at? I could look at every number between 1 and 100, and that would be a waste - but I’m going to do it anyway to illustrate a point. Our range will therefore be range(1,101), since we want to include 100.

1
2

total = 1
for n in range(1,101):

Next is the update statement. I know my update statement is multiplication, and that statement would look like total = total * num. However, I only want to do that when the number ends in 4. How do we know if a number ends in 4? Well, it’s a bit tricky, but we can do this:

n % 10 == 4

This will take the remainder of dividing the number by 10, which drops everything except for the last digit 10, 100, 100, etc are all divisible by 10, so they all go away). This boolean expression will tell us if a number ends in 4 or not.

1
2
3
4

total = 1
for n in range(1,101):
    if n % 10 == 4:
        total = total * num

Finally, I want to make sure I’m correct, so I print out the number and run it!.

total = 1

for n in range(1,101):

    if n % 10 == 4:

        total = total * n

​

print("The total is {}".format(total))

​

The total is 4060162871525376

(0307_ex_3)

Although I don’t know what the actual answer is, so I will just punch the following into wolframalpha:

4 * 14 * 24 * 34 * 44 * 54 * 64 * 74 * 84 * 94

And I get 4060162871525376 as my answer. It matches!

What I did was the inefficient way as well - a clever programmer may have figured out that I could simply make a better range and come to the same conclusion:

total = 1

for n in range(4,101,10):

    total = total * n

​

print("The total is {}".format(total))

​

The total is 4060162871525376

(0307_ex_4)

(This code will loop 10 times, whereas the other loops 100 times)

Checks For Understanding¶

#write solution here

​

#write solution here

​

#write solution here

​