The Josephus Problem

Posted by Unknown On Saturday, July 10, 2010 1 comments

/********************************************************
The Josephus Problem

--> The Problem is known as the Josephus problem and postulates a group of

soldiers surrounded by an overwhelming enemy force. There is no hope for

victory without reinforcements, but there is only a single horse available

for escape and summon help. They form a circle and a number n is picked from

Image via Wikipedia

Fig: Circular Linked List

a hat. One of their names is also picked from a hat. Beginning with the

soldier whose name is picked, they begin to count clockwise around the circle.

when the count reaches n, that soldier is removed from the circle, and the

count reaches n, another soldier is removed from the circle. Any soldier

removed from the circle is no longer counted. The last soldier remaining is to

take the horse and escape.

The problem is, given a number n, the ordering of the soldiers in the

circle, and the soldier from whom the count begins, to determine the order in

which soldiers are eliminated from the cirlce and which soldier escapes.

*********************************************************/

/*******************************************************
APPLICATION : The Josephus Problem
CODED BY : Ankit Pokhrel
COMPILED ON : Borland C++ Ver 5.02
DATE : 2010 - July - 01
********************************************************/

#include "iostream.h"
#include "conio.h"
#include "string.h"

struct Josephus
{
char name[15];
struct Josephus *next;
};

typedef Josephus node;

node *New,*head = NULL,*ptr;

void create(char *n) //Function to create node and link
{
New = new node;
strcpy(New -> name,n);
if(head == NULL)
  {
head = New;
   head -> next = head;
   ptr = head;
  }

else
{
   ptr -> next = New;
   New -> next = head;
   ptr = New;
   }
}

node* remove(char *n) //Function to delete a node
{
node *temp = head,*deleted;
while(strcmp(temp -> next -> name,n) != 0)
   temp = temp -> next;

deleted = temp -> next;
temp -> next = temp -> next -> next;
return deleted; //return deleted node
}

int main()
{
create(""); //Create first node with empty contents to represent end or Start of list
int m,n,i,j;
char nme[15],sname[15];
do
{
  cout << "How many Soldiers? "; //Scan total number of soldiers
  cin >> m;
  if(m <= 0)
   cout << "\nPlease choose number greater than " << m << endl;
}while(m <= 0);

do
{
  cout << "\nEnter N = "; //Scan N
  cin >> n;
  if(n <= 0)
cout << "\nPlease pick the number greater than " << m;
}while(n <= 0);

for(i = 0;i < m;i++) //Scan Soldiers Name
  {
   cout << "\nEnter Name : ";
   cin >> nme;
create(nme); //Create a list of soldiers
  }

cout << "\n\nStart With : "; //Starting Soldier
cin >> sname;

node *temp = head,*nd;
while(strcmp(temp -> next -> name,sname) != 0)
  {
temp = temp -> next; //Go to starting soldier
   if(strcmp(temp -> name,"") == 0) //if not found
   {
   cout << "\nSorry, the Soldier is not on list";
   getch();
   return 0;
   }
  }

cout << endl << endl;
for(int k = 0;k < m;k++)
  {
   j = 0;
   for(i = 1;i <= n;i++) //Loop from 1 to n
   {
   temp = temp -> next; //Move to next node
   j++;
   if(strcmp(temp -> name,"") == 0) //Ignore empty node
   {
   j--;
   i--;
   }

   if(j == n) //If node is found
   {
   nd = remove(temp -> name); //Remove node
   if(k != m-1) //If more than one node
   cout << "Eliminated Soldier : " << nd -> name << endl;

   else
   cout << "\nThe Soldier to take Horse and Escape is " << nd -> name << endl;

   break; //Exit from loop
   }
  }
}

getch();
return 0;
}