In C++, use a circular list to implement the Josephus Problem. In the Josephus Problem, there is originally a circle of people numbered from one to n. Some number is chosen as the starting person, and an interval of size m is selected. Then, starting at the chosen person, every mth person is eliminated until only one person remains.

The output should be a list of the eliminated people in the order of elimination, and a statement of which person remains.

Do this once with the circular list class implemented with nodes and pointers and once as a circular array with some method of designating a person as "not there." The two implementations of the circular list should be designed to require no change to the code outside the circular list class. Both circular list classes should have functions AdvanceN(n) and DeleteThis(x), where AdvanceN(n) returns a new position in the list that is n places further on, and DeleteThis(x) deletes person x and returns the position previous to x.

The code I have so far is below, but I'm not sure about the "designating a person as not there" part.

#include using namespace std;

//define the structure of the node struct node { int value; node *previous; node *next; };

int main (){ int numPeople = 0; cout << "Enter the number of people: " << endl; cin >> numPeople; //Create a head node node *curNode = new node(); curNode->value = 1; //create a temp node node *temp = curNode; //create a chain of nodes //each node has a pointer to next and previous nodes //plus a number for its value for (int i=2; i <= numPeople; i++){ curNode->next = new node(); curNode->next->previous = curNode; curNode = curNode->next; curNode->value = i; } //attach the tail node back to the head curNode->next = temp; curNode->next->previous = curNode; //move current node back to head curNode = curNode->next; int DeleteThis = 0; //prompt for the nth person to kill on each iteration cout << "Enter the nth number killed: " << endl; cin >> DeleteThis; int counter = 1; //loop through the nodes killing every nth person //one is left standing when node points to itself while (curNode->next != curNode) { //compare the count to the value of nth killed //kill the node by kicking it out of the chain //reset counter if (counter == DeleteThis) { cout << "killed: " << curNode->value << endl; //tell the previous node to point to the current node's //next node curNode->previous->next = curNode->next; //tell the next node's previous pointer to point to the //current node's previous node curNode->next->previous = curNode->previous; //record the next node because will free the current node node *next = curNode->previous->next; delete(curNode); //advance the current node to the next //node to complete the kill curNode = next; counter = 1; } else { //not a time to kill, so move to the next node //and advance counter curNode = curNode->next; counter++; } } //by the time the loop ends, we have 1 survivor cout << "Survivor: " << curNode->value << endl; delete(curNode); return 0; }