Thread: Problem

  1. #1
    Blank
    Join Date
    Aug 2001
    Posts
    1,034

    Problem

    Ok here's a problem I asked following the demise of the old c board.

    Given that you have a unlimited amount of pennies, nickles, dimes, quaters, halve dollars. To find all the ways that you can make change for a given amount one can write



    Code:
    int count_change(int amount)
    
    {
    
        return cc(amount, 4);
    
    }
    
    
    
    int cc(int amount, int coin)
    
    {
    
        static const int denom[] = {1, 5, 10, 25, 50};
    
    
    
        if (amount == 0) 
    
            return 1;
    
        else if (coin < 0 || amount < 0) 
    
            return 0;
    
    
    
        return cc(amount - denom[coin], coin) + cc(amount, coin - 1);
    
    }


    My question is what is the order of growth (in Big Oh Notation) of the

    number of steps? And show?

  2. #2
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    No one tried!



    Code:
    // mimic recursive function
    
    int count_change(int amount)
    
    {
    
        int i, j, k, m, n;
    
        int c = 0;
    
    
    
        for (i = amount; i > 0; i -= 50) {
    
            for (j = i; j > 0; j -= 25) {
    
                for (k = j; k > 0; k -= 10) {
    
                    for (m = k; m > 0; m -= 5) {
    
                        for (n = m; n > 0; n -= 1) 
    
                            ;
    
                        if (n == 0) 
    
                            ++c;
    
                    }
    
                    if (m == 0) 
    
                        ++c;
    
                }
    
                if (k == 0) 
    
                    ++c;
    
            }
    
            if (j == 0) 
    
                ++c;
    
        }
    
        if (i == 0) 
    
            ++c;
    
    
    
        return c;
    
    }

  3. #3
    geek SilentStrike's Avatar
    Join Date
    Aug 2001
    Location
    NJ
    Posts
    1,141
    So it's running time is O(N^4)?

    I was messing with it a little, but couldn't do anything definitive.

    BTW, what is this loop doing?

    for (n = m; n > 0; n -= 1)

    ;
    Prove you can code in C++ or C# at TopCoder, referrer rrenaud
    Read my livejournal

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help understanding a problem
    By dnguyen1022 in forum C++ Programming
    Replies: 2
    Last Post: 04-29-2009, 04:21 PM
  2. Memory problem with Borland C 3.1
    By AZ1699 in forum C Programming
    Replies: 16
    Last Post: 11-16-2007, 10:22 AM
  3. Someone having same problem with Code Block?
    By ofayto in forum C++ Programming
    Replies: 1
    Last Post: 07-12-2007, 08:38 AM
  4. A question related to strcmp
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2007, 02:51 PM
  5. WS_POPUP, continuation of old problem
    By blurrymadness in forum Windows Programming
    Replies: 1
    Last Post: 04-20-2007, 06:54 PM