Josephus Problem
C++ Code for Josephus Problem
#include<iostream>
#include<conio.h>
#include<string.h>
using namespace std;
struct Josephus
{
char name[20];
struct Josephus *next;
};
typedef Josephus node;
node *New,*head = NULL,*ptr;
void create(char *n)
{
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)
{
node *temp = head,*deleted;
while(strcmp(temp -> next -> name,n) != 0)
temp = temp -> next;
deleted = temp -> next;
temp -> next = temp -> next -> next;
return deleted;
}
int main()
{
int m,n,i,j;
char nme[15],sname[15];
do
{
cout << “enter total person = “;
cin >> m;
if(m <= 0)
cout << “\nPlease choose number greater than ” << m << endl;
}while(m <= 0);
do
{
cout << “\nEnter Number = “;
cin >> n;
if(n <= 0)
cout << “\nPlease enter the number greater than ” << m;
}while(n <= 0);
for(i = 0;i < m;i++)
{
cout << “\nEnter the Name = “;
cin >> nme;
create(nme);
}
cout << “\n\n your Starting name With : “;
cin >> sname;
node *temp = head,*nd;
while(strcmp(temp -> next -> name,sname) != 0)
{
temp = temp -> next;
if(strcmp(temp -> name,””) == 0)
{
cout << “\nSorry, there is no person in the list “;
getch();
return 0;
}
}
cout << endl << endl;
for(int k = 0;k < m;k++)
{
j = 0;
for(i = 1;i <= n;i++)
{
temp = temp -> next;
j++;
if(strcmp(temp -> name,””) == 0)
{
j–;
i–;
}
if(j == n)
{
nd = remove(temp -> name);
if(k != m-1)
cout << “Eliminated person : ” << nd -> name << endl;
else
cout << “\to take Hourse and Eleminate is ” << nd -> name << endl;
break;
}
}
}
getch();
return 0;
}
Click on the link to download the presentation
Related links
Single link list Stack AVL Trees Binary search Counting Sort
Doubly link list Queue Graphs Bubble Sort Radix sort
Circular link list Binary search tree Hashing Insertion Sort Bucket Sort
Josephus Problem Tree Traversal Heaps Quick Sort Merge Sort
At Cui tutorial, courses, past papers and final year projects
#tutorial #cui #pastpaper #courses