C++ Tutorial 3 - Control structres, conditions and loops using Collatz

If you have not checked out the previous tutorials you probably should, a quick summary of what we have learned so far would be, basic input out including printing characters and numbers to the terminal as well as taking floating point values from the same environment and manipulating those numbers and walked through some type declarations. In this lesson we will discuss the control structures found in the C++ language. The idea behind control structures is remarkably simple, the purpose is to control the flow of the program, the order and number of times that lines of code are executed by the computer. Previously we could have looked at all of the previous programs as executing from top to bottom of following instructions that the programmer gives the computer before moving onto the next line of code. Programs do not have to execute in this way, in fact there are some problems which cannot be reduced to a top down, linear format and actually require a more sophisticated approach.

A quick note about operators: C++ has many operators and key words that are used commonly and we will only touch on a few of them in this tutorial, lesson four will go into greater depth, but for now you will probably recognize all of them with the exception of modulus operator, %, which gives us the remainder after integer, non-floating point, division. The only syntactica lly difficult operator you might see so far is when we decide to change the value of a number, for example below: input = input/2, but the concept should be straight forward enough to see that we are dividing a number by two and then replacing that original number. That is, the original value of input is lost forever.

The first way of controlling the execution of a program is going to be a simple program in which the user enters a number into the terminal and the program then performs some operation of that number based on if the number is odd or even.

#include<iostream>
using namespace std;

int main()
{
cout << "=== Starting Program ===" << endl;

int input;

cout << "Input an int: ";
cin >> input;

if(input % 2 == 0)
{
input = input / 2;
}

if(input % 2 != 0)
{
input = input * 3 + 1;
}

cout << "Result was: " << input << endl;
cout << "=== Ending Program ===" << endl;

return 0;
}

Just like previous concepts we looked at , the C++ language has some syntax requirements for the programmer to under stand. The first thing to remember is that if statements have to be followed by some condition, these conditions are always recorded as true/false, in parenthesis and no semi colon. The braces are once again optional, but if you choose not use them then you must indent the code that would be inside of the braces unless the code below the condition is only one line. The reason why is simple, the compiler has no idea what code is to be run if the condition holds true if you do not include those braces. Once again, the choice to include them or not is largely a personal one but note that most of the time you will see braces included in code in existing projects. No, this does not break C++ as a white space insensitive language. After the condition you have the code block, in braces or not, and what ever code you put inside of here must end in a semi colon.

The short program above is a simple implementation of something called the Collatz Conjecture. Essentially this conjecture says that if you take any random integer and divide it by 2 if it is even, or multiply it by three and add one, increment, if it is odd. If you do this consecutively it will always converge to one. For this code segment the crucial thing to notice is that the code inside of the second " if statement", input = input * 3 + 1, will execute as long as "input" is not divisible by two. That condition can be true, that code segment will execute, if the user enters an odd number, such as the number three, or if the user enters an even number which when divided by two has a dividend which is odd. For example, if the user were to input the number ten then the first conditional would execute because ten is evenly divisible by two. Ten divided by two is equal to five which is odd and then the final result should be sixteen. You should probably be able to see where this might cause a problem if the purpose of this program is to find the number of steps that it takes for a user defined number to converge to one via the Collatz Conjecture, that is the number of steps that the program takes will be miscounted by cause two steps could occur at once. Now it is possible to solve some this problem by including an additional variable, bools are probably the best choice because the problem is fundamentally binary - has this condition been checked for ?, and test for two variables at the same time like below:

#include<iostream>
using namespace std;

int main()
{
cout << "=== Starting Program ===" << endl;

int input;
bool already_tested = false;

cout << "Input an int: ";
cin >> input;

if(input % 2 == 0)
{
already_tested = true;
input = input / 2;
}

if(input % 2 != 0 && !already_tested)
{
already_tested = true;
input = input * 3 + 1;
}

cout << "Result was: " << input << endl;
cout << "=== Ending Program ===" << endl;

return 0;
}

