By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
435,197 Members | 1,173 Online
Bytes IT Community
+ Ask a Question
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
  1. [int list::Delete(int M)
  2. {
  3.     //try to find the node with its value equal to n
  4.     node* prevNode = NULL;
  5.     node* currNode =head;
  6.     int   currIndex =1;
  7.     while(currNode && currNode->data != M)
  8.     {
  9.         prevNode = currNode;
  10.         currNode = currNode->next;
  11.         currIndex++;
  12.     }
  13.  
  14.     //found it
  15.     if(currNode)
  16.     {
  17.         if(prevNode)
  18.         {
  19.             prevNode->next = currNode->next;
  20.             delete currNode;
  21.         }
  22.         else //delete the first Node
  23.         {
  24.             head = currNode->next;
  25.             delete currNode;
  26.         }
  27.         return currIndex;
  28.     }
  29.      return 0;
  30. }]
  31.  
  32. i called it in main as
  33. [for(int i = N; i =1; i--)
  34. {
  35.     list.delete(M);
  36. }}
  37.  
  38.  
thanks
Nov 4 '15 #1

✓ answered by weaknessforcats

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.

Share this Question
Share on Google+
7 Replies


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

weaknessforcats
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

weaknessforcats
Expert Mod 5K+
P: 9,197
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.
Nov 4 '15 #5

weaknessforcats
Expert Mod 5K+
P: 9,197
I noticed this in your code:

Expand|Select|Wrap|Line Numbers
  1. i called it in main as
  2. [for(int i = N; i =1; i--)        <<<  i == 1 ?
  3. {
  4.     list.delete(M);
  5. }}
  6.  
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

Post your reply

Sign in to post your reply or Sign up for a free account.