I'm supposed to implement a variant of the josephus problem for my C++ class using an STL list. I've got it pretty much half working but there is a logic oversight that I'm making and I keep getting assertion errors. The problem is, I believe, 'wrapping' the iterator from the end of the list to the beginning when the tempcount is less than the M value - or at least that's what the visual studio debugger would lead me to believe. In that instance, itr seems to be pointing to garbage. Help!
Code:#include <iostream> #include <list> using namespace std; int main(){ //M: incrememnt amount //N: size of list/number of current 'persons' //playerList<int>: our list, numbered 1 to N //done: becoems true when current persons is 1 bool done = false; int N = 0; int M = 0; cout <<"Please enter # of 'players': "; cin >> N; cout <<"\nPlease enter an incriment value: "; cin >> M; //check for default case, if there's only a single 'player' if(N <= 1){ cout <<" We need more players!"; system("PAUSE"); return 0; } //so we have our values, lets create our list to spec list<int> playerList; for(int i = 0; i < N; i++){ playerList.push_back(i+1); } //iterator list<int>::iterator itr; itr = playerList.begin(); int tempCount = 1; //add offset(M) to the iterator starting at begin(gradually). whatever it lands on is erased. //continue this , and wrap around if iterator == end while(done == false){ if(N == 1){ done = true; cout << "\nWinner: Player" << *itr << endl; //outputs what the iterator is pointing at } else{ //okay, so now we start to traverse the list //do we wrap? //and we have tempcount to add to the iterator until we reach m if(itr == playerList.end()){ if(tempCount == M){ //temp = true; tempCount = 0; N--; cout << "\n Player " << *itr << " lost."; itr = playerList.erase(itr); } else{ itr = playerList.begin(); //almost the same as itr++ tempCount++; } } else{ //we didn't wrap, what do we do //1: increment the iterator//tempcount //2: if tempCount = M, delete whats at the iterator //2.1: if we delete, reset tempCount, and decrease N, output result //3: soemthing if(tempCount == M){ tempCount = 0; N--; cout << "\n Player " << *itr << " lost."; itr = playerList.erase(itr); } else{ if(itr == playerList.end()){ itr = playerList.begin(); //almost the same as itr++ tempCount++; } else{ itr++; tempCount++; } } }//end inside else }//end else }//end while system("PAUSE"); return 0; }



LinkBack URL
About LinkBacks


