Thread: 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?

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;

}