Problem Consider the following code to solve the Josephus pr

Problem) Consider the following code to solve the Josephus problem.   A) Document the code to explain how it works; B) Re-implement the solution using classes from the STL; C) Caculate Big – O for the algorithm. DO all th parts.

//Josephus Problem

#include <iostream.h>

#include <stdlib.h>

struct node

{ int item; node* next;

    node(int x, node* t)

      { item = x; next = t; }

};

typedef node *link;

int main(int argc, char *argv[])

{ int i, N = atoi(argv[1]), M = atoi(argv[2]);

    link t = new node(1, 0); t->next = t;

    link x = t;

    for (i = 2; i <= N; i++)

      x = (x->next = new node(i, t));

    while (x != x->next)

      {

        for (i = 1; i < M; i++) x = x->next;

        x->next = x->next->next;

      }

    cout << x->item << endl;

}

5 6 7 9 9 2 8 2 Figure 3.5 Example of Josephus election This diagram shows the result of a Josephus-style election, where the group stands in a circle, then counts around the circle, eliminat- ing every fifth person and closing the circle.

Solution

a) Explaination of Josephous election :

Here we used linkedlist circular, and pointed to the next node immediately after removing the Mth node among N nodes .

From N 2to N , We traversed M nodes and removed Mth node . WE linked the removed node to next node pointer .

b)Using standard template library in C++, we can write Josephus problem like : Use circular queue

#include<iostream.h>
template <class T>
class ex
{
   private:
       struct node
       {
           T data;
           struct node *next;
       };
       struct node *head,*front,*rear;
   public:
       ex()
       {
           head=new node;
           head->next=NULL;
           front=rear=head;
       }
       void enqueue(T x);
       T dequeue();
       void print();
       void move_next();
};

//////////////////Implementation file
#include \"ex.h\"
template <class T>
void ex<T>::enqueue(T x)
{
   node *p;
   p=new node;
   p->data=x;
   if(head->next==NULL)
   {
       front=rear=p;
       head->next=p;
       p->next=p;
   }
   else
   {
       rear->next=p;
       p->next=front;
       rear=rear->next;
   }
}

template<class T>
T ex<T>::dequeue()
{
   node *t;
   T x;
   t=front;
   x=t->data;
   front=front->next;
   rear->next=front;
   delete(t);
   return x;
}

template<class T>
void ex<T>::print()
{
   node *p=front;
   do
   {
       cout<<p->data<<endl;
       p=p->next;
   }while(p!=rear->next);
}

template<class T>
void ex<T>::move_next()
{
   front=front->next;
   rear=rear->next;
}

/////////////////Application file
#include \"ex.cpp\"
void main()
{
   ex<int> e;
   int m,n,i,d;
   cout<<\"Enter the number of people
\";
   cin>>n;
   cout<<\"Enter the number of passes
\";
   cin>>m;
   for(i=1;i<=n;i++)
       e.enqueue(i);
   cout<<\"The people are
\";
   e.print();
   cout<<\"Eliminated in order
\";
   while(n>1)
   {
       for(i=1;i<=m;i++)
           e.move_next();
       d=e.dequeue();
       cout<<d<<endl;
       n--;
   }
   d=e.dequeue();
   cout<<\"Winning person:   \"<<d<<endl;
}

3) Big O complexity analysis for Josephus problem given is O(nm) where n is time for the adding n elements and m is time for deleeting m elements in order .

O(nm) is the time complexity