Problem

This is a discussion on Problem within the A Brief History of Cprogramming.com forums, part of the Community Boards category; Ok here's a problem I asked following the demise of the old c board. Given that you have a unlimited ...

  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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21