The code above certainly works, the "bug" where a user could enter a number and if that number meets certain criteria then the number of steps could be miscounted, has been eliminated and because the program is reasonably small the code is also relatively easy to read. However there are three fairly obvious problems with this little bit of code. The first problem is that it is not scalable, which is to say that if we wanted to make the program a bit larger then we would have trouble with the number of variables which we have to create and their naming conventions would also probably become quite confusing. The second problem which we have not talked about in any great depth yet is that any variable we create takes up some amount of code in the computer's memory and if we choose to use many conditional statements in some project then we could end up using a considerable amount of memory, on a side note there is also a considerable amount of overhead in the CPU resources which are consumed by checking these variables. But the most important problem which is so simple it might not be obvious, and that is that there is simply a better way of solving this problem without creating many variables which do not have more than a single use. If we could "break" the flow of a program after we have already checked some condition then we would not need to use this clumsy system of using multiple variables to accomplish the same task. Well, the C++ language allows us to do that withsomething called an "if-else-if statement". In terms of code the syntax is quite straight forward but the critical thing to remember is that the second code segment, which we will call that segment "B" for expediency, will not execute if the condition for segment "A" is true. As stated, the code for this is quite easy to understand as you can see below:

#include<iostream>
using namespace std;

int main()
{
cout << "=== Starting Program ===" << endl;

int input;

cout << "Input an int: ";
cin >> input;

if (input % 2 == 0)
{
input = input / 2;
}

else if (input % 2 != 0)
{
input = input * 3 + 1;
}

cout << "Result was: " << input << endl;
cout << "=== Ending Program ===" << endl;

return 0;
}

The code above works in exactly the way that we discussed previously. First the user must input a number, when he does then the first condition is tested and if it is true then segment A is executed, or if it is not then segment B is executed. Because there are only two conditions, either the input is even or odd, and the answer is binary, which is to say that if one condition is false then the other must be true so either the number is even or odd, it is possible that we could write a brief variation on this code where the second segment, B, only has an “else statement” which is executed when the first statement is not true. The difference between ad else if and an else statement is that the in an else statement there is no condition to be tested and the second segment will be performed automatically if the first condition is not true. The proper syntax for this is to remove the “if(input % 2 != )” from the line which the else if statement is found.

The next type of conditional statement we will look at might seem a little strange considering how straight forward the previous ones we have looked are. This statement is called the switch statement. In C++ there is a considerable difference between an if-else statement and the switch statement and we will only have a chance to discuss part of the differences in this series.We will talk about the switch statement in greater depth once we have gone over operators, lesson 4, but for now we will to talk about them as a competing idea to the if else statement. If-else-if-else statements can be extended to as many if-else-if clauses that the programmer wants to, this does not apply here but if we needed to have multiple else if conditions between anif and an else block we could without any extra work than is required to write any of the previous. Ignoring certain benefits to switch statements, such as the possibility of faster run time, the main reason why we would would use them is to control the flow of a program which has many possible conditions which we must check for. Although it is hard to see in this example, switch statements tend to be easier to read in problems which have many conditions to check for.

#include<iostream>
using namespace std;

int main()
{
cout << "=== Starting Program ===" << endl;

int input;

cout << "Input an int: ";
cin >> input;

switch(input % 2)
{
case 0:

input = input / 2;
break;

case 1:

input = input * 3 + 1;
break;
}

cout << "Result was: " << input << endl;
cout << "=== Ending Program ===" << endl;

return 0;
}

Obviously the syntax for this type of statement is significantly different from what we saw with if-else, and there are some quite different mechanisms at play, but we are using it to achieve the same exact goal, and correctly produce the same exact output, only with different syntax. Some things to remember about using this code. First of all the lines which say “case n:” are not referring to the number of cases, “n” refers to the value of input % 2. We can add a case to the effect of “case -1:” if we wanted to handle negative input from the user. The second thing to remember is that each has must end in a colon. The third thing to remember is that if you do not include “break;” at the end of a case then the given case will “fall through” to the next case. For example, if we removed the line which has “break;” from the first case, case: 0, then we would have the same bug as we had in one of the earlier examples because the those two cases would not be run separately. Again, this particular topic will be discussed in the next lesson.

The next topic which we will have a look at is the loop. You probably noticed that this short code segment only executes once. The stated goal of this program at the beginning of this article is to write a program which calculates the number of steps required to converge to one. If the user enters “1” then the program executes correctly. But suppose that the user enters the number “7“, then the program prints out “Result was: 28”, which is obviously wrong. The reason why this is not giving us the right answer is because the Collatzconjecture requires us to repeat the process many times until we reach one. The conjecture actually states that for any positive integer it will eventually reach one if you repeat enough times. One possible solution would be to write to take the number of steps required to solve the problem and copy-paste that many if-else statements into out source file. That would work as long as we know how many steps are required, which we obviously do not know because the set of integers continues to infinity and we can always find a new number which has not been triedbefore, and even if we could the number of steps it takes for the number seven to reach one is sixteen so would have a total of fifteen more statements to copy paste. Clearly we need to have a way of repeating the same task over and over again until some condition, that number equals one, has been reached. Thankfully there is a way of doing such a thing with a “while loop”. The following code illustrates one possible solution to the problem:

