Suppose you've got some money, f.e. 120$
There are,f.e. 3 different coins, say 1$, 5$, and
10$. The task is to write a program with a recoursive function that calculates how many different ways there are to have 120$.
F.e. 10 times 10$ and 4 times 5$ would be 120$,
so increase a counter.
The final return value of the recoursive SolveIt()
function is the number of different ways to have a certain amount of money given the number of different coins and their values.
Can you solve this problem (it's difficult), is there an algorithm?
That is 100% a homework question, write some code then post it, at least attempt it.
This problem isn't too hard.
The number of ways to change an amount with coins 1, 5, 10, 25 is
the number of ways to change the amount with 1, 5, 10 plus the number of ways to change (amount-25) with 1, 5, 10, 25.
Perhaps it's recursion where Mecnels is struggling with.
A very easy example of an recursive function:
Desiging a recursive function consists of two steps. First there must be an end-step.
int fac (int n)
if (n == 1)
return (n * fac (n -1));
n! = n x (n -1) x (n-2) x .. x 2 x 1
You can see, if (n == 1), then the end is reached. In each other case, you have to perform the recursion step. In this example it is easy to see that:
n! = n x (n - 1)!
n! = n x (n - 1) x (n - 2)!
So the recursion step is:
n x (n - 1)!
Or in C:
n x fac (n - 1)
If I remember correctly, the answer is all solutions to this equation.
x + 5y + 10z = 120
0 <= x
0 <= y
0 <= z