int count = 0;
void test( int n )
{
// we know that when there are only 2 seats/people
// there are 2 combinations so add those to count
if ( n == 2 )
{
count += 2;
return;
}
for ( int i = 0; i < n; i++ )
{
test(n-1);
}
}
recursive function check
Author
Can anyone look at my function. I haven't used recursion much and just want to know if I did this right. It's supposed to count the number of possible seat combinations given n. where n is the number of people and seats.
For starters you will be required to create a prototype of the function or you will get a compile time error. I am unsure about whether your algorithm is correct because I do not understand it. That function will however recurse successfully.
That doesn't look right to me. Perhaps try something like this:
It assumes n >= 0.
int CountCombinations(const int n){ if (n <= 2) return n; else return n*CountCombinations(n-1);}It assumes n >= 0.
Eew eew eew. Get rid of that global variable, right now.
Call that function twice in a row, and you get a wrong answer the second time. That's bad.
CM
Call that function twice in a row, and you get a wrong answer the second time. That's bad.
CM
Author
Well, I'm gonna try to break it down for anyone that cares...
Basically you call test with how many people you have. So if you have 3 people call test(3) to see how many combinations you can seat them in.
So if you have a row of 3 seats the people can be seated in any of these combinations (i think this is right):
123
132
213
312
321
231
So from what I understand you are supposed to break the problem down into a simpler problem that you can answer easily. So I knew that if I had 2 people/seats that I could only put them in 2 different combinations:
12
21
The for loop just moves the first person to each seat and then breaks it down to one less person/seat to test until it gets to 2. So here the first person starts in seat 1 and then we call test(n-1), now n==2 so I add 2 to count for the two combinations (above: 123 and 132). Now we the for loop moves the first person to seat 2 and we call test(n-1), again n==2 so I add 2 for the 2 combinations(213 and 312). Loop again and the first person is in seat 3 and we call test(n-1), n==2 so we add 2 again for the combinations (321 and 231). There's no where else for the first person to move so we are done.
We found 6 possible seating combinations. Hopefully you can see how it works for more than 3 people cause that would probably cause my brain to explode to try and break that down :P
I hope that explains what I'm doing better. This stuff is hard to explain. It was hard enough coming up with something that worked... lol :P
Basically you call test with how many people you have. So if you have 3 people call test(3) to see how many combinations you can seat them in.
So if you have a row of 3 seats the people can be seated in any of these combinations (i think this is right):
123
132
213
312
321
231
So from what I understand you are supposed to break the problem down into a simpler problem that you can answer easily. So I knew that if I had 2 people/seats that I could only put them in 2 different combinations:
12
21
The for loop just moves the first person to each seat and then breaks it down to one less person/seat to test until it gets to 2. So here the first person starts in seat 1 and then we call test(n-1), now n==2 so I add 2 to count for the two combinations (above: 123 and 132). Now we the for loop moves the first person to seat 2 and we call test(n-1), again n==2 so I add 2 for the 2 combinations(213 and 312). Loop again and the first person is in seat 3 and we call test(n-1), n==2 so we add 2 again for the combinations (321 and 231). There's no where else for the first person to move so we are done.
We found 6 possible seating combinations. Hopefully you can see how it works for more than 3 people cause that would probably cause my brain to explode to try and break that down :P
I hope that explains what I'm doing better. This stuff is hard to explain. It was hard enough coming up with something that worked... lol :P
Author
Quote:Original post by Conner McCloud
Eew eew eew. Get rid of that global variable, right now.
Call that function twice in a row, and you get a wrong answer the second time. That's bad.
CM
lol yea i know i shouldnt use that i just threw this together quick to see what would come up.
Author
Quote:Original post by nilkn
That doesn't look right to me. Perhaps try something like this:
*** Source Snippet Removed ***
It assumes n >= 0.
I knew there had to be an easier way. That looks much better. Thanks. I'm thinking too much about it I think.
Author
Quote:Original post by Andorien
From what I can see, you don't actually have a way to retrieve the result. You'd need something like this
*** Source Snippet Removed ***
I think that should do it.
I tried that at first too but that return in the loop means it will only loop once so the answer doesn't come out right. nilkn did it right, I just wasn't thinking to multiply instead of doing the loop.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement