C++ Program - Josephus Problem

IMPLEMENTATION OF JOSEPHUS PROBLEM

USING LINKED LIST

PROGRAM EXPLANATION:

 

Ø        Get the number of soldiers as input.

Ø        Insert the names of the soldiers into the nodes using linked list.

Ø        Delete the nodes until the last node remains.

Ø        Print the node which is not deleted

Ø        It represents the soldier who escapes.

Ø        Display the result.

 

CODE:

#include<iostream.h>

#include<conio.h>

#include<stdlib.h>

 

class jos

{

char data;

jos *next;

public:

void insert();

void del();

void display();

};

jos *node;

 

void jos::insert()

{

jos *temp;

char ch;

temp=node;

cout<<"enter the name : ";

cin>>ch;

if(temp->data==NULL)

{

temp=new jos;

temp->data=ch;

temp->next=temp;

node=temp;

}

else

{

temp=node;

jos *r;

r=new jos;

while(temp->next!=node)

{

temp=temp->next;

}

r->data=ch;

temp->next=r;

r->next=node;

}

}

 

void jos::del()

{

jos *temp,*r;

temp=node;

int a;

for(a=0;a<4;a++)

{

r=temp;

temp=temp->next;

}

cout<<endl<<temp->data<<" cannot escape!!! "<<endl;

r->next=temp->next;

node=r->next;

if(node->next==node)

{

cout<<endl<<"the saved soldier is :"<<node->data;

}

}

 

void jos::display()

{

jos *temp;

temp=node;

while(temp->next!=node)

{

cout<<endl<<temp->data;

temp=temp->next;

}

cout<<endl<<temp->data;

}

 

void main()

{

jos j;

int i,count,k;

clrscr();

cout<<"enter the number of soldiers :";

cin>>i;

for(count=0;count<i;count++)

{

j.insert();

}

for(count=0;count<i-1;count++)

{

j.del();

}

getch();

}

 

Click on the attachment below to view the output of this program

Attachment: 

Dear Guest,
Spend a minute to Register in a few simple steps, for complete access to the Social Learning Platform with Community Learning Features and Learning Resources.
If you are part of the Learning Community already, Login now!
3
Your rating: None Average: 3 (1 vote)

Posted by



Wed, 05/20/2009 - 11:16

Share

Collaborate