Partition Problem

[Clayton]

hi guys, im taking part in a competition soon and ive looked up some previous problems to practice, but i dont quite understand them heres the first one:
you have to make a program to find the partition of a number. the partition of a number is the number of ways you can add numbers together (1 to the number) to make that number for example:

5=1+1+1+1+1
5=1+1+1+2
5=1+2+2
5=1+1+3
5=2+3
5=1+4
5=5

so therefore partition(5)=7 because there are seven ways to make 5,
what you have to do is code it so that a user can input a number from 1-50 and the program must find the partition of that number heres a sample

INPUT
50
OUTPUT
Partition(50)=204226

my question is does anybody here know how you might go about doing that if so plz help

[batman]

Well, there are many ways of doing this type of code. You could use an array if you wanted too. That might work and maybe a for loop. It be best if you showed me what you've done so far and then I could help you out from there.

[chrispminis]

No, batman, I think he's asking a math question. As in how you would reliably find the partition of a number. You should try googling it, or figure it out yourself. Get say the first 10 partitions and try to find a pattern.

[batman]

Yes chris is right! Find a pattern first. The pattern is 1,2,3,5,7,9 for 1,2,3,4,5,6! Thats what ive gotten so far. The only way this prgram will work is you have to use a "counter."

[McKenzie]

You've posted in the wrong area. Post under contests. ... Seems trivial, I know, but if you are doing contest training post under contests because there are some killer contest writers who visit this site (e.g. Bugz (I know of no better))

[md]

batman wrote:

Yes chris is right! Find a pattern first. The pattern is 1,2,3,5,7,9 for 1,2,3,4,5,6! Thats what ive gotten so far. The only way this prgram will work is you have to use a "counter."

*sigh* there are many ways this program will work; though in order to return a total you either need a math formula or yes a counter. I can see a recursive method in this; thought it might be a bit challenging.

Oh, and there are 10 ways to get 6.

[MysticVegeta]

Wow bugz must feel proud after that reply no?
Anyways, what you are doing calls for DP (Dynamic Programming) For a better understanding of what I am saying go here and read posts by Bugz and Martin.
http://www.compsci.ca/v2/viewtopic.php?t=11393

[md]

MysticVegeta wrote:

Wow bugz must feel proud after that reply no?
Anyways, what you are doing calls for DP (Dynamic Programming) For a better understanding of what I am saying go here and read posts by Bugz and Martin.
http://www.compsci.ca/v2/viewtopic.php?t=11393

Wrong topic?

[MysticVegeta]

huh? what?

[batman]

There are many ways to do this type of code but the best way is too use a counter.

[[Gandalf]]

"Best" is relative, and I doubt that your point is true in this case.

[Cervantes]

I think batman should take a challenge.

[MysticVegeta]

batman wrote:

There are many ways to do this type of code but the best way is too use a counter.

I will take it you mean counting the # of possible combinations. I would sort of because I think the best way to accomplish this is to use a boolean array..? look at martins explanation for a better explanation

[batman]

What is the challenge?

[MysticVegeta]

Hint: Click the link "challenge" to find out.