Posted by Kaoru [send private reply] at September 15, 2002, 05:32:11 PM

How can I use C++ to solve the following problem (revised)?

List how many ways the numbers 9, 13, 17, 25, 31, and 35 can be added exactly 6 times to equal 100.

(I'm pretty sure the numbers can be used more than once.)

I don't need the *exact* code or anything (although it would be nice :E), just a hint or idea on how to start it b/c I have no idea where to begin. X.x

Posted by mop [send private reply] at September 15, 2002, 08:54:20 PM

Please, do not post your *exact* homework assignments because we won't do your work for you. Rather, post specific questions that you need help with.

Although I'll give a shot at working it out in psuedo-code, sounds kinda fun.

Posted by sphinX [send private reply] at September 16, 2002, 12:20:31 AM

just run through all the permutations of adding the numbers and remember the ones that add to 100.

Posted by buzgub [send private reply] at September 16, 2002, 12:35:02 AM

I will suggest that you need to write code to generate a list of the combinations of how you can put those numbers in a row of 6 numbers. That shouldn't be that difficult; 6 nested for loops is an obvious way of doing it; there are ways of doing it so that there is one for loop, though, so you might like to think about how you're going to do it.

If you examine the list of possible combinations I've provided, you may well be able to work out how you should be writing your code. You should look for the pattern in the sample.

Once you've worked out how you generate these lists, it should be a simple matter to go from there.

Some possible combinations:

9, 9, 9, 9, 9, 9
9, 9, 9, 9, 9, 13
9, 9, 9, 9, 9, 17
9, 9, 9, 9, 9, 25
9, 9, 9, 9, 9, 31
9, 9, 9, 9, 9, 35
9, 9, 9, 9, 13, 9
9, 9, 9, 9, 13, 13
9, 9, 9, 9, 13, 17

Good luck!

Posted by CodeRed [send private reply] at September 16, 2002, 10:51:25 AM

jesus, just shoot yourself in the head and save yourself the trouble....

Posted by DragonWolf [send private reply] at September 16, 2002, 11:16:12 AM

Buzgub's solution is the simplist and you probably don't want something complicated, but I got bored.. so heres a method which I believe is the most efficient way of doing it.

A tree with the root starting at 100, then generating the node below it (100-35)

If the result < 0 then go back up a node (then try the next number in the sequence)

if the result = 0 then increment the number of solutions by 1 and go back up a node

if the result > 0, generate the next node.

You'll need to keep track of the level of the node, if the next node goes above the 6th level then go back a node.

If there are no more numbers in the sequence to generate a new node then go up a node (unless it is the root node in which case end loop)

Display number of solutions.

This will significantly decrease the amount of memory accesses and amount of processing time required.

Posted by Kaoru [send private reply] at September 16, 2002, 02:14:04 PM

Thanks a lot for the help guys. It wasn't as hard as I thought it would be. ^^; I've been able to come up with the following so far:

// points.cpp
#include <iostream.h>

int main()
{
int p[6] = {9,13,17,25,31,35};
int a, b, c, d, e, f, sum=0;

for (a = 0; a < 6; a++)
for (b = 0; b < 6; b++)
for (c = 0; c < 6; c++)
for (d = 0; d < 6; d++)
for (e = 0; e < 6; e++)
for (f = 0; f < 6; f++)
{
sum=p[a]+p[b]+p[c]+p[d]+p[e]+p[f];

if (sum == 100)
cout << p[a] <<" + "<< p[b] <<" + "<< p[c] <<" + "<< p[d] <<" + "<< p[e] <<" + "<< p[f] <<" = 100" << endl;
}
return 0;
}

I have two followup questions:

1. How can I eliminate repeats? (ie: 35+25+9+9+9+13 and 35+25+9+9+13+9, and many others)

2. Buzgub, what was that about doing the whole thing in one loop?

Posted by CViper [send private reply] at September 16, 2002, 03:39:59 PM

Store the results somewhere (an array). When you've finished looping through all, just sort out the repeated ones from the array.

Posted by Psion [send private reply] at September 16, 2002, 04:54:39 PM

Oi, that's a pretty bad idea, CViper. Can anyone give a better way before I have to say the obvious? =)

Posted by regretfuldaydreamer [send private reply] at September 16, 2002, 05:01:05 PM

Linked List?

Posted by CViper [send private reply] at September 17, 2002, 01:32:40 AM

:( It's a easy suggestion tough... (yeah i know you can use permutations and so on, but it's early in the morning, so my brain isn't [very] active yet)

Posted by buzgub [send private reply] at September 17, 2002, 02:13:45 AM

Me not having done any serious study of computer science stuff of any sort yet, I'm stabbing in the dark about how you'd do this stuff. However, from what little I know of hashing, it can be used to handle this (collision detection?).

I suspect Psion's going to have to say the obvious :)

Posted by CViper [send private reply] at September 17, 2002, 05:27:32 AM

Instead of actually storing all results, you can filter them directly before storing (before adding a solution, you check if it's unique and only then store it)

Posted by buzgub [send private reply] at September 17, 2002, 05:35:49 AM

That's still not really any more elegant as a solution.

Perhaps it is possible to arrange your loops such that you get no repeats. I can't think of how you'd do so, though.

Posted by DragonWolf [send private reply] at September 17, 2002, 05:36:52 AM

its really bugging me but I can't see any simple changes to that code that would solve the problem. Plenty of other methods of checking it, but nothing "obvious" ^^

Posted by Psion [send private reply] at September 17, 2002, 08:59:39 AM

Does "non increasing sequences" mean anything to you? ;)

Posted by DragonWolf [send private reply] at September 17, 2002, 09:46:36 AM

I must have missed that lecture ^^

nope

Posted by regretfuldaydreamer [send private reply] at September 17, 2002, 11:40:42 AM

nope - We're not all in our third year of uni.

Posted by CViper [send private reply] at September 17, 2002, 02:57:06 PM

for( int a = 0; a < 6; ++a )
{
  for( int b = a; b < 6; ++b )
  {
    // and so on
  }
}

You have to sort the array (p) by size. The idea is that while a number can repeat itself, the number in the next loop can't be smaller/larger (depending on the sorting) than that in the current one.

Posted by Psion [send private reply] at September 17, 2002, 03:30:58 PM

It's not a technical term. It just refers to the fact that you can consider sets (order doesn't matter) as actually being sequences in sorted order, AKA the elements never increase/decrease (pick one and stick with it) as you read them off in order.

Posted by DragonWolf [send private reply] at September 18, 2002, 04:58:16 AM

I was thinking of a way of doing the same thing but didn't see it. Thats ingenious, I'll have to remember that for the next time I run into this problem (if ever)

Posted by buzgub [send private reply] at September 18, 2002, 06:02:20 AM

Psion, I'm afraid I don't get your statement "the elements never increase/decrease (pick one and stick with it) as you read them off in order. "

Is there any chance you could expand my knowledge a bit by explaining further here?

Posted by Psion [send private reply] at September 18, 2002, 06:34:40 AM

What 2-element sequences can you make from {0, 1}?

{00, 01, 10, 11}

What if order doesn't matter? Then we'll make sure we only output sorted sequences so we don't have duplicates.

{00, 01, 11}

Posted by buzgub [send private reply] at September 18, 2002, 06:54:00 AM

Hm. My current guess as to how this gives you an improvement is that because you are now sorting the numbers before you start doing these checks you can just do a comparison with the current largest known correct permutation; if it's unknown it will in this case be larger.

Does that sound like my thoughts are on at least the right railway line?

Posted by Psion [send private reply] at September 18, 2002, 07:16:43 AM

You don't sort each possibility. You only consider choices for next members of the sequence if they are >= the last one.

Posted by buzgub [send private reply] at September 18, 2002, 07:43:10 AM

Gotcha. That took me so long to get my head around it's ridiculous.