# UCL WIKI

##### Child pages
• Session 1 - Control structure
Go to start of banner

# Session 1 - Control structure

Go to start of metadata

Contents:

### Fibonacci series

The Fibonacci series is the numbers that follow the integer sequence:

 LaTeX Markup problem Show/Hide latex markup \documentclass{article} \usepackage{amsmath} \usepackage{amsthm} \usepackage{amssymb} \usepackage{bm} \newcommand{\mx}[1]{\mathbf{\bm{#1}}} % Matrix command \newcommand{\vc}[1]{\mathbf{\bm{#1}}} % Vector command \newcommand{\T}{\text{T}} % Transpose \pagestyle{empty} \begin{document} $1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...$ \end{document}  Show/Hide latex error Unable to find DVI conversion log file.

Each Fibonacci number is defined by the following recursion relation:

 LaTeX Markup problem Show/Hide latex markup \documentclass{article} \usepackage{amsmath} \usepackage{amsthm} \usepackage{amssymb} \usepackage{bm} \newcommand{\mx}[1]{\mathbf{\bm{#1}}} % Matrix command \newcommand{\vc}[1]{\mathbf{\bm{#1}}} % Vector command \newcommand{\T}{\text{T}} % Transpose \pagestyle{empty} \begin{document} $F_n = F_{n-1} + F_{n-2}$ \end{document}  Show/Hide latex error Unable to find DVI conversion log file.

with initial conditions:

 LaTeX Markup problem Show/Hide latex markup \documentclass{article} \usepackage{amsmath} \usepackage{amsthm} \usepackage{amssymb} \usepackage{bm} \newcommand{\mx}[1]{\mathbf{\bm{#1}}} % Matrix command \newcommand{\vc}[1]{\mathbf{\bm{#1}}} % Vector command \newcommand{\T}{\text{T}} % Transpose \pagestyle{empty} \begin{document} $F_0 = 0, F_1 = 1.$ \end{document}  Show/Hide latex error Unable to find DVI conversion log file.

As with any recursion relation this can be implemented by using recursive functions in C++.

Implement a program that takes in a number, n, and print to screen the the n th element of the series.
Now loop over and print all the numbers in the series up to and including n.

### It's all a bit random

Write a function that takes a two numbers,

 LaTeX Markup problem Show/Hide latex markup \documentclass{article} \usepackage{amsmath} \usepackage{amsthm} \usepackage{amssymb} \usepackage{bm} \newcommand{\mx}[1]{\mathbf{\bm{#1}}} % Matrix command \newcommand{\vc}[1]{\mathbf{\bm{#1}}} % Vector command \newcommand{\T}{\text{T}} % Transpose \pagestyle{empty} \begin{document} $x_0$ \end{document}  Show/Hide latex error Unable to find DVI conversion log file.
and
 LaTeX Markup problem Show/Hide latex markup \documentclass{article} \usepackage{amsmath} \usepackage{amsthm} \usepackage{amssymb} \usepackage{bm} \newcommand{\mx}[1]{\mathbf{\bm{#1}}} % Matrix command \newcommand{\vc}[1]{\mathbf{\bm{#1}}} % Vector command \newcommand{\T}{\text{T}} % Transpose \pagestyle{empty} \begin{document} $x_1$ \end{document}  Show/Hide latex error Unable to find DVI conversion log file.
and returns a random number in that range. To make things easy for the users of the function make sure it works correctly even if
 LaTeX Markup problem Show/Hide latex markup \documentclass{article} \usepackage{amsmath} \usepackage{amsthm} \usepackage{amssymb} \usepackage{bm} \newcommand{\mx}[1]{\mathbf{\bm{#1}}} % Matrix command \newcommand{\vc}[1]{\mathbf{\bm{#1}}} % Vector command \newcommand{\T}{\text{T}} % Transpose \pagestyle{empty} \begin{document} $x_1 > x_0$ \end{document}  Show/Hide latex error Unable to find DVI conversion log file.
.

Now write an overloaded function (see the lectures if you can't remember what this means) that takes no parameters and returns a random number in the range

 LaTeX Markup problem Show/Hide latex markup \documentclass{article} \usepackage{amsmath} \usepackage{amsthm} \usepackage{amssymb} \usepackage{bm} \newcommand{\mx}[1]{\mathbf{\bm{#1}}} % Matrix command \newcommand{\vc}[1]{\mathbf{\bm{#1}}} % Vector command \newcommand{\T}{\text{T}} % Transpose \pagestyle{empty} \begin{document} $0 \rightarrow 1$ \end{document}  Show/Hide latex error Unable to find DVI conversion log file.
. You may want to reuse the function you've already written.

Finally write a program that asks for three numbers,

 LaTeX Markup problem Show/Hide latex markup \documentclass{article} \usepackage{amsmath} \usepackage{amsthm} \usepackage{amssymb} \usepackage{bm} \newcommand{\mx}[1]{\mathbf{\bm{#1}}} % Matrix command \newcommand{\vc}[1]{\mathbf{\bm{#1}}} % Vector command \newcommand{\T}{\text{T}} % Transpose \pagestyle{empty} \begin{document} $x_0, x_1, n$ \end{document}  Show/Hide latex error Unable to find DVI conversion log file.
where
 LaTeX Markup problem Show/Hide latex markup \documentclass{article} \usepackage{amsmath} \usepackage{amsthm} \usepackage{amssymb} \usepackage{bm} \newcommand{\mx}[1]{\mathbf{\bm{#1}}} % Matrix command \newcommand{\vc}[1]{\mathbf{\bm{#1}}} % Vector command \newcommand{\T}{\text{T}} % Transpose \pagestyle{empty} \begin{document} $n$ \end{document}  Show/Hide latex error Unable to find DVI conversion log file.
is the number of points to generate. The program should then produce
 LaTeX Markup problem Show/Hide latex markup \documentclass{article} \usepackage{amsmath} \usepackage{amsthm} \usepackage{amssymb} \usepackage{bm} \newcommand{\mx}[1]{\mathbf{\bm{#1}}} % Matrix command \newcommand{\vc}[1]{\mathbf{\bm{#1}}} % Vector command \newcommand{\T}{\text{T}} % Transpose \pagestyle{empty} \begin{document} $n$ \end{document}  Show/Hide latex error Unable to find DVI conversion log file.
random numbers and print them to the screen.

To get random numbers you can use the rand() function. See here for a description. Basically rand gives back an integer from 0 to RAND_MAX so to get a floating point random number just divide the result by RAND_MAX (remember to convert everything to doubles!) which will give you a floating point number from 0 to 1. To use rand you have to include the <cstdlib> header.

### Lottery odds

The UK lottery is a so called 6/49 game because the player chooses 6 numbers from a range of 49. The odds of choosing all 6 numbers correctly and winning the jackpot can be calculated as follows:

1. The odds of choosing the first first ball correctly are 1 in 49.
2. Now only 48 balls remain so the chance of guessing this one correctly is 1 in 48.
3. And so on until all six balls are selected. As the probabilities are independent the probability of guessing all balls correctly is 1 in 49 x 48 x 47 x 46 x 45 x 44 which can be written as
 LaTeX Markup problem Show/Hide latex markup \documentclass{article} \usepackage{amsmath} \usepackage{amsthm} \usepackage{amssymb} \usepackage{bm} \newcommand{\mx}[1]{\mathbf{\bm{#1}}} % Matrix command \newcommand{\vc}[1]{\mathbf{\bm{#1}}} % Vector command \newcommand{\T}{\text{T}} % Transpose \pagestyle{empty} \begin{document} \begin{equation*}\frac{49!}{(49 - 6)!}\end{equation*} \end{document}  Show/Hide latex error Unable to find DVI conversion log file.
.
4. However this calculation assumes that the order of numbers matters, which it does't, so we need to further divide by the number of ways 6 numbers can be arranged i.e. 6!. Giving the final solution as the binomial coefficient:
 LaTeX Markup problem Show/Hide latex markup \documentclass{article} \usepackage{amsmath} \usepackage{amsthm} \usepackage{amssymb} \usepackage{bm} \newcommand{\mx}[1]{\mathbf{\bm{#1}}} % Matrix command \newcommand{\vc}[1]{\mathbf{\bm{#1}}} % Vector command \newcommand{\T}{\text{T}} % Transpose \pagestyle{empty} \begin{document} \begin{equation*} \binom nk = \frac{n!}{k!(n - k)!} \end{equation*} \end{document}  Show/Hide latex error Unable to find DVI conversion log file.

Go to code/1_control_structure/exercises/lottery_odds.cpp. Here you will find a skeleton code with the factorial function from lectures. Make the following changes:

1. Write a combination function that takes two integer values, n and k, and calculates the binomial coefficient.
2. In the main function, ask the user for two numbers, the total number of balls and the number to be chosen.
3. Check that the number to be chosen is less than or equal to the number of balls, otherwise print an error message and return.
4. Calculate the users odds and print them to the screen.
5. Go to this website http://www.funny2.com/odds.htm or anywhere else you can get some interesting odds. After printing out the users odds, check if they have a better chance of, say, being hit by lightning and inform them of that fact. Now, find something more likely, say, winning an Olympic gold medal. If the users odds are somewhere between those of being struck by lightning and winning a gold medal then inform them of that fact.

### Fractal forest

For this exercise, we'll get graphical output. We need to set this up quickly. Save your work and close your Putty session. Run putty again, click on your socrates profile, then click "Load". In the left panel, navigate to "Connection" > "SSH" > "X11" and check the "Enable X11 forwarding" box. Now click on session, then again on your socrates profile and finally hit "Save".

Now we need to run Exceed. Search for "Exceed" in the start menu by typing in the search bar and click on its icon. That's it! You will need to run Exceed if you want to display windows from a remote machine. If you saved your socrates putty profile, you don't need to enable X11 in putty again.

Let's start the exercise. Go to code/1_control_structure/exercises/fractal_forest.cpp. Here you will find a skeleton code for drawing a Fractal tree. Use recursive programming to create a branching tree and visualise the output in gnuplot.

Once you have a version that you're happy with compile it.

Now, open another terminal at the same path. Start your program with:

[your_program_name] > fratal_forest.dat


In the other terminal type

gnuplot fractal_forest.plt


You should see your first tree appear. Draw some more, see what happens.

Change you code, some things to try:

1. Use a random branching angle in a sensible range.
2. Use a random branching length coefficient.

The image above was generated using a random angle between 0 and pi/5 radians +/- of the parent branch angle and a random length of 0 to 2/3 times the length of the parent branch.

### Anyone for Pi?

One way to calculate

 LaTeX Markup problem Show/Hide latex markup \documentclass{article} \usepackage{amsmath} \usepackage{amsthm} \usepackage{amssymb} \usepackage{bm} \newcommand{\mx}[1]{\mathbf{\bm{#1}}} % Matrix command \newcommand{\vc}[1]{\mathbf{\bm{#1}}} % Vector command \newcommand{\T}{\text{T}} % Transpose \pagestyle{empty} \begin{document} $\pi$ \end{document}  Show/Hide latex error Unable to find DVI conversion log file.
is using the Monte Carlo method devised by Nicholas Constantine Metropolis. It goes as follows.

 LaTeX Markup problem Show/Hide latex markup \documentclass{article} \usepackage{amsmath} \usepackage{amsthm} \usepackage{amssymb} \usepackage{bm} \newcommand{\mx}[1]{\mathbf{\bm{#1}}} % Matrix command \newcommand{\vc}[1]{\mathbf{\bm{#1}}} % Vector command \newcommand{\T}{\text{T}} % Transpose \pagestyle{empty} \begin{document} $r = 1$ \end{document}  Show/Hide latex error Unable to find DVI conversion log file.
centred on the origin. The circle sits within a square of dimension
 LaTeX Markup problem Show/Hide latex markup \documentclass{article} \usepackage{amsmath} \usepackage{amsthm} \usepackage{amssymb} \usepackage{bm} \newcommand{\mx}[1]{\mathbf{\bm{#1}}} % Matrix command \newcommand{\vc}[1]{\mathbf{\bm{#1}}} % Vector command \newcommand{\T}{\text{T}} % Transpose \pagestyle{empty} \begin{document} $l = 2r = 2$ \end{document}  Show/Hide latex error Unable to find DVI conversion log file.
also centred on the origin like so:

The ratio of the areas of the circle and square is given by:

 LaTeX Markup problem Show/Hide latex markup \documentclass{article} \usepackage{amsmath} \usepackage{amsthm} \usepackage{amssymb} \usepackage{bm} \newcommand{\mx}[1]{\mathbf{\bm{#1}}} % Matrix command \newcommand{\vc}[1]{\mathbf{\bm{#1}}} % Vector command \newcommand{\T}{\text{T}} % Transpose \pagestyle{empty} \begin{document} \begin{equation*} \rho = \frac{\text{Area of circle}}{\text{Area of square}} = \frac{\pi r^2}{(2r)^2} = \frac{\pi}{4} \end{equation*} \end{document}  Show/Hide latex error Unable to find DVI conversion log file.

So to get some

 LaTeX Markup problem Show/Hide latex markup \documentclass{article} \usepackage{amsmath} \usepackage{amsthm} \usepackage{amssymb} \usepackage{bm} \newcommand{\mx}[1]{\mathbf{\bm{#1}}} % Matrix command \newcommand{\vc}[1]{\mathbf{\bm{#1}}} % Vector command \newcommand{\T}{\text{T}} % Transpose \pagestyle{empty} \begin{document} $\pi$ \end{document}  Show/Hide latex error Unable to find DVI conversion log file.
all we have to do is find this ratio and multiply by 4. Simple...

But wait, how do we get the areas, and therefore ratio, without using the formulas?

This is where Monte Carlo comes in handy. If we start placing random points within the square and measure what proportion also fall within the circle then we'll get a value that converges to the ratio and we can calculate

 LaTeX Markup problem Show/Hide latex markup \documentclass{article} \usepackage{amsmath} \usepackage{amsthm} \usepackage{amssymb} \usepackage{bm} \newcommand{\mx}[1]{\mathbf{\bm{#1}}} % Matrix command \newcommand{\vc}[1]{\mathbf{\bm{#1}}} % Vector command \newcommand{\T}{\text{T}} % Transpose \pagestyle{empty} \begin{document} $pi$ \end{document}  Show/Hide latex error Unable to find DVI conversion log file.
.

The easiest way to do this is to just consider a quarter of the circle like so:

Steps for writing your program:

1. Get one of your random functions that gives a random number between 0 and 1.
2. Decide what the number of random points to use
3. Loop over that many times finding two random points, x and y.
4. Check if the point lies within the circle, if so add it to a counter that keeps track of this.
5. After all the loops divide the number that fell in the circle by the total number of points and multiply by 4. Voila:
 LaTeX Markup problem Show/Hide latex markup \documentclass{article} \usepackage{amsmath} \usepackage{amsthm} \usepackage{amssymb} \usepackage{bm} \newcommand{\mx}[1]{\mathbf{\bm{#1}}} % Matrix command \newcommand{\vc}[1]{\mathbf{\bm{#1}}} % Vector command \newcommand{\T}{\text{T}} % Transpose \pagestyle{empty} \begin{document} $\pi$ \end{document}  Show/Hide latex error Unable to find DVI conversion log file.
!

Extension to visualise output:

1. Ask the user how many points they want and calculate
 LaTeX Markup problem Show/Hide latex markup \documentclass{article} \usepackage{amsmath} \usepackage{amsthm} \usepackage{amssymb} \usepackage{bm} \newcommand{\mx}[1]{\mathbf{\bm{#1}}} % Matrix command \newcommand{\vc}[1]{\mathbf{\bm{#1}}} % Vector command \newcommand{\T}{\text{T}} % Transpose \pagestyle{empty} \begin{document} $\pi$ \end{document}  Show/Hide latex error Unable to find DVI conversion log file.
2. For each point print the coordinates to the screen line by line in the format: x y
3. Print the current value of
 LaTeX Markup problem Show/Hide latex markup \documentclass{article} \usepackage{amsmath} \usepackage{amsthm} \usepackage{amssymb} \usepackage{bm} \newcommand{\mx}[1]{\mathbf{\bm{#1}}} % Matrix command \newcommand{\vc}[1]{\mathbf{\bm{#1}}} % Vector command \newcommand{\T}{\text{T}} % Transpose \pagestyle{empty} \begin{document} $\pi$ \end{document}  Show/Hide latex error Unable to find DVI conversion log file.
to the screen prefixed the a hash symbol: #
4. Now loop around and ask them again how many points they want
5. If the user enters 0 points, then exit
6. (Prefix any other screen output (except the coordinates) with a hash symbol)

A do loop allows you to do stuff before the loop condition is evaluated.

To visualise open two terminals and run your program like so:

[your_program_name] > pi.dat


In the other terminal type:

gnuplot pi.plt


How good is your value? How many points to you have to go to?

### Pong - gaming classic.

Go to code/1_control_structure/exercises/pong.cpp. Here you will find a skeleton code for a pong game. Compile it by typing:

g++ pong.cpp -lcurses -o pong


Now try running it running in:

pong


You will see two paddles and a ball that quickly moves off the screen.

##### Step 1 - Contain the ball

To keep the ball on the screen we will use the following approach:

1. If the ball position is > XMAX or < 0 negate the velocity.
2. Similar for Y.

Try it, does it stay on screen?

##### Step 2 - Collision detection

We need to detect if the ball has hit a paddle.

We can do this at the same time as detecting collision with the boundaries. If the ball is about to go off screen:

1. Check if is not in the range bottomPaddleX - PADDLE_HALF_SIZE -> bottomPaddleX + PADDLE_HALF_SIZE
2. If not, then the ball has gone out and we should reset. Call
reset(topPaddleX, bottomPaddleX, ballX, ballY);

to reset everything.
3. Do the same for Y
##### Step 3 - Scores: where it gets competitive

When you call reset, make sure to add a point to the opposite player.