Quote (Richter @ Nov 30 2012 11:27am)

yes it's still brute force, but thats the reason i called it brute-force. you mad?

Quote (Nom_Nomz @ 29 Nov 2012 17:47)

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?

Quote (Fawar @ 3 Dec 2012 12:51)

Do you need to display every possibilites or is the numbers of way enough?
If you don't need the display here is an easy way of calculating the number of possibilites recursively

http://ideone.com/gPl19n


Have Fun!

Edit: HAd forgotten to cover the negative numbers... (if amount <0)

Quote (irimi @ 29 Nov 2012 17:50)

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.

Quote (irimi @ 4 Dec 2012 14:51)

several things regarding that --

1) the inductive solution is correct; the code expressing it, not so much
2) the code in a later post is much closer to the real deal; it is in fact a correct solution if you add some minor logic to dedup solutions
3) the count is uninteresting -- it's simpler to calculate (you can formulaically dedup rather than have to do it programmatically).

last but not least, your solutions posted above are so conceptually far off the mark that I don't even want to start...

Quote (Fawar @ Dec 4 2012 02:34pm)

So thats how you are, proven wrong you attack.