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

[aminu241]

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

[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

[aminu241]

please ignore the { and } at the beginning and end of the delete algorithm

[weaknessforcats]

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.

[aminu241]

i haven't studied template yet, but if its that effective ill look into it and see if i can do better.

[weaknessforcats]

Here's the short course:

#include <iostream>
#include <list>
using namespace std;

int main()
{
	list<int>  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<int>::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 <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>::iter ator.

You position to the beginning of the list using the list<int>::begi n() 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.

[weaknessforcats]

I noticed this in your code:

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.

[aminu241]

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

[aminu241]

thanks, i think i got how to implement the template into my code. thanks