Thread: recoursive function

  1. #1
    Registered User
    Join Date
    Dec 2001
    Posts
    60

    recoursive function

    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?

  2. #2
    Hamster without a wheel iain's Avatar
    Join Date
    Aug 2001
    Posts
    1,385
    That is 100% a homework question, write some code then post it, at least attempt it.
    Monday - what a way to spend a seventh of your life

  3. #3
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    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.

  4. #4
    ....
    Join Date
    Aug 2001
    Location
    Groningen (NL)
    Posts
    2,380
    Perhaps it's recursion where Mecnels is struggling with.

    A very easy example of an recursive function:

    Code:
    int fac (int n)
    {
        if (n == 1)
            return 1;
        else
            return (n * fac (n -1));
    }
    Desiging a recursive function consists of two steps. First there must be an end-step.

    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)

  5. #5
    Unregistered
    Guest
    If I remember correctly, the answer is all solutions to this equation.
    x + 5y + 10z = 120
    0 <= x
    0 <= y
    0 <= z

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Post your games here...
    By Hammer in forum Game Programming
    Replies: 132
    Last Post: 02-28-2013, 09:29 AM
  2. dllimport function not allowed
    By steve1_rm in forum C++ Programming
    Replies: 5
    Last Post: 03-11-2008, 03:33 AM
  3. We Got _DEBUG Errors
    By Tonto in forum Windows Programming
    Replies: 5
    Last Post: 12-22-2006, 05:45 PM
  4. Game Pointer Trouble?
    By Drahcir in forum C Programming
    Replies: 8
    Last Post: 02-04-2006, 02:53 AM
  5. <Gulp>
    By kryptkat in forum Windows Programming
    Replies: 7
    Last Post: 01-14-2006, 01:03 PM