you don't need loops or recursion... just plain common sense.



edit: oh wait, you want like, every possible way to make change. ok, nevermind that.

This post was edited by irimi on Nov 29 2012 01:30pm

haha yeah...also the assignment has to be done recursively >.<

this problem definitely lends itself to recursion then. think about it abstractly --

base case:
1 cent
--> all the ways to make change (1) == 1 penny

recursive case:
--> n + 1 cents
--> all the ways to make change (n+1) == { all the ways to make change (n) + 1 penny } + if ((n+1)%25 == 0) { ((n+1)/25 quarters) } + if ((n+1)%5 == 0) {(n+1)/5 nickels} + if ((n+1)%10 == 0) {(n+1)/10 dimes}

edit: there's one corner case i'm missing - e.g. 24 cents -> 25 cents misses the 1 dime 3 nickels case ; so a slight modification to the recursive case is needed

This post was edited by irimi on Nov 29 2012 01:54pm

here's the text version: xD
easiest is when you first code the lowest part. as example, what if the recursive function gets a "1"? then it is easy to tell what it should do: increase the counter for possibilities by only 1 and return 0.
also easy is when the recursive function gets a 2. because 2 is not dividable by 5, the function calls itself but with a "1", and also increase the counter for possibilities. the returnvalue of the just called recursive function must then be added, cause that's the value for all possibilities of the sub-problem ^^
ok that was not well formulated, but maybe you get the point
think what input values and what output values must be important for your recursive function

hmm, you also need to define:
is "1 cent and then 5 cents" the same as "first 5 cents and then 1 cent"?

edit: blah, this can be simplified

This post was edited by irimi on Nov 29 2012 02:18pm

but the brute force way would be to lay out the base cases for 1, 5, 10, 25 cents. then for your recursive case --

n=k+1

if n|25 --> change(n-25) + change(25)
if n|10 --> change(n-10) + change(10)
if n|5 --> change(n-5) + change(5)
else: change(n-1) + change(1)

i think this is actually the correct answer, but there's got to be a more elegant way to lay out the base cases. the base cases aren't actually that bad... until you get to 25 cents.

This post was edited by irimi on Nov 29 2012 02:19pm

If I could some how get the cases to run at the same time for results because the problem is that case 2 is always filling in with nickels so a result like 1 dime and 7 pennies for the entry 17 will never result. what I want to do is have case 3 run and then branch directly to case 1 and also branch directly to
case 2 and then case 1

is there any way to do this?

This post was edited by Nom_Nomz on Nov 29 2012 02:47pm

yeah i'm not even bothering with looking at your code. i'm kind of assuming it's wrong.

you have to figure out the abstract solution before implementing it. doing it in reverse is a guaranteed waste of time.

---

in any case, here's a somewhat simplistic way of looking at the base cases -- they may be generalizable so that you can reduce some of the base case into your recursive case:

n = 1 cent --> 1 penny
n = 5 cents --> 5x change(1) + 1 nickel
n = 10 cents --> [ change(5) * change(5) ] + 1 dime
n = 25 cents --> [ change(10)*change(10)*change(5) ] + 1 quarter

the * is basically where you take the solution for 1 and cross-multiply it with the other;
i.e. for 10 cents, change(5) = [5 pennies, 1 nickel]
so change(10) = [5 pennies, 1 nickel] * [5 pennies, 1 nickel ] + 1 dime --> [ 10 pennies, 5 pennies & 1 nickel, 2 nickels ] + 1 dime

This post was edited by irimi on Nov 29 2012 03:09pm

I have the solution and it works I just need to know if/how you can branch a a case to another while keeping the course.

my code at the moment removes quarters > dimes > nickels > pennies

the problem is that it will never give a solution like quarters + pennies or dimes + pennies

I have checked to see if I comment out the dimes and nickels and it works to give me quarters + pennies so if I could find a way to have it branch to case 1 for example while retain it's initial order I'd be set.

basically the only thing my code cannot do are cases for the following

Quarters Dimes Pennies

Dimes Pennies

Quarters Pennies

I am pretty sure

The solution is easy enough to understand it's just the implementation that I really am having trouble with.

I think I am just going to make special functions with their own switch statements in the different orders that return an int of ways to add to the sum, it's ugly but it works.

This post was edited by Nom_Nomz on Nov 29 2012 03:30pm

yeah. so i read your post a few times, and you're not making a lot of sense in what you just said.

in any case, those don't look like corner cases to me. they look like inherent flaws in your logic.