### Impuzzable

This is about a fiendishly difficult jigsaw and how to solve it using a computer program.

### A Computer Program to Find Magic Squares

This follows up the 'magic Squares for Special Occasions' article which tells you you to create a 4by4 magicsquare with a special date on the top line using no negative numbers and no repeats.

### First Forward Into Logo 10: Count up - Count Down

What happens when a procedure calls itself?

# An Introduction to Computer Programming and Mathematics

##### Stage: 5

Published February 2011.

A computer program is a series of instructions (also called code) given to the computer to perform some task, which could be anything from summing the numbers from 1 to 10 to modelling the climate. When the computer follows the instructions given in the program, we say that the computer is running the program. There are many different ways of writing these instructions for the computer (we speak of programming in different languages) - in this article, we will use a language called C++. By the end of it you will be able to write your own programs to perform basic mathematical and scientific tasks.

## Our first C++ program

Our first C++ program will tell the computer to print out the text "Hello world!". Here it is (don't worry - it will be explained line by line).

#include
using namespace std;

int main()
{
// the next line prints out the text "Hello world!"
cout << "Hello world!";
}


For a computer to run this program, it must first be compiled by a compiler (this means translating it from the language of C++ to the computer's native machine code language). There's a useful online resource, codepad.org, which does the steps of compiling and running the program for us. Navigate to this website, select the option "C++" for the language, and copy and paste (or better yet, type out) the program above in the text box, before clicking the submit button. If you entered the text correctly, then you should see the following displayed for the output:

Hello world!


If this doesn't appear, then you may have entered the program incorrectly - try again.

To get a feel for what is going on, let us examine the structure of the program.

#include
using namespace std;


These first two lines tell the compiler about a range of functions that are available - a function is a block of code, which in this case, already exists in the computer memory ready for us to use. For now you don't need to understand exactly these lines mean; only that these should be placed at the top of most C++ programs that you will write. In this program, we want to use a function called "cout", which prints out text.

int main()
{
...
}


This type of structure denotes a function in the program, called "main". This is a special function; we can (and later will) define functions with other names, but the computer will look for this function for the initial instructions to start following, which we place inside the brackets {, } (these show where the function starts and stops). We will describe more on the function syntax later.

// the next line prints out the text "Hello world!"


This is a comment line. When the compiler sees "//", it will ignore anything that comes after this until the end of the line. Adding this text has no effect on the behaviour of the program, but it can be useful for when a person wishes to read and understand the code at a later date.

cout << "Hello world!" << endl;


This tells the computer to print out text. You don't need to worry about how cout works for now - only how to use it. A series of text or numbers can be printed out by combining them with <<. For example we could have written the above line instead as:

cout << "Hello" << " world" << "!" << endl;


The endl means "end line" and prints out a newline character.

The semicolons ; tell the compiler where one instruction stops and another begins - their role is analogous to the role played by full-stops in sentences.

Exercise: We must be precise in programming. If we type out a name of a keyword incorrectly, miss out a bracket, or forget a semicolon, for example, then the compiler will not be able to understand the program. Identify the 5 mistakes in the following program.

#invlude
us1ng namespace std

int main()
{
/ / the next line prints out the text "Hello world!"
cout << "Hello world!;
}


Solution: include and using were spelt incorrectly. There is a semicolon missing at the end of the 2nd line. A space has been inserted into the "//" comment part. There is a quote " missing for the string in the 7th line.

## Variables and arithmetic

A variable in a computer program is a piece of information such as a number in the computer's memory. Once we have a variable, we can make use of and modify its value as we please. This is analogous to how a human brain stores, for example, a friend's address - it is there ready to be recalled, and may change from time to time.

Variables are essential for computer programs to work. If we sum the numbers from 1 to 10, we need a variable to store the sum at each stage of the calculation. If a program receives two numbers from the user and calculates their sum, it must use variables to store the inputed values before the sum can be calculated.

### Integer variables

In C++, there are many different types of variables, representing the different types of information that they refer to. To make use of a variable, we must first tell the computer what type we want. The first one we look at in this section are integer variables, for storing a whole number.

To "declare" an integer variable (which means setting aside computer memory for an integer), we include a line of code such as the following. The variable is then ready for use.

int x = 0;


The "int" is the special codeword for integer. The "x" is the name of the variable, and can be replaced with anything made up of letters, numbers, and underscores (the first character cannot be a number however). The case of the letters are also important (so "hello" and "heLLo" would be seen as different by the computer). The " = 0" sets the variable's initial value to zero. We can also write "int x;" if we do not care about setting a specific value.

Exercise: Which of these are valid variable names?

1. seven
2. 2nd
3. TOP_speed
4. fast1
5. quick#

Solution: 1, 3, 4 are valid variable names. Name 2 starts with a number. Name 5 contains an illegal character #.

We can later change the value of a variable by writing a piece of code such as:

x = 7;


This assigns the value 7 to x. To print out the value of a variable, we can again use the "cout" function - to display the value of x for example, we include the line of code:

cout << x << endl;


Here is a complete program that declares a variable called x, with initial value 0, prints out its value, assigns the value of 7 to x and prints out its value again. This shows how variables can be read from and changed. Try it.

#include
using namespace std;

int main()
{
int x = 0;
cout << x << endl;
x = 7;
cout << x << endl;
}


For integers, we can perform all the basic arithmetic operations such as addition, subtraction, multiplication and division. We use the symbols +, -, *, and / for these respectively. For example, this code creates two integer variables x and y with initial values, creates a third integer variable z, and sets the value of z to the value of x + y.

int x = 2;
int y = 4;
int z;
z = x + y + 3;


In the above code, z would now have the value of 9. We can also write the last two lines more quickly as "int z = x + y + 3". We can also write code such as:

int x = 2;
x = x * x;


The line "x = x * x" may look a bit strange - and if it was a mathematical equation then it would mean "x has a value satisfying x = x * x". In a computer program however, it means "take x, multipy it by itself, and assign the resulting value back to x". Now x would have the value 4.

There are another two operators, ++ and --, which are very useful (there are different types of operators - things like + and - will take two integer values and produce a third. ++ and -- take an integer variable and change its value). The expression "x = x + 1;" (increasing the value of x by 1) tends to occur a lot in programming, so C++ has a shorter way of writing this: the piece of code "x++;" has exactly the same effect. Similarly "x = x - 1;" and "x--;" are equivalent. For example, in the following lines of code, x has initial value 3, but has final value 5.

int x = 3;
x++;
x++;


What about division? If x is an integer variable has value 4, and we write "int y = x / 2;", then y will have the value 2. However, what is the value of y in the following program?

int x = 4;
int y = x / 3;


The "int" means that y is a whole number. In this expression, the computer will discard the non-integer part of the value of x/3. So since 4/3 = 1 + 1/3, y will get the value 1; y is "rounded down". If the expression is negative, then the resulting value will get "rounded up" (this is a convention, and suits the way the computer calculates the numbers). So for example, the value of (-4)/3 = -1 - 1/3, so its integer part is -1 (and not -2).

The last integer operator that we have not yet mentioned is %. The value of the expression "x % y" is the remainder of x when it is divided by y. For example, if x has the value 7 and we write "int z = x % 4;", then z will have the value 3.

Exercise: What value of x will be printed in the following code? Try creating a program with this code and running it to see if you are correct.

int x = 11;
int y = x % 4;
x = x / 2;
x = x + y*2;
cout << "x = " << x << endl;


### Real variables

In the previous section, we saw how "int x;" defined an integer valued variable called x. We can similarly define variables for storing a real valued number, such as -2.5 or 3.141592. In programming these are referred to as floating point numbers. In C++ we can write

float x;


to define a floating point variable called x. All the arithmetic operations +, -, *, / can be used for floating point numbers and variables. When we divide two floating point numbers, then we get the full number (not just the integer part).

The following piece of code creates two floating point variables called pi and r to store an approximation to $pi$, and a radius, and defines a third floating point variable called area which stores the result of a calculation - namely the area of the circle of radius 4. Try it!

#include
using namespace std;

int main()
{
float pi = 3.141592;
float r = 4;
float area = pi * r * r;
cout << area << endl;
}


Exercise: Write a program that calculates the volume of a sphere of radius 4 (the formula for the volume is $(4/3) \pi r^3$).

### Boolean variables

A boolean variable stores a truth value (a bit of information representing either "true" or "false"). We define it using the "bool" keyword. For example, to define a boolean variable called x with initial value true, we write:

bool x = true;


Similarly to how we can combine two numbers via addition or subtraction to get a third number, there are two operations, known as AND and OR that combine two boolean variables to produce a third. In C++, we write && for AND (similarly to how we write + for addition), and || for OR. If x and y are boolean variables, then "x && y" has value true only when x and y are both true. "x or y" has value true only when at least one of x or y has value true. (For more on logic, see here.) There is also a third operator, NOT, which takes a single boolean value and gives its logical inverse. C++ uses the symbol ! for this. If x is false, then "!x" has the value true, and vice versa.

Let's see an example of this. Try running the following program.

#include
using namespace std;

int main()
{
bool is_saturday = true;
bool is_sunday = false;

bool is_weekend = is_saturday || is_sunday;

cout << is_weekend << endl;
}


In this program, the value of is_weekend is the logical OR of the two boolean variables is_saturday and is_sunday (and so it will have value true). Try changing the initial values of the boolean variables is_saturday and is_sunday and run the program again.

The following is a snippet of code showing the NOT operator in use. The boolean variable is_weekday will be initialized with the value false.

bool is_weekend = true;
bool is_weekday = !is_weekend;


Similarly to how we can write expressions for integer variables which use multiple operators and mix variables with numbers, we can do the same with boolean variables. For example, in the following code, c will get the value true.

bool a = false;
bool b = true;
bool c = (a || b) && (a || true);


Exercise: The AND and OR operators are like AND and OR logic gates in electronic circuits (for more on logic gates, see here). We can combine &&, || and ! to produce different logic gates. For example, the C++ expresion "!(!a || !b)" represents AND - it is equivalent to "a && b", where a and b are boolean variables. What boolean expressions represent the following?

• OR (using only the operators ! and &&).
• NAND
• NOR
• XOR
• XNOR

## Testing variables

C++ allows us to test the value of a variable (for example, to see if an integer variable has value 27 or has value at least 18). The result of a comparison is a boolean value (true or false). There are five "comparison operators" for numbers (we will see these in use shortly).

• x <= y - This expression is true if x $\le$ y.
• x >= y - This expression is true if x $\ge$ y.
• x < y - This expression is true if x < y.
• x > y - This expression is true if x > y.
• x == y - This expression is true if x = y.
• x != y - This expression is true if x $\ne$ y.

For example, suppose we had declared an integer variable called "age". The expression age >= 18 has a boolean value, and is true if age $\ge$ 18, and otherwise is false. Equivalently, we could have written age > 17. We can store the result of this expression in a boolean variable. Here's an example program:

#include
using namespace std;

int main()
{
int age = 15;

bool isAdult = age >= 18;
}


Try running the program. Try modifying the value of age, and also try other comparison operators (so try replacing >= with one of <=, >, < ==).

Of course, we are free to compare variables with variables, variables with values, and values with values (for example, 15 > 17 is a valid piece of C++ code, and always has the value false). We can also combine comparison expressions together in the same way that we combined boolean values together with && and ||. What does the following piece of code do?

int age = 15;
bool isTeenager = (age >= 13) && (age <= 19);


The expression age >= 13 has value true, and the expression age <= 19 also has value true. Therefore isTeenager has the value of the expression (age >= 13) && (age <= 19), which has value true && true, which is true.

There are in general many ways of writing a boolean expression with the same value. For example, all of these are equivalent:

• age >= 18
• age - 3 > 14
• -age < -17
• 15 - age <= 3

## Branching and if statements

So far, the programs we have written can be thought of as a sequence of instructions executed in turn, for example performing an arithmetic operation and then printing out its value. This doesn't allow us to do that much. C++ allows us to conditionally execute a segment of code depending on the value of a boolean expression. We do this using an if statement. Let us demonstrate by an example - try running this code.

#include
using namespace std;

int main()
{
int x = 6;
int y = 5;

if ( x > y )
{
cout << "x is bigger than y" << endl;
}
}


When you run this program, it will output "x is bigger than y". This is an example of conditional execution - the value of the (boolean) comparison expression x > y is true, and so the code inside the brackets { ... } is executed.

This code also shows where else brackets { } are used. They are like parentheses ( ) in a mathematical expression such as (((2+3)*5)-4)*(3-4). They must be nestled and matched properly - for example, )2+(3*7)+3( is not a valid mathematical expression. Every time { appears in C++ code, it must be followed somewhere later by a corresponding }. We can nestle if statements together in this way, for example:

int x = 6;
int y = 5;
int z = 2;

if ( x > y )
{
if ( x > z )
{
cout cout << "x is biggest of them all" << endl;
}
}


We can also extend if statements to an if-else block of code. This has the general form if ( expr1 ) { code1 } else if ( expr2 ) { code2 } ... else if ( exprN ) { codeN } else { lastCode } (but many variations are possible). The computer will check each expression expr1, expr2, ... in turn to see if any of them are true. If it is true then the code inside the brackets will be executed and then no further expressions will be checked. If none of the expressions are true then the code in the last brackets is executed (lastCode in the above). Any of the else if or the else parts can be eliminated to also produce valid code. The following example program shows them in use.

#include
using namespace std;

int main()
{
int x = 4;
int y = 5;

if ( x > y )
{
cout << "x is bigger than y" << endl;
}
else if ( x == y )
{
cout << "x is equal to y" << endl;
}
else
{
cout << "x is smaller than y" << endl;
}
}


When you run the program, the text "x is smaller than y" is displayed. We could delete the last "else" part to produce a valid C++ program, which would not display any output when ran (since neither of the expressions x > y or x == y is true), such as:

int x = 4;
int y = 5;

if ( x > y )
{
cout << "x is bigger than y" << endl;
}
else if ( x == y )
{
cout << "x is equal to y" << endl;
}


Or we could delete the middle "else if" part, so that either the first code was executed, or the second code was executed.

int x = 4;
int y = 5;

if ( x > y )
{
cout << "x is bigger than y" << endl;
}
else
{
cout << "x is at most y" << endl;
}


Exercise:Write a program that defines a variable x with some initial value, and an if-else statement that prints out whether x is odd or even.

## Loops

Looping is the next important concept in programming. C++ allows us to repeatedly execute a block of code, until some condition is reached (for example, until the value of an integer counter reaches 10).

The first type of looping is the while loop. To use this in a C++ program, we insert code of the form

while ( expression )
{
// code
}


where expression is replaced with a boolean expression (such as x < 10), and code is replaced with the instructions that we wish to repeatedly execute. When the while loop is encountered by the computer, the behaviour is as follows:

1. If the expression is false, then skip the code inside the brackets { } and continue with the program.
2. Otherwise, execute the code in the brackets { } and goto step 1 again.

So the code inside the brackets { } will be repeatedly executed until the expression evaluates to false.

Let us see an example - try running the following program:

#include
using namespace std;

int main()
{
int i = 0;
while ( i < 5 )
{
cout << i << endl;
i++;
}
}


This program creates an integer valued variable called i with initial value 0. The code in the while loop is executed if i < 5, which is clearly true initially - and so "0" is printed out. The value of i is then increased to 1 (this is the code i++;). The condition i < 5 is still true, so the value of i - "1" - is printed out again, and i is incremented again. This continues until i reaches value 5 - at which point the condition i < 5 is false and the while loop is skipped.

Exercise: write a program to print the numbers from 0 to 9 in order, and then back down to 0. You will need two while loops.

In fact, this use of a while loop (where we increment a counter variable each time until it reaches a certain value) occurs so often that C++ has a special way of writing it - a for loop. The general form is:

for ( int i = 0; i < N; i++ )
{
// code
}


Here, N is replaced with any value (such as 10, 2*5, or the name of an integer variable). The code inside the brackets { } is repeatedly executed until i < N is true - i.e., when the value of i reaches N, at which point the for loop code is skipped. Often, one will write i <= N instead, so the code will be executed until i has value greater than N. And of course, we can change 0 to any other value that we want i to have intially.

Let us see an example of a for loop summing the numbers from 0 to 10, and printing out the value:

#include
using namespace std;

int main()
{
int sum = 0;
for ( int i = 0; i <= 10; i++ )
{
sum = sum + i;
}
cout << sum << endl;
}


Exercise: Modify the above program:

1. So that it sums the squares from 0 to 10.
2. Add an integer variable called N with some initial value (such as 100), and change the code so that it sums the squares from 0 to N.

Collatz conjecture states that the following process always stops for all initial values of n:

1. Take a whole number n greater than 0.
2. If n is even, then halve it. Otherwise, set its value to 3n+1.
3. If n now has value 1, then stop. Otherwise go to step 2.

Exercise: Write a C++ program to test the Collatz conjecture, that prints out n at every iteration (we give a solution program below - but try writing one first!).

Solution:

#include
using namespace std;

int main()
{
int n = 25;
while ( n != 1 )
{
cout << n << endl;

bool isEven = n%2 == 0;
if ( isEven )
{
n = n/2;
}
else
{
n = 3*n + 1;
}
}
}


Exercise: Write a C++ program that implements Euclid's algorithm.

## Functions

At its simplest, a function is a way of grouping together a collection of instructions so that they can be repeatedly executed. Each function has a name (these have the same rules as variables names, so they are case sensitive; allow both letters, numbers and _, and cannot start with a number). At the top of the C++ program we "declare" a function, which tells the compiler that it exists (otherwise when the function name occured, the compiler would not know what it meant). Then somewhere in the program, we "define" the function, i.e., write the instructions for the function. When we want to execute the instructions in the function, we call it be writing its name (as will be seen).

Let's see an example. We write a function that prints out the numbers from 1 to 9, called countToTen. First, we need to include the following line of code somewhere at the top of the program to define the function:

void countToNine();


The void keyword is there to say that the function does not return a value - more on this soon. The () will be explained shortly as well, and of course the semicolon ; is needed as the end of the instruction.

And to define the function, we include the following block of code (note that this time, we do not include a semicolon at the end of the first line):

void countToNine()
{
// code
}


Here, // code is replaced with the code to be executed when the function is called. As you can see, the form is very similar to out int main() { ... } - this is because "main" is in fact the special function that the computer calls. When we want to call the function, we write countToTen();. Let's see a complete program which calls this function twice. Try running it.

#include
using namespace std;

void countToNine();

int main()
{
countToNine();
countToNine();
}

void countToNine()
{
for ( int i = 1; i <= 9; i++ )
{
cout << i;
}
cout << endl;
}


These are called functions because they can behave like mathematical functions - they can have input values and / or an output value.

To declare a function with a set of input variables (which can be any of the variable types we have seen so far), we list these types inside the brackets ( ) in the declaration, separated by commas (we can also include names for these variables, which are helpful for descriptive purposes).

Let's modify the countToNine function above so that it has an input value (which we call N), and prints the numbers from 1 to N. We declare the function as follows (changing its name):

void countToN( int N );


We similarly define the function, with the 9 in the for loop replaced by N. To call the function with value, say, 5, we write "countToN(5);". If we have an integer variable called x, we can use the value of x as an input by writing "countToN(x);". Let's put this together to form a complete program - try guessing what the following program does, before running it!.

#include
using namespace std;

void countToN( int N );

int main()
{
for ( int i = 1; i <= 9; ++i )
{
countToN( i );
}
}

void countToN( int N )
{
for ( int i = 1; i <= N; i++ )
{
cout << i;
}
cout << endl;
}


To declare a function with an output value (called returning a value), we replace the void keyword with the value type. For example, if we wanted to return a decimal number, we would replace void with float. Inside the function, when we want to return from the function to where the function was called from, we write "return value;", where value is replaced by the value to be returned (such as 5, or x).

Let's construct a function called gcd that has two input values (which we will call a and b), and (crudely) calculates their greatest commond divisor, and returns the value. As described above, we declare the function as

int gcd( int a, int b );


And for the definition of the function, we use a similar format (again this time, without the semicolon at the end of the first line):

int gcd( int a, int b )
{
while ( a != b )
{
if ( a > b )
{
a = a - b;
}
else
{
b = b - a;
}
}
return a;
}


Exercise: How and why does the algorithm given in the above function work?

To call the function, we write, for example, gcd( 168, 120 ). This is then treated as an integer, whose value is the value returned - so we can treat it like any other integer. For example, we can write "int x = gcd( 168, 120 );" to create an integer with this value. Or we could write "cout << gcd( 168, 120 ) << endl;". Let's put this together in a program:

#include
using namespace std;

int gcd( int a, int b );

int main()
{
int x = gcd( 168, 120 );
cout << "The greatest common divisor of 168 and 120 is " << x << endl;

x = gcd( 78, 114 );
cout << "The greatest common divisor of 78 and 114 is " << x << endl;
}

int gcd( int a, int b )
{
while ( a != b )
{
if ( a > b )
{
a = a - b;
}
else
{
b = b - a;
}
}
return a;
}


Exercise: Change the code in the gcd function so that it uses Euclids algorithm, which is computationally more efficient.

Exercise: Write a function that takes two integers a and b, and returns the value of $a^b$.

## Other maths functionality

We have covered the basic functionality of C++. C++ also comes with a whole range of predefined functions - for example, the common mathematical functions such as sin, cos, and square root, and functions for generating random numbers.

### Common maths functions

To make use of the mathematical functions, we write "#include " somewhere at the top of the program - this tells the compiler about these functions (what their names are, what inputs they take, what outputs they give). Most of the mathematical functions have float as their input and output type. The trignometric functions use radians as their input instead of degrees, and the log function is base e. Here's a short program demonstrating the use of some of these functions.

#include
#include
using namespace std;

int main()
{
// x is initialized with the value of sin(1).
float x = sin( 1 );
cout << "sin(1)=" << x << endl;

// x now gets the value 3^5.
x = pow( 3.0, 5 );
cout << "3^5=" << x << endl;

// x is now log base e of 20, or ln(20).
x = log( 20 );
cout << "ln(20)=" << x << endl;

// x is now square root of 25
x = sqrt( 25 );
cout << "sqrt(25)=" << x << endl;
}


The most commonly used maths functions are:

• cos, sin, tan - the trigonometric functions.
• acos, asin, atan - the inverse trigonometric functions.
• cosh, sinh, tanh - the hyperbolic functions.
• exp - the exponential function (for example, exp(10) has value $e^10$).
• log, log10 - the logarithmic functions to base e and base 10 respectively.
• pow - raise to a power (so pow(a,b) is $a^b$).
• sqrt - square root.
• ceil, floor - round a number up or down (for example, ceil(2.4) = 3 and floor(9.8) = 9).
• fabs - compute the absolute value (for example, fabs(-3.4) = 3.4).

### Random numbers

To make use of random numbers, we need to include the library "cstdlib", so write #include at the top of the program. Then the rand() function returns a random positive integer between 0 and RAND_MAX (RAND_MAX is a predefined constant that is available in your program when the library cstdlib is included).

To turn this into a floating point number between 0 and 1, called x, we would write:

float x = float(rand()) / RAND_MAX;


This contains some new code - the float(rand()) turns the integer returned by rand() into a floating point number with the same value. This is necessary since if we divide two integers, then the part after the decimal point is discarded. Here's an example of a program generating 10 random numbers between 0 and 1.

#include
#include
using namespace std;

int main()
{
for ( int i = 0; i < 10; i++ )
{
float x = float(rand()) / RAND_MAX;
cout << "x has value " << x << endl;
}
}


Exercise: How would you generate a random integer between 1 and 10?

Exercise: Use random numbers and Buffon's needle to generate an estimate for pi.