PDA

View Full Version : Problem

Nick
08-27-2001, 11:23 AM
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

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?

Nick
08-29-2001, 09:12 PM
No one tried!

// 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;

}

SilentStrike
08-29-2001, 11:40 PM
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)

;