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

Josephus Problem

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