You will see looping in Computer Science called by many different names: repetition, iteration, and looping. What all of this really means is to repeat a set of statements until a certain condition is met.
It doesn't seem likely but many times beginning students will use looping structures where they want decisions and decisions where they want looping structures. Understanding the difference between the two is an important concept to grasp because you need to know which construct to you before you can solve particular problems.
The above depicts how the flow of control of the selection structure works. In the example if you are at then of the file then it is time to close the file. If you are not at the end of the file then control branches to the next statement following the close file statement.
As stated iteration (looping) is similar in that a boolean condition is used to control the flow of the program. The difference is that instead of executing a block of code if the condition is true, iteration executes the statements repeatedly until the condition becomes false:
In the above illustration a boolean check is made to see if the end of the file has been encountered. If the program is not at the end of the file the next line of the file is read. The process of checking for end of file and reading the next line will continue until the end of the file is found. At this point the loop exits and the statements following the loop are executed.
Like the if statement, looping structure rely on a boolean test condition to control the loop. One of the things that distinguishes the loops from each other is where the test condition occurs. One loop, the do-while loop has the test condition last where another loop, the while loop has the test condition first:
As you can see the major difference between the two loops is where the test condition occurs. With a bottom tested loop the code in the body of the loop will always execute at least one time. Remember, the code flows from top to bottom so the test condition is not checked until after the body of the loop has executed once.
New programmers tend to gravitate towards the do-while bottom tested loop. This is probably because using this loop avoids having to setup any preconditions to get the loop going. You should know though that using this type of loop should not be your first choice because it is like "leaping before you look". Think of it this way, would you add seasoning to something you are cooking before tasting it first?
Loop Classification
In C++ there are two types of loops:
Counted Loops
You employ counted loops when you know how many times you want something to repeat. For instance, output your name to the screen 10 times. Of course it is not always possible to know how many times you want the loop to run before hand. Consider reading lines from a file or counting the number of characters that appear in a string.
The counted loop in my mind is the simplest loop to learn in C++ because every statement needed to initialize, control, and update the loop appears on one line.
Indefinite loops
Indefinite loops are called indefinite because you can not determine how many iterations the loop will need to execute to perform the task at hand. Here is an example problem of an indefinite loop:
Generate random numbers until a prime number is produced
Because the numbers are being generated are random there is no way to tell how many numbers will need to be generated before a prime number is one of the numbers produced.
Indefinite loops can be further broken down into the following three categories
You will find that when you start writing loops that it is an easy thing to do to have a logic error in your code that will produce a loop that will never end. Loops have always been a source of errors in programs so it is important to understand how to write them correctly the first time. In a book written by Doug Cooper called Oh Pascal, the author defines a strategy for building loops correctly.
Included in this strategy is that loops consist of preconditions, actions the loop performs, post conditions, and a bounds and goal. We will look at all of these concepts as we move along but in order to write loops correctly the first time we need to get an understanding of what the bounds an goal are and how to identify them.
The Loop Bounds
In my opinion knowing what the bounds for your loop is and how to make your loop move towards that bounds is the most important thing to learn when writing loops. The bounds is what is needed to make your loops stop and since infinite loops are one the most common errors in programming, learning the bounds first is most important.
To understand the bounds consider the following problem:
Count all of the vowels that are present in a String
Understanding what the bounds is in this problem may not be entirely straight forward to you. Think about it in another way. You want to count all of the vowels until there is are no more characters left to examine. We could say then that the bounds would be that end of the String was encountered.
It should seem obvious that we need examine the first character, then the second, and so on until there are no more characters left to examine. We could say then that examining each character in order is moving us towards our bounds (the end of the string).
Loop Goal
We know that we need to examine each character in order until there are no more characters left which moves us towards the bounds and stops the loop from executing but what is the goal of the problem?
The goal of the problem is more obvious. It is to count the number of vowels that appear in the string.
So how would this loop be constructed? Let's consider some pseudo-code.
// Initialize variables A counter called count initialized to 0
A String called s initialized from the keyboard
A char called ch set to first character of s
while ch is not equal to end of string { if(ch is equal to a vowel) increment counter;
assign next char in s to ch // move towards bounds
}
It is important to note that this loop will execute until there are not more characters in the String. Assigning the next character in the string s to ch moves us towards the end of the string (the bounds). Without this statement ch never changes so the test condition will always remain the same.
Precondition / Post Condition
As for the post condition in this code there really isn't one. It is typical for loops to not have a post condition that needs to be taken care of. If the program was asking for an average then the post condition would be to test that the loop actually was entered. Otherwise you might have a divide by zero error.
Priming The Loop
Assigning the first character to the char ch is called priming the loop. This is needed to start the loop. Priming will be covered in a later section but you should know that many times you need to initialize a variable with data before the loop then get more data at the bottom of the loop. Without these two statements the bounds would never be reached.
Now that you have an idea on the mechanics or writing loops properly it is time to look the loops that are specific to the C++ programming language. In the following sections you will see:
The for loop is the best loop to start with because it tends to be the easiest loop to comprehend. The reason it is the most simple loop to learn is that all of the statements that make up the loop are located on the same line. This makes it easy to identify any missing components.
The for loop is a natural counting loop. You use this loop when you need to repeat a set of instructions a specific number of times. This could include printing your name to the screen 10 times or checking for all of the upper case characters in a string. You may be wondering how using a counted loop will help you count the uppercase characters in a string? The answer is that you can use the length method of the String to determine the number of characters. From that point you simply create a loop that counts from 0 up to the number of characters in the String.
The for loop is a test at the top loop and it has the following syntax:
The six components that make up the for loop are as follows
Notice that the initialization, Boolean test, and update expression are separated by a semicolon? Like statements in C++ these are necessary to terminate each individual section.
First Example
Earlier an example was discussed to use a for loop to count all of the upper case characters in a String. At this point let's take a look at some code that will do this:
In the initialization section notice that the variable i was created and set to 0. This variable is used for the counter to control the loop. In the test expression section the test checks to see if i is less than the length of the String. If the test is true the body of the loop executes. Finally, the update expression executes incrementing the variable i by one. This process continues until the variable i becomes equal to the number of characters in the string.
The flow of the for loop is depicted here:
This process continues until the bounds of the loop are met.
The bounds - The bounds of this loop is when i becomes equal to the number of characters in the String.
The Goal - The goal of the loop is to count the number of upper case characters in the String.
The Initialization Section
The initialization section is encountered first. It is the first clause that is part of the loop. This section will always be executed once at the time the loop in entered. It is typically used for variable creation to move the loop towards a bounds.
Variations
You are not limited to the creation of only one variable in the initialization section. You can initialize as many variables as you would like. You simply need to separate each variable declaration by comma:
It should also be noted that the variables all have to be of the same type. This means you cannot mix a double and an int for instance:
The Test Expression
The test expression happens right after the initialization section executes and subsequently after the update expression executes. If the test expression is true then the statements withing the loop body are executed. If the test expression is false the flow of the program continues after the end of the loop body.
The test expression is created just like you would create the test expression in an if statement. You use the relational operators to construct a Boolean test:
You can also use the logical operators to construct a compound test expression:
What you cannot do in the test expression is have multiple tests:
Update Expression
The update expression executes immediately after the loop body executes and just before the test expression. This section is designed to change the counter variable which will move the loop towards it's bounds:
Like the other components of the for loop you can have multiple test expressions. You simply separate them by a comma:
Counting Variations
Counting Down
You are not limited to counting up. You can count down also if you want to:
The following code shows how to print out a string in reverse order
One of the things that might not be clear about the above code is the initialization section:
int i = s.length() - 1;
We want to start outputting at the last character in the string. The length will give us the number of characters but this is one more than the last index. If there are 25 characters in the string the last index is 24. This is because we start counting a zero in Computer Science so, 0 - 24 is 25 characters.
Counting By Steps You can count by steps:
This loop executes 10 times because i is increased by 2 each time through the loop.
Counting Exponentially
You can also count exponentially if you want:
Example Code - Sum Of All Characters
Code Review
In the above example the variable i is initialized to 0. The loops bounds then is when the value of i reaches becomes equal to the number of characters in the string. Each time through the loop i is incremented by one. In the body of the loop an accumulator (the sum variable) is incremented by the ascii value of the character each time through the loop. Notice the use of the cast static_case<int>(str.at(i))
Because we are accumulating the variable sum which is an int it is appropriate to cast each char to an int. This means that for that statement treat the character as an int. This way we are adding int values to each other.
Omitting Expressions
Here is an example of removing the update expression:
Finally here is an example of a for ever loop (A loop that never ends) :
That's true for counted loops; if you are going to write loops that are controlled by a counter, you should probably use the for loop. But, not all loops, or even most loops, are counter-controlled. Event controlled loops are much more common, and there, the while loop reigns.
A number is called a perfect number if by adding all the positive divisors of the number (except itself), the result is the number itself.
Six is the first perfect number. Its divisors (other than the number itself: 6) are 1, 2, and 3 and 1 + 2 + 3 equals 6. Other perfect numbers include 28, 496 and 8128. Using a counted loop can you check to see if a number is a perfect number? Check your solution with the video below
Random Numbers
I know you were expecting to see information about the while loop here. Before we get to that I want to take a detour and go down the road of creating and using random numbers. We do that here because we will want to have an example or two using random numbers with the while loop.
The C++ programming language has many built in functions that you can use to help you with you coding tasks. There are two such functions dedicated to the creation of random numbers. These functions are
To generate a random number you simply call the rand function and assign what the function produces to a variable:
int someNumber = rand();
If you haven't deduced it by now, this is the way all assignment works in C++; even functions!
The above will generate a value between 0 and a constant called RAND_MAX which is defined in the header cstdlib. The value of RAND_MAX is platform dependent but is guaranteed to be at least 32767 (16-bit value).
Getting a range
To get a random number within a range (scaling the value) you need to employ the modulus operator. Suppose you want to generate a random number in the range of 0 to 100. You would do the following:
int someNumber = rand() % 101;
You may be asking why a value of 101 when what you want is 100? The simple answer is that you want a range of 100 but we start counting at zero in computer science so if you did a modulus of 100 you would get a range of 100 values but they would be the numbers 0 to 99.
This idea of scaling can be taken one step further. Suppose you want to generate a random number in the range of 1 - 100. This can be done simply by adding one to the result:
int someNumber = rand() % 100 + 1;
Here you get a value between 0 and 99 then simply add 1 to get a value in the range of 1 to 100.
To get a more diverse range you can use a formula of modulus ((max - min) + 1) + min. Suppose you want to have numbers in the range of 10 to 25. The following code uses the formula to do just that:
Pseudo- Random
As it turns out random numbers in C++ are not really random. If you were to run the above code several times what you would find is that the same random numbers would appear in the same order each time the program is run. This would not make for a very good Vegas game would it? To deal with this we can use the srand function. The srand function is a function that simply injects a value into the formula used to create a random number. The s in srand stands for seed. What you are doing with the function then is seeding the random number generator. You can provide any unsigned whole number to the function. For example:
srand(100);
The problem with doing this is that you have seeded the random number generator with a constant so you have the same problem. The numbers will repeat in the same order each time you run the program.
The Time Of Day Clock
To solve the seeding problem you can incorporate one of the time functions that is part of the standard library. In order to use any of the time functions though you must first
#include <ctime>
The function you want to use is simply time. The time function gets the current calendar time. You can pass this function a parameter of type time_t or you can pass NULL. In either case the function will return the time in milliseconds. For our purposes, we simply want to pass a value of NULL. Here is the above program using the time functions to seed the random number generator.
One of the things you might encounter when using the value produced by the time function to seed the random number generator and that is a warning from the compiler stating that the conversion from time_t to unsigned int could produce a possible loss of data. This warning is generated because the srand function takes a data type of unsigned int and the time function produces a data type of time_t which is defined inside the ctime header. For our purposes this warning really doesn't mean much but we can get rid of it by casting:
srand(static_cast<unsigned int>(time(0)));
The while Loop
The while loop has the following syntax
As you can see the while loop is constructed very similar to an if statement. The only visible difference is the use of the keyword while instead of if. Be careful though, you don't want to use a decision where you need to repeat statements and vice-versa.
The different loops have particular type problems that they work best for but you will see that they are very versatile also. For instance, you can use a while loop to solve a counting problem. You simply need to make sure that you have all of the components needed for counting initialized and in the right place.
Counting Loops With While
To create a counted loop using while you must have all of the components used in the for loop but they are going to have to be put in different locations. To recap, here is an example of a for loop that counts up to 10:
To create the same loop with while you must create the variable i as a precondition to the loop, the test expression goes inside the parentheses, and the update expression goes in the body of the loop:
Example
Let's look one more time at the example of summing all of the ascii character in a String. This time written using a counted while loop:
To use a while loop instead of a for loop three things needed to be done:
Common Sources Of Error It is easy to introduce logic errors when using a while loop for counting. You should become aware of each of them so that you know how to write the loop correctly the first time. Or, at the very least know where to look and how to fix these problems
1. Using an improperly initialized or expired counter. In the for loop the scope of the counter is restricted to the body of the for loop. This is not true for variables defined outside of the block of the loop. It is possible to have several loops that use the same variable. In this situation using an expired counter is an easy thing to do.
One solution to this problem is to use unique variable names for each counter you create. Another solution and probable the best answer to get into the habit of creating and initializing your counter line directly before the while statement.
2. Endless loops. Endless loops typically happen because there isn't any code within the body of the loop to move the loop towards it's bounds. In the case of a counted loop this is usually caused by forgetting to place or update the counter within the body of the loop.
The best solution to this problem is to build the loop first without any of the statements you want repeated. This would involve determining the bounds of the loop and creating and updating any variables that will move the loop towards the bounds. If you get into the habit of concentrating on the components of what makes the loop run you will have much better success.
3. The phantom semicolon. The phantom semicolon is not particular to the while loop. It can be placed in any block of code. Here is an example:
Because of the semicolon, the code inside the body of the loop may never happen. If it does happen it will only happen one time.
Video - Counted Loops
Indefinite Loops
Examine the following code:
Can you determine what the bounds and the goal of the loop are?
Ok, I agree this is not much of an algorithm but it serves as a simple example. Here is another question, can you tell how many times this loop will execute? The answer should be no. Because the number tested for is being randomly generated there is no way to know for sure how many times the loop will execute. This kind of loop is called an indefinite loop because we cannot determine how many numbers will be generated before the value 50 comes up.
Sentinel Loop
A sentinel loop is a loop that looks for some particular value as a way of terminating the repetition. The above indefinite loop is also called a sentinel bounds loop because it is looking for the value of 50 to end the loop.
Sentinel loops are typically used in two different situations:
Sentinel Ranges
Sentinels do not necessarily need to be one particular value. You can also have a range of values:
"Read numbers from the keyboard until an even number is encountered. Output the sum and average of the odd numbers"
Given the above problem can you determine the bounds and the goal of the problem? In addition, can you determine any preconditions, and post conditions that are necessary?
Let's take a look at the code for this problem:
This loop has some pre and post conditions that should be identified discussed:
Preconditions
Loop preconditions typically involve the creation of variable to be used for the bounds and the goal. Looking closely at the code you can see that there are some preconditions.
This problem also has a post condition
Post Condition
Since one of the goals of the loop is to output the average of all of the odd numbers we must make sure that at least one odd number was entered. If not, the loop would not be entered and the count variable would be zero. This would present us with a divide by zero error. The if statement takes care of this problem by checking the value of count before any division takes place.
Primed Loops
. Priming the loop means setting up the first value before the loop is entered so that the loop works properly. Before the loop is entered the first value is taken from the keyboard. This allows the loop to start working with proper first value. Notice that these instructions are repeated at the bottom of the loop. You may be thinking that this is bad because code has been duplicated. In the case of primed loops this is required to move the loop towards it's bounds.
Many beginning students will do something like this:
Here the number 1 has been stored in the variable value. This is not correct because you will be counting the one as the first number entered.
You are going to find that in most cases you will need to prime the while loop in some way. This means getting the first value for the loop test then repeating it again inside the loop body to move the loop towards a bounds.
Here is an example of a simple game loop that will repeat until the user does not want to play:
Before the loop starts the user is asked if they want to play. The while loop is encountered and the boolean test checks to see if the answer is 'y'. This will make the loop repeat until the answer is anything other than 'y'. At the bottom of the loop body the code that asks the user if they want to play is repeated. Their answer is then taken from the keyboard. If this code is not in the body of the loop the loop will run forever. The reason this becomes an infinite loop is that the variable answer would never get changed so the loop would not move towards it's bounds in any way.
Video - Using Indefinite Loops
The final loop we will look at is the do-while loop. With this loop, the test is at the bottom meaning that the loop body will always be executed one time. Here is the syntax for the do-while loop:
The do - while loop's boolean condition follows the while keyword. Just like all selection and iteration statements in C++. Notice that at the end of the condition statement there is a semicolon. This is needed or you will receive an error. This is an easy thing to forget an could be a headache for you.
The do-while loop is one that many beginning programmers gravitate towards. I believe this is because there is a lack if understanding on how to properly prime the while loop. It could be that this loop seems a little more natural. If you find yourself being one of the people who is using the do-while loop often you should probably rethink what you are doing. The majority of the time a for loop or a while loop will work just fine.
You should know that this loop is typically not meant to be the best loop to choose because it is like putting the cart before the horse. Think of it this way, if you were cooking a big pot of soup wouldn't you taste it before adding any seasoning? With a do-while loop it is like seasoning the soup before tasting to see if it needs any seasoning.
Here is an example to show you what I mean. This program asks the user to keep guessing a value between 1 and 10. The answer of course is 7, please don't tell anyone:
Repetition and selections statements in C++ alter the flow of control which is done by providing a method of conditionally executing or repeating blocks of code.
In the early days of programming before high level programming languages provided constructs for selection and iteration, programming languages used jumps as a way to have selection and looping statements.
The C++ language has a jump statement built into it. This statement is called the goto statement and is frowned upon by most programmers. The reason for this is that when used too frequently the goto statement can produce "spaghetti code". That is code that can jump back and forth making the code path difficult to follow. In fact using goto statements are so frowned upon that this is the only place they are mentioned in this material.
The break statement forces the flow of the code to jump past the closing brace of the loop it is contained within. This means that if you have a nested loop the break statement will only force the code to break out of the loop it is in. If the break is in an inner loop it will only break out of that inner loop.
Here's an example, that shows how the break statement can be used to simulate a sentinel loop that stops when the number 50 has been reached. Note that the loop bounds does not need to test for the sentinel value.
The following code will demonstrate the use of the continue statement:
9 and '9' are different
The isdigit() function returns a bool true if the character is a digit, false otherwise.
If the character entered is a digit then it gets converted to a number by subtracting the character '0' from the character entered. The character '0' has an ascii value of 48. So the above code is equivalent to subtracting 48 from the character entered. In any case, subtracting 48 from the digit will give us the actual binary value of the character representation.
Once the character is converted, it gets added to the sum of the values. If what is entered at the keyboard is not a digit then the continue statement forces the path of the code back to the top of the loop. Notice that the update expression is missing. The update variable i in this case only gets updated if a digit character is entered. This forces the input of 10 digit characters.
Nested Loops
Both break and continue work on the current loop. That means, when you are in an inner loop, a break statement only exits the inner loop, it doesn't get you out of the outer loop.
If you need to break out of both inner and outer loops, then you will have to write some logic to handle it.
Video - The break Statement