#include<iostream>
using namespace std;

int main()
{
cout << "=== Starting Program ===" << endl;

int input;
int steps = 0;

cout << "Input an int: ";
cin >> input;

while(input != 1)
{
if (input % 2 == 0)
{
input = input / 2;
steps = steps + 1;
}

else if (input % 2 != 0)
{
input = input * 3 + 1;
steps = steps + 1;
}
}

cout << "Result was: " << input << endl;
cout << "Number of steps required for is: " << steps << endl;
cout << "=== Ending Program ===" << endl;

return 0;
}

The syntax for the while loop probably looks considerably similar to if statements and there are few or no differences. The only critical thing to remember is that the condition of the while loop, “input != 1” in this case, will be tested right after the last line of code in the while block is tested. It is not a problem here, but sometimes the program might crash if you try to do something like divide by zero and you are not watching. The advantage of using loops is that they reduce a great deal of labor, and sometimes allow us to do things which we otherwise could not, the massive disadvantage to them is that sometimes we can lose track of how many times the loop has executed, iterated, which can obviously cause many problem.

There is a second type of loop, which is at least as common if not more so, is the "for loop". Generally speaking, this loop is used in settings when we know how many times it will run, in other words for a definite number of iterations, and while loops are generally used where we do not know how many times a loop might iterate. But in this case to illustrate how you might use a for loop to solve this problem you would simply change one line of code to the following:

#include<iostream>
using namespace std;

int main()
{
cout << "=== Starting Program ===" << endl;

int input;
int steps = 0;

cout << "Input an int: ";
cin >> input;

while(input != 1)
{
if (input % 2 == 0)
{
input = input / 2;
steps = steps + 1;
}

else if (input % 2 != 0)
{
input = input * 3 + 1;
steps = steps + 1;
}
}

cout << "Result was: " << input << endl;
cout << "Number of steps required for is: " << steps << endl;
cout << "=== Ending Program ===" << endl;

return 0;
}

Examining the following code you should notice that the syntax for the for loop is substantially different while the block of the loop is similar to identical to that of the while loop. For starters there are a few semicolons in the first line of the for loop, each one of the three semicolons corresponds to a different statement. The first statement is called the initialization, this one is pretty straight forward as it only does one thing which is create an integer, it does not have to be an integer but floating point numbers, characters, and Boolean values do not make sense here and although you could use one of the variations of the integer type if you were working with really large numbers but we will not have to worry about that here, and initialize it to some value – generally zero but not always. The next statement contains a condition, generally speaking the condition tests if the integer that we just created is less than some integer value but not always as you can see in this example, which for as long as that condition equals true then the block of code will execute. The third statement is the operation. This statement almost always adds one to the integer, increment, or subtracts one from the integer if you wish to iterate from the maximum value, that condition we just mentioned, to the minimum value. This concept will be made clearer in the fifth tutorial when we go over arrays.

There is one keyword and two types of structures which I have not mentioned yet but they are less common and generally, if not always, bad practice to use. The first one is the continue keyword. This keyword is used in a loop, while or for loops, stops the further execution of the all of the code after the keyword and jumps back to the beginning of the loop. If the condition of the loop is met then the loop will execute again, including the continue keyword unless you put it inside of an if or switch statement, if it is not met then the loop will end.

The structure that I did not mention before is called the do while loop. It should not be a shock, the name is a good hint, that this loop is very similar to the while loop but differs in one critical fact which is that regardless of what the condition this loop will always execute at least once, DO while not while do, even if the condition is false. This can be advantageous because it can simplify code somewhat, the other approach would be to take the code inside of the loop and just write it before or after the loop, but it can have serious downsides if in the process of checking the condition you do something which could crash your program. Once again, the loops are more or less interchangeable and probably the best choice is to just use either a while or a for loop. The other awkward thing about this loop is that the syntax is not as clear. Instead of placing while at the start of the loop it is at the bottom of the loop and the condition directly follows the do keyword which is where the while keyword used to be.

The last one is a dreadful vile control which goes back to the dark ages and should be avoided at all costs. This is the goto statement. The goto statement is used to jump from line of code to line of code using the goto keyword and the colon, :, operator after some label, any valid name which follows the naming conventions from the previous tutorial, and then the program jumps back to that after the goto is called.