435,197 Members | 1,173 Online
Need help? Post your question and get tips & solutions from a community of 435,197 IT Pros & Developers. It's quick & easy.

# Josephus problem help, the implementation of josephus problem using c++

 P: 5 hi guys, i'm New to this forum and would really appreciate your help. I've been learning linked lists recently and am trying to implement the josephus problem using c++, josephus problem is a game in which there are N number of players who are going to be eliminated after every M passes, i think i got the insertion part alright, and also the display function seems to work fine but I'm still struggling with the deletion after M passes. can some one please help give me some tips on how i might implement it. below is my deletion algorithm Expand|Select|Wrap|Line Numbers [int list::Delete(int M) {     //try to find the node with its value equal to n     node* prevNode = NULL;     node* currNode =head;     int   currIndex =1;     while(currNode && currNode->data != M)     {         prevNode = currNode;         currNode = currNode->next;         currIndex++;     }       //found it     if(currNode)     {         if(prevNode)         {             prevNode->next = currNode->next;             delete currNode;         }         else //delete the first Node         {             head = currNode->next;             delete currNode;         }         return currIndex;     }      return 0; }]   i called it in main as [for(int i = N; i =1; i--) {     list.delete(M); }}     thanks Nov 4 '15 #1

Here's the short course:

Expand|Select|Wrap|Line Numbers
1. #include <iostream>
2. #include <list>
3. using namespace std;
4.
5. int main()
6. {
7.     list<int>  myList;  //create the list
8.     myList.push_back(4); //add 4 to the end of the list
9.     myList.push_front(20); //add 20 to the front of the lst
10.
11.     list<int>::iterator itr;   //create an iterator for int
12.     itr = myList.begin();      //position iterator to first element
13.
14.     while (itr != myList.end())
15.     {
16.         cout << *itr << endl;   //iterator acts like a pointer
17.         ++itr;                  //increment iterator to next element
18.     }
19.
20. }
In this example the list template is in the <list> header. For a list of ints you create a variable using list<int>. This makes a copy of the template an populates the element as an int. Now you have a class specifically for int. All you have to do is create an instance of the class.

From here you need to read about list member functions. There are quite a few but in the example you see adding to the back and the front of the list.

To scan the list, all C++ Standard Library objects use a helper class named iterator. Again, this is a template and you need an iterator object that acts like an int pointer. That is the list<int>::iterator.

You position to the beginning of the list using the list<int>::begin() member function. You reach the end of the list AFTER he last element is processed. So the list<int>::end() member function returns an iterator that is one element beyond the end of the list.

These container templates all work the same so once you learn the member functions for one of them you will find they are there for the other containers as well.

I hope to convey that using the C++ Standard Template Library does not involve a ton of study nor a ton of code.

7 Replies

 P: 5 please ignore the { and } at the beginning and end of the delete algorithm Nov 4 '15 #2

 Expert Mod 5K+ P: 9,197 Considering you are using C++, why would you re-invent a linked list rather than use the list<> template? All of your issues are resolved in the code for the template. Nov 4 '15 #3

 P: 5 i haven't studied template yet, but if its that effective ill look into it and see if i can do better. Nov 4 '15 #4

 Expert Mod 5K+ P: 9,197 Here's the short course: Expand|Select|Wrap|Line Numbers #include  #include  using namespace std;   int main() {     list  myList;  //create the list     myList.push_back(4); //add 4 to the end of the list     myList.push_front(20); //add 20 to the front of the lst       list::iterator itr;   //create an iterator for int     itr = myList.begin();      //position iterator to first element       while (itr != myList.end())     {         cout << *itr << endl;   //iterator acts like a pointer         ++itr;                  //increment iterator to next element     }   } In this example the list template is in the header. For a list of ints you create a variable using list. This makes a copy of the template an populates the element as an int. Now you have a class specifically for int. All you have to do is create an instance of the class. From here you need to read about list member functions. There are quite a few but in the example you see adding to the back and the front of the list. To scan the list, all C++ Standard Library objects use a helper class named iterator. Again, this is a template and you need an iterator object that acts like an int pointer. That is the list::iterator. You position to the beginning of the list using the list::begin() member function. You reach the end of the list AFTER he last element is processed. So the list::end() member function returns an iterator that is one element beyond the end of the list. These container templates all work the same so once you learn the member functions for one of them you will find they are there for the other containers as well. I hope to convey that using the C++ Standard Template Library does not involve a ton of study nor a ton of code. Nov 4 '15 #5

 Expert Mod 5K+ P: 9,197 I noticed this in your code: Expand|Select|Wrap|Line Numbers i called it in main as [for(int i = N; i =1; i--)        <<<  i == 1 ? {     list.delete(M); }}   I hope this is a typo and not a copy/paste because you show the exit condition as an assignment rather than an equality/inequality test. Nov 4 '15 #6

 P: 5 yeah it's a typo, i did it correctly in the original program, its not and assignment its and equality test to check stop looping when i==1 Nov 5 '15 #7

 P: 5 thanks, i think i got how to implement the template into my code. thanks Nov 5 '15 #8