# The Josephus Problem

• 11-20-2002
Nakeerb
The Josephus Problem
I am having a bit of trouble. The Josephus problem is where you have a circle of people, body_count people big (like, if body_count were 5, that means the circle is made up of 5 people). And another term, excuse_counter, is set to a number. Using this number we go around the circle elinimating people until one is left.

For instance, let's say the circle is made of 9 people, and we choose our excuse_counter to be 5:

5, 1, 7, 4, 3, 6, 9, 2, 8

We reloop around this circle nailing off the person we come to when we count to excuse_counter. Using the remaining people we count again, etc, until we are left with one man left.

However I am having a bit of trouble with the coding portion. It finds the first person alright, but from here it's all downhill:

Code:

``` person* pick_person(person *group, int excuse_counter, int body_count){         person *temp = new person;         temp -> position = 12345;         temp -> next = group;                 person *previous = temp;         person *current;                 for (int i = 1; i < body_count; i++){                                 for (int x = 1; x <= excuse_counter; x++){                         if (temp -> next -> next == NULL)                                 temp -> next = previous -> next;                                                                         else                                 temp = temp -> next;                                                         }                                 cout << "\nPerson " << temp -> position << " is leaving...";                                 current = temp;                                                         while (previous -> next != current){                         previous = previous -> next;                 }                                         previous -> next = current -> next;                 delete current;                                                                             }        return group; } //end person *pick_person```

The struct:

Code:

``` struct person{         int position;         person *next; };```

I know this is very close to working but it needs a push in the right direction. I am using a linklist
• 11-20-2002
Mister C
I would use a queue. I had to do this problem in college.

Also, would it be better to use a random number to choose which person who would be killed??
• 11-20-2002
Nakeerb
No the user decides the values
• 11-20-2002
Nakeerb
That and the problem states that we must use a linklist
• 11-21-2002
Stoned_Coder
well my approach to this would be a circular list. This can be rotated and nodes removed. I would think that a circular list will model a circle of people better
• 11-21-2002
Nick
Try to find the trick to solving this problem fast without a
list.