That's most likely the case but I dont know how to implement this any other way unfortunately

an example of what I was saying is this

my code runs cases in that order 4 3 2 1

when I input 17 cents to be processed I get every result except the one 1 dime + 7 pennies

If I remove case 4 and case 2 (the cases that process quarters and nickels) I get the missing result of 1 dime and 7 pennies

So what I wanted to do was run 4 3 2 1 and some how implement a way to run 3 and 1 alone 4 and 1 alone 4 3 1 alone and lastly 3 2 1 alone and then add them up this way and subtracting overlap?

I dont know I am pretty burnt out, probably overthinking the hell out o this... I appreciate the help though.

This post was edited by Nom_Nomz on Nov 29 2012 04:15pm

oftentimes the best way when you get stuck is to throw out everything and start from scratch. don't try to fix something that's broken -- just rewrite it.

look at the recursive solution that i most recently posted. it's mostly correct, though the case for making change for 25 cents is still a work in progress. once you get the base cases correct, implementing the recursion is absolutely trivial.

the code structure would look something like this:



This post was edited by irimi on Nov 29 2012 04:48pm

"...to find all the ways..."
so if you enter the number 17.... what should be the output? think about it... you'll see that 17 already has a very huge amount of possibilities...
here are just a few:


think about the possibilities... are you really so crazy that you need all those numbers in the RIGHT ORDER? I at least still don't know what you want... I understand Irmi and I also understand you... but your way won't work until you know what recursive means :/

I guess that this output is what you want for the number 17:
17:


or is it this version? (number of lines says how many possibilities, first row says how many cents, second one how many 5-cent pieces... and so on)


or is the output just a "6 possibilities for the change are possible" ?

YUP!

Order doesn't matter (thank god)

Also I'm not sure if this was obvious or not but I am coding in C at the moment if that makes a difference.

your short code block with all the 1's etc is what I am trying to get to at the moment.

I think my biggest problem right now is the act that my instructor gave me some starting hints and they just aren't working for me...let me know i you can explain them better?

Hints (not mandatory):
Here is the function description:
// Precondition: denomination = 1 (for penny), 2 (for nickel), 3 (for dime),
// or 4 (for quarter).
// Postcondition: If amount < 0, then 0 has been returned. Otherwise,
// the value returned is the number of ways that amount
// can be changed into coins whose denomination is no
// larger than denomination.
int ways (int amount, int denomination);
For the sake of simplifying the ways function, develop a coins function that returns the value of each
denomination. Thus, coins(1) returns 1, coins(2) returns 5, coins(3) returns 10, and coins(4) returns 25.

I understand recursion takes an input performs a reduction step and then calls itself using the result of that step ( on a very basic level) to some ending condition... at least that is what I think it means?

This post was edited by Nom_Nomz on Nov 29 2012 04:53pm

see the code i posted above.

as I mentioned before, a fairly simple relationship can be established from 1 cent to 5 cents to 10 cents.

1 cent = 1 penny
5 cents = 5 * [solution for 1 cent] + 1 nickel
10 cents = [solution for 5 cents] * [solution for 5 cents] + 1 dime

so I think by extension:
25 cents = [solution for 10 cents] * [solution for 10 cents] * [solution for 5 cents] + 1 quarter

but perhaps, it's easier to think of it this way:

25 cents = [solution for 15 cents] * [solution for 10 cents] + 1 quarter
which *then becomes*
25 cents = [solution for 10 cents] * [solution for 10 cents] * [solution for 5 cents] + 1 quarter

so in theory, the only thing you need in your base case... is to add the additional coin. the rest is just a matter of doing an i-j for loop to combine two subcases you get from subtracting the largest possible coin.

second attempt:


or something like that.

This post was edited by irimi on Nov 29 2012 05:11pm

yes, thats it. but you need a function, in which one you call the function itself...

if you would call in every function the function itself, the program would crash as soon as so many function are called that there is no more space available (wherever that space is doesn't matter)

so the function aborts at a certain time. when? as soon as there are no more possibilities for the sub-problem

so if i start with such a recursive function, i must give it the number for the remaining cash. the remaining cash is at the beginning 17

well, when the function gets 17, then it knows that it can't give a 25'er piece back... that would be too much.

so what does the function now? it opens the function itself for all the remaining possibilities...
those are:

the last line (17-25) isn't a possibility, because it gets negative... doesn't matter if you check it before you call the function or after that...

actually this is kind of annoying. this should be pretty easy to solve lol - kind of embarrassed that i haven't come up with a stupidly simple solution to this yet.

fucking combinatorics.

Yeah every time I think I've got it...I don't. tbh I'd rather take a kick to the nuts right now...

it's just too late :S

This post was edited by Richter on Nov 29 2012 05:34pm