In this lesson you will learn an important topic: algorithms with repetitions (a.k.a. loops). You will see how to solve problems creating algorithms with repetitions.
During the lesson you will see some examples.
The approximate time to complete this lesson is 20 minutes.
Transcription
Welcome back.
So far, we studied algorithms, conditionals relational and logical operators and multiple conditionals.
In this lesson, we are going to study another structure that is very helpful to solve problems using algorithms: repetitions (a.k.a. loops).
Let’s see the following problem: print the odd numbers that are greater than 10 and less than 1000.
In this case, we are first trying to draft some ideas on how we can solve this problem. But we are not just going to start writing the pseudo-code or the flow diagram. you will understand later why we are doing it like this.
So, let’s explore some ideas. First, we need to have the values from 10 to 1000 in a variable, one at a time. So, in this case, we cannot think about having a thousand variables, we just must do it using only one variable and having a different value at a time.
Once we have the values on the variable, then the solution is simple, because it’s like the previous problems that we already solved.
So, if we have a specific number, we can use a conditional to ask if the number is odd. In the case that the condition is true, then we print the number. The previous two steps we already know how to do it.
Algorithms with repetitions: pseudo-code
Let’s now see in a pseudo-code, how we can do that.
1- number = 10
2- increment number in 1
3- if number % 2 == 1 print number
4- if number<1000 go to step 2
First, we assign the value 10 to the variable number. Then we increment the number in one because the problem states that they are greater than 10. So, 10 is not greater than 10, therefore we must make sure that the first value that we analyze is 11.
Now the conditional if the reminder of the division of the number by 2 is equal to 1 then the number is odd. Then we print the number.
After that, we are going to use another condition, but this one is different. If the number is less than one thousand, then we are going to “jump back” to step two.
We didn’t see these types of examples before. If we go to step 2 from step 4 then step 3 will be repeated and that’s why we call this type of algorithm an algorithm with repetitions.
Notice that if the initial value of the number is 10 and we increment it in one every time.
Eventually, the condition of step 4 will not be true, and the algorithm will finish.
First, number equals 10, then we increment number in one (equals 11).
At step 4, when we “jump back” to step 2, we increment the number in 1 again and then it will be 12 and so on until equals 1000.
After that, at step four, the condition will be false, and the algorithm will finish. This assures us that the algorithm is finite, one of the characteristics that every algorithm has. If the algorithm is not finite (by definition is not an algorithm) then it will never finish. You will never have a solution to the problem.
Flow diagram for algorithms with repetitions
Let’s see how this will look in a flow diagram.
We first start and we state number equals 11. After that, we check the condition number<1000. If the condition is false we finish.
If the result of the condition is true, then we check another condition: “number%2==1”. If this condition is true, it means that the number is odd. Then we print the number and, increase number in one (number=number+1) and, less than 1000. Now we repeat the whole process.
As you can see in the flow diagram, if it’s true we will repeat all the instructions to check whether the number is odd or not. But, if it’s false, then we just finish.
In programming, we call this type of structures loops.
Algorithms with repetitions: loops with precondition and postcondition
We have two types of loops.
Loops with precondition like in the previous example.
while condition do
block of instructions
What the precondition means is that if the condition doesn’t hold at
the beginning the block of instruction will not be executed (not even once).
The other type of loop is called loop with postcondition.
repeat/do
block of instruction
while condition
As you can see, the block of instruction will always be executed at least one time and, after the first iteration (the first time the block of instruction is executed) we check if the condition holds or not.
That’s why it is called loop with postcondition.
Let’s see now how the algorithm will look like using the while loop structure.
On the left side, we can the first solution that we gave to our problem, in which we used a “go-to” statement. This is a kind of an old type of statement that we don’t use anymore in programming. Although it is valid to use it to design an algorithm.
On the right side, we use a while-loop (a loop with pre-condition). In this example, you can see at line 5 that we don’t have to explicitly state a go-to line 2, the while structure just gives us that functionality “out of the box”. So, we don’t have to explicitly state that it must “jump back” to line 2, but it will do it “out of the box”.
After a “jump back” to line 2, the condition will be checked again, if it holds the block of instructions will be executed again. So, this one is kind of a simplified version of the previous solutions that we created.
For-loop
There is also another type of loop: for-loop. It is a precondition loop. So, it will first check if the condition holds before it executes the block of instruction. But this structure allows us to give an initial value to a certain variable, to state the condition and to state the increment
in just one line as you can see below.
For (number = 11, number<1000, number++)
if number % 2 == 1 print number
End for
That’s the way that we specified when the repetitions must stop.
Find below the general way of specifying a for-loop. This “general way” is called syntaxis in a programming language. It is a kind of grammar rule of the languages that we usually speak. The main difference is that if we don’t write the code exactly following the syntaxis, the program won’t be executed by the computer.
For var=initial_value, condition, increment
Do block of instructions
End for
We must make sure that modifying “var” with “increment”, eventually, the condition won’t
hold, so the for loop will stop. Otherwise, we will have an infinite loop and we won’t solve the problem. And yes, it is always about solving a problem.
If you check the code above (the for-loop solution to our previous problem), you will see that initially, number equals 11. Then we increment number in 1 each time. If number equals 11 and we add 1 several times, eventually number will equal 1000 and the condition (number<1000) will not hold. Therefore, the for-loop will finish.
Within the for-loop, we just ask if the number is odd, and if it is odd, we print it.
Notice we didn’t write a “jump back” (go to) statement, the for-loop does it for us “out of the box”.
Algorithms with repetitions: for-loop and while-loop
Let’s now see both solutions: a while loop and a for loop. As you can see in the picture below, with the while-loop we need to initialize the variable before the while. That type of variable that we use to control how many iterations or repetitions the loop will have; we call it the control variable.
In the case of the while, the control variable must be initialized before the line of the while and, within the while, we must modify that variable to make sure that the while will finish eventually.
In the case of the for-loop, the control variable is declared and initialized in the same line of the for-loop, also the stop-condition is on the same line together with the increment.
Those are the two main loop structures that we have available in programming. For pre-condition loops, we have the while-loop and the for-loop. We can use both of them. As you can see it depends mostly on what you prefer but with both, you can achieve the same thing.
We can also use a different way of defining what is within the loops. In the examples below I used “while – end while” and “for – end for” to define what is within the loop. However, because it is pseudo-code you can use a different way. For instance, you can use brackets (see figure below) or whatever symbol you want. Just remember it must be clear that the symbols are there to specify what is within the loop.
Algorithms with repetitions: example of a basic algorithm for summing
Let’s see another example: print the sum of the odd numbers that are greater than 10 and less than 1000.
In this case, we are not just printing the odd numbers, we must print the sum of all the odd numbers.
Notice that we must go through all the numbers from 11 to 1000. Because of this, we can see the need for a loop (or repetitions). Apart from that, we need a variable that will hold the sum of all the numbers that will hold a certain condition: odd numbers
Our first step must be to initialize that variable to 0 because 0 is neutral for the sum. Whatever number we sum at the beginning, we need to make sure that doesn’t modify our previous number. So, for instance, if the first number is 1 and the second one is 2, then the sum must be 3. Because the variable is initialised to zero, when you sum 0+1+2 = 1+2 = 3. Therefore, initializing the variable to 0 doesn’t make a difference in the sum of all the numbers, which is what we need.
This is also considered a basic building block in programming. It is also known as a basic algorithm. You can read more about it here.
Now we have to think in the repetitions. We have to use a loop to go through the numbers from 11 to 1000. We already know how to do that. So, let’s write the pseudo-code.
pseudo-code
Let’s explain now the pseudo-code.
In line 1 we are initializing the variable we will use to store the sum. I already explained why it must be initialized to 0.
Then we write the for-loop to go through the numbers we have to check 11-1000. Also, with the increment number++ (the same as number=number+1), we guarantee that we check all numbers between 11 and 1000, one at a time.
Within the for-loop, we have a condition because we can only sum odd numbers. So, we first ask if the number is odd, if the result is true, then we sum. If the number is not odd, we don’t do anything.
After the for-loop, all we have to do is to print the value we calculated.
Notice that the variable sum will hold the value resulting from the sum of all odd numbers between 11 and 1000.
Recap
In a summary, in this lesson, we studied how useful can loops be when we are solving a certain type of problems.
Imagine that instead of those three lines that we used in the for loop, we need to have a thousand variables. That wouldn’t be practical. We cannot solve problems in that way.
So, when we need to repeat certain things several times, then we need to use loops as a way of solving the problem.
We have two types of loops. We also must be aware of this: we have loops with precondition and postconditions.
We use preconditions when we need our block of instructions to be executed only if the condition is meet and we use postcondition when we want our block of instructions to be executed at least one time and if the condition is met then it can repeat the block of instruction. if the condition does not hold after the first time the block of instructions is executed, then we finish.
By using loops, we can solve more complex problems and there is a wide variety of problems that we can solve using this structure.
