Josephus Algorithm
The problem is described as, “If there are n persons standing in a circle. Beginning from any person, the others are numbered in a particular direction (clockwise or anti-clockwise). Then a random number, n is generated. The counting begins from the person numbered as one upto n. The nth person is removed from the game so that total number of persons in the circle gets reduced by one. The same process is continued until one person remains in the circle, who is declared to be the winner. Circular linked list may be used for representing this problem, which is codified below:
/*Josephus algorithm*/
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
struct clist
{
int id;
char name[45];
struct clist *next;
}*head=NULL,*temp,*ptr;
void create()
{
ptr=(struct clist *)malloc(sizeof(struct clist));
if(ptr==NULL)
{
printf(“Memory Allocation Error!”);
exit(1);
}
}
void makenode(int pid,char nm[])
{
create();
ptr->id=pid;
strcpy(ptr->name,nm);
ptr->next=NULL;
}
void insertend()
{
if(head==NULL)
{
head=ptr;
ptr->next=head;
}
else
{temp=head;
while(temp->next!=head)
temp=temp->next;
ptr->next=head;
temp->next=ptr;
}
}
void display()
{
if(head==NULL)
{
printf(“List is empty.”);
return;
}
if(head==head->next)
{
printf(“(%d,%s)->”,head->id,head->name);
return;
}
temp=head;
printf(“(%d,%s)->”,temp->id,temp->name);
temp=temp->next;
while(temp!=head)
{
printf(“(%d,%s)->”,temp->id,temp->name);
temp=temp->next;
}
printf(“bb “);
}
void playgame()
{
int m,i;
struct clist *tmp;
printf(“Enter the value of counter m?”);
scanf(“%d”,&m);
temp=head;
while(temp!=temp->next)
{
for(i=0;i<m-1;i++)
temp=temp->next;
tmp=temp->next;
temp->next=tmp->next;
free(tmp);
}
printf(“Winner of the Game is: (%d,%s)”,temp->id,temp->name);
getch();
}
void main()
{
int choice,id;
char name[45];
while(1)
{
clrscr();
printf(“ntWhat to do”);
printf(“nnt1. Generate Circular list of persons”);
printf(“nt2. Display List of persons”);
printf(“nt3. Play the Game”);
printf(“nt4. Exit”);
printf(“ntEnter your choice?”);
scanf(“%d”,&choice);
switch(choice)
{
case 1:
printf(“nEnter person id?”);
scanf(“%d”,&id);
printf(“nEnter person name?”);
scanf(“%s”,name);
makenode(id,name);
insertend();
break;
case 2:
display();
getch();
break;
case 3:
playgame();
break;
case 4:
exit(0);
default:
printf(“nInvalid choice.”);
}
}
}