Department of Engineering

1B C++ Computing

C++

Exercise 5

TASK DESCRIPTION

In this exercise you will write a C++ program that computes how many different ways coins can be used to make change for a given amount. For example, there are 4 ways of making change for 5p:

  • One 5p coin
  • Two 2p coins and one 1p coin
  • One 2p coin and three 1p coins
  • Five 1p coins

For larger values, there are many more ways of making change. You will compute the number of combinations using a recursive function -- a function that calls itself. You should read the total amount from standard input (cin) and output the number of ways to make change to standard output (cout).

SUGGESTIONS

For this exercise, use only the standard UK coins: 1p, 2p, 5p, 10p, 20p, 50p, 100p, and 200p. Compute all values in units of pence so that everything can be represented with integers. You'll want to store the coin values in an array or vector and refer to them by index, not value.

To solve the stated problem, consider the slightly constrained problem of determining how many ways to make change for an amount if the largest coin you can use is specified. For instance, with the example above of 5p, if the largest coin you can use is 2p, then there are only three ways of making change.

Here are the cases for how to make change for X pence if the largest coin you can use has index C:

  1. If C is not a valid coin index, there are zero ways to make change.
  2. If X < value(C), you can make change only using coins smaller than C
  3. If X == value(C), you can make change using exactly one C coin or with coins smaller than C
  4. Otherwise, let R = X - value(C) (so that R is the remaining amount after using one C coin).
    Then you have a choice: either use a C coin or not.
    • If you do, the number of ways of making change for X is the same as the number of ways for R.
    • If you don't, then you have to make change for X using only coins smaller than C.
    The total number of possibilities is the sum of these two options.

Call the function 'ways', which has two parameters: the amount 'X', and the largest coin to use 'C'. Notice that in all but the first case above, your function can call itself recursively in order to compute the result. For instance, considering only case (3) you could have

int ways(int X, int C) 
{
   ...
   // Case 3
   if( X == value(C))
       return 1 + ways(X,C-1);
   ...
}

The other cases can be treated similarly.

Notice that the function computes the result by making recursive calls to itself with different parameters.
You will want to store the coin values in a way that is easily indexed by C, the coin label. One way of structuring your program might be this:

#include <iostream>
using namespace std;

const int NUM_COINS = 8;
const int coins[NUM_COINS] = {1, 2, 5, 10, 20, 50, 100, 200};

int ways(int X, int C) 
{
	// ... 
}

int main()
{
	int X;
	cin >> X;

	// ...
}

The coins values are stored in a constant array, and the index (C) of the largest coin is NUM_COINS-1.

TESTING THE PROGRAM

Your program should read the X value (in pence) from cin, and output the number of ways to make change to cout. First try your program on small X values, for which you know the answer. For example, we know that there are 4 combinations for 5p, and you can easily compute that there are 11 combinations for 10p. Once you think it's working on these values, try larger ones, like 100. Finally, compute the number of possibilities for 500p (5 pounds).

Values for Testing

Pence102030405053
Ways to make Change1141109236451530

You'll find that for large values, like 1000, your program runs very slowly. This is because it's recomputing the same sub-problems over and over. This issue is resolved using a method called dynamic programming, by which your program remembers answers to problems it's already solved and doesn't recompute them when asked again. You don't need to do this for this exercise, but think about how you might accomplish this in your code.

  • © 2010 University of Cambridge Department of Engineering
    Information provided by Roberto Cipolla and Ethan Eade (Last updated: December 2010)