----------------------------------- Clayton Fri Mar 03, 2006 4:59 pm Partition Problem ----------------------------------- 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 Fri Mar 03, 2006 5:06 pm Code ----------------------------------- 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. :D ----------------------------------- chrispminis Fri Mar 03, 2006 6:30 pm ----------------------------------- 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 Fri Mar 03, 2006 7:09 pm program ----------------------------------- 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 Fri Mar 03, 2006 9:23 pm ----------------------------------- 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 Fri Mar 03, 2006 9:30 pm Re: program ----------------------------------- 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 Fri Mar 03, 2006 9:33 pm ----------------------------------- 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 Fri Mar 03, 2006 9:38 pm ----------------------------------- 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 Fri Mar 03, 2006 10:38 pm ----------------------------------- huh? what? ----------------------------------- batman Sat Mar 04, 2006 9:22 am Code ----------------------------------- There are many ways to do this type of code but the best way is too use a counter. ----------------------------------- [Gandalf] Sat Mar 04, 2006 9:49 am ----------------------------------- "Best" is relative, and I doubt that your point is true in this case. ----------------------------------- Cervantes Sat Mar 04, 2006 11:36 am ----------------------------------- I think batman should take a [url=http://www.compsci.ca/v2/viewtopic.php?t=11391]challenge. ----------------------------------- MysticVegeta Sat Mar 04, 2006 12:27 pm Re: Code ----------------------------------- 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 Sat Mar 04, 2006 1:20 pm Code ----------------------------------- What is the challenge? ----------------------------------- MysticVegeta Sat Mar 04, 2006 1:36 pm ----------------------------------- Hint: Click the link "challenge" to find out. :roll: ----------------------------------- batman Sat Mar 04, 2006 2:09 pm code ----------------------------------- So the challange is to learn the computer language O'Cami? Ok, well i'll give it a shot then. :D ----------------------------------- Cervantes Sat Mar 04, 2006 2:16 pm ----------------------------------- Awesome. Except, it's O'Caml. "El". ;) Join the [url=http://www.compsci.ca/wiki/index.php?title=IRC_channel]IRC Channel for some help. ----------------------------------- batman Sat Mar 04, 2006 2:39 pm O'Caml ----------------------------------- Oh, my bad! :( ----------------------------------- batman Sat Mar 04, 2006 2:41 pm Language ----------------------------------- I don't have time to learn it now though. During the march break i'll begin to start learning O'Caml. ----------------------------------- Clayton Sat Mar 04, 2006 6:35 pm ----------------------------------- This is all great and everything but what happened to staying on topic in this thread, if you dont have anything to help please dont post it here, thats what the PM feature is for