UCL WIKI

UCL Logo
Child pages
  • Session 1 - Control structure
Skip to end of metadata
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

Show/Hide latex error

Each Fibonacci number is defined by the following recursion relation:

LaTeX Markup problem

Show/Hide latex markup

Show/Hide latex error

with initial conditions:

LaTeX Markup problem

Show/Hide latex markup

Show/Hide latex error

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

Show/Hide latex error

and
LaTeX Markup problem

Show/Hide latex markup

Show/Hide latex error

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

Show/Hide latex error

.

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

Show/Hide latex error

. 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

Show/Hide latex error

where
LaTeX Markup problem

Show/Hide latex markup

Show/Hide latex error

is the number of points to generate. The program should then produce
LaTeX Markup problem

Show/Hide latex markup

Show/Hide latex error

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

    Show/Hide latex error

    .
  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

    Show/Hide latex error

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

Show/Hide latex error

is using the Monte Carlo method devised by Nicholas Constantine Metropolis. It goes as follows.

Start with a circle of radius

LaTeX Markup problem

Show/Hide latex markup

Show/Hide latex error

centred on the origin. The circle sits within a square of dimension
LaTeX Markup problem

Show/Hide latex markup

Show/Hide latex error

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

Show/Hide latex error

So to get some

LaTeX Markup problem

Show/Hide latex markup

Show/Hide latex error

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

Show/Hide latex error

.

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

    Show/Hide latex error

    !

Extension to visualise output:

  1. Ask the user how many points they want and calculate
    LaTeX Markup problem

    Show/Hide latex markup

    Show/Hide latex error

  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

    Show/Hide latex error

    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.