Solve Josephus problem. Here are the 3 given classes and the original homework s
ID: 3707284 • Letter: S
Question
Solve Josephus problem. Here are the 3 given classes and the original homework sheet.
/**
*
*
* Purpose: Solve Josephus problem
* with different data structures
* and different algorithms and compare running times
*
*
*
*/
public class Josephus {
/**
* Uses ArrayDeque class as Queue/Deque to find the survivor's position.
* @param size Number of people in the circle that is bigger than 0
* @param rotation Elimination order in the circle. The value has to be greater than 0
* @return The position value of the survivor
*/
public int playWithAD(int size, int rotation) {
// TODO your implementation here
return -1; // update this statement
}
/**
* Uses LinkedList class as Queue/Deque to find the survivor's position.
* @param size Number of people in the circle that is bigger than 0
* @param rotation Elimination order in the circle. The value has to be greater than 0
* @return The position value of the survivor
*/
public int playWithLL(int size, int rotation) {
// TODO your implementation here
return -2; // update this statement
}
/**
* Uses LinkedList class to find the survivor's position.
* However, do NOT use the LinkedList as Queue/Deque
* Instead, use the LinkedList as "List"
* That means, it uses index value to find and remove a person to be executed in the circle
*
* Note: Think carefully about this method!!
* When in doubt, please visit one of the office hours!!
*
* @param size Number of people in the circle that is bigger than 0
* @param rotation Elimination order in the circle. The value has to be greater than 0
* @return The position value of the survivor
*/
public int playWithLLAt(int size, int rotation) {
// TODO your implementation here
return -3; // update this statement
}
}
***************
public class MySavor11{
/**
* A simple test program.
* @param args arguments
*/
public static void main(String[] args) {
// You can change size and rotation values for your testing
int size = 100000;
int rotation = 30000;
Josephus game = new Josephus();
Stopwatch timer1 = new Stopwatch();
System.out.println("Survivor's position: " + game.playWithAD(size, rotation));
System.out
.println("Computing time with ArrayDeque used as Queue/Deque: " + timer1.elapsedTime() + " millisec.");
Stopwatch timer2 = new Stopwatch();
System.out.println("Survivor's position: " + game.playWithLL(size, rotation));
System.out
.println("Computing time with LinkedList used as Queue/Deque: " + timer2.elapsedTime() + " millisec.");
Stopwatch timer3 = new Stopwatch();
System.out.println("Survivor's position: " + game.playWithLLAt(size, rotation));
System.out
.println("Computing time with LinkedList (remove with index) : " + timer3.elapsedTime() + " millisec.");
}
}
*************
CS 1302 4/22018 Fares Test your code extensively! MySavorll o Test code in Mysavori1.Java fle is just a starting point to test your program. VWhern you run the program, you should see the folowing result. Do not make any asaumpions and make sure to print the same values aa you sce below size (number of people) Objectives *Understand how QueueDenue can be used as an aid in an algonthm Explore and comparo d fiarant data structures uraeaue, and Liokedlist) and their mothods to solve tho aama problam. 24 wikipedie) Josephus Problem Thoro aro peoplo standing in a circle waiting to bo xocutod. A oortain number of pooplo aro slopped and then one person is executed. This is repeated starting with the person after the person who was executed. The elimination proceeds around the crcle (wch is becoming smaller as the executed people are removea) untl one person remains Notice that rotation value cen be bigger than size thst is the number of the people in the circle Remember! Time is critical here! You cannot atford to be slow to find out where to stand. So, In EACH iteration, your algorithm should be able to find the limination position without rotating the cirelo more than its current slz o Named aftor Flavius Josophus, a Jewish historian Iming in the 1st century. According to Josephus account of the siege of Yodfat, he and his comrade soldiers were trapped in a cave, the exit of which was blocked by Romans. They chose suicice over capture and decided that they would a circle and start kiling themselves using a tap Of three Josapnus and another man remained alive o o Dont be confused! Position here does not mean an index value. It means the position aat and gave up to the Romans The goal is to cetermine where to stand in the circe so that you are the last person alive magine that you are in the same situation jut ke Favius Josephus. You are in danger! However. you are a programmer and smart enough to build an aigonthm that tels you where o stand n the circle to You have three clase(1) MySavorl 1 (driver), (2) Josephus, and (3) Stopwatch Make sure you document your cod? and indicato ny ahoices you maie in implementing those mothod . Each mathod should have a documentation descnbing ita purpose. in the orclo to survivo. As you can imagine, time is critical here. You need to quickly implement and com pare three differen Zip roport2, samplo output, and all clasaos into a single ono and aubm it via Blazaxios methods in the Sosephus class and decide which method is the fassest to use for you to survive You are to implement throe differont mothods to sovo the Josophus problom. Step-by-step guide Undorstand how Josophus probiem works. of execution are as follows using Quoue data For your undorstanding, the steps structure (aize , rotation 3 Initial Circle: 1 23456 After the " execution: 4 5612 After the 2d oxoouion: 1 2 45 After the 3" execution: 51 2 After the 4 execution: 5 1 Atter the 5 execution: 1 (1 survives)Explanation / Answer
* Using LinkedList class as Queue/Deque to find the survivor's position.
// CPP program to find last man standing
#include<bits/stdc++.h>
using namespace std;
/* structure for a node in circular
linked list */
struct Node
{
int data;
struct Node *next;
};
// To create a new node of circular
// linked list
Node *newNode(int data)
{
Node *temp = new Node;
temp->next = temp;
temp->data = data;
}
/* Function to find the only person left
after one in every m-th node is killed
in a circle of n nodes */
void getJosephusPosition(int m, int n)
{
// Create a circular linked list of
// size N.
Node *head = newNode(1);
Node *prev = head;
for (int i = 2; i <= n; i++)
{
prev->next = newNode(i);
prev = prev->next;
}
prev->next = head; // Connect last
// node to first
/* while only one node is left in the
linked list*/
Node *ptr1 = head, *ptr2 = head;
while (ptr1->next != ptr1)
{
// Find m-th node
int count = 1;
while (count != m)
{
ptr2 = ptr1;
ptr1 = ptr1->next;
count++;
}
/* Remove the m-th node */
ptr2->next = ptr1->next;
ptr1 = ptr2->next;
}
printf ("Last person left standing "
"(Josephus Position) is %d ",
ptr1->data);
}
/* Driver program to test above functions */
int main()
{
int n = 14, m = 2;
getJosephusPosition(m, n);
return 0;
}
*Using ArrayDeque class as Queue/Deque to find the survivor's position.
#include<iostream.h>
template <class T>
class ex
{
private:
struct node
{
T data;
struct node *next;
};
struct node *head,*front,*rear;
public:
ex()
{
head=new node;
head->next=NULL;
front=rear=head;
}
void enqueue(T x);
T dequeue();
void print();
void move_next();
};
//////////////////Implementation file
#include "ex.h"
template <class T>
void ex<T>::enqueue(T x)
{
node *p;
p=new node;
p->data=x;
if(head->next==NULL)
{
front=rear=p;
head->next=p;
p->next=p;
}
else
{
rear->next=p;
p->next=front;
rear=rear->next;
}
}
template<class T>
T ex<T>::dequeue()
{
node *t;
T x;
t=front;
x=t->data;
front=front->next;
rear->next=front;
delete(t);
return x;
}
template<class T>
void ex<T>::print()
{
node *p=front;
do
{
cout<<p->data<<endl;
p=p->next;
}while(p!=rear->next);
}
template<class T>
void ex<T>::move_next()
{
front=front->next;
rear=rear->next;
}
/////////////////Application file
#include "ex.cpp"
void main()
{
ex<int> e;
int m,n,i,d;
cout<<"Enter the number of people
";
cin>>n;
cout<<"Enter the number of passes
";
cin>>m;
for(i=1;i<=n;i++)
e.enqueue(i);
cout<<"The players are
";
e.print();
cout<<"Eliminated in order
";
while(n>1)
{
for(i=1;i<=m;i++)
e.move_next();
d=e.dequeue();
cout<<d<<endl;
n--;
}
d=e.dequeue();
cout<<"Winning player: "<<d<<endl;
}
Time Complexity: O(n)
// CPP program to find last man standing
#include<bits/stdc++.h>
using namespace std;
/* structure for a node in circular
linked list */
struct Node
{
int data;
struct Node *next;
};
// To create a new node of circular
// linked list
Node *newNode(int data)
{
Node *temp = new Node;
temp->next = temp;
temp->data = data;
}
/* Function to find the only person left
after one in every m-th node is killed
in a circle of n nodes */
void getJosephusPosition(int m, int n)
{
// Create a circular linked list of
// size N.
Node *head = newNode(1);
Node *prev = head;
for (int i = 2; i <= n; i++)
{
prev->next = newNode(i);
prev = prev->next;
}
prev->next = head; // Connect last
// node to first
/* while only one node is left in the
linked list*/
Node *ptr1 = head, *ptr2 = head;
while (ptr1->next != ptr1)
{
// Find m-th node
int count = 1;
while (count != m)
{
ptr2 = ptr1;
ptr1 = ptr1->next;
count++;
}
/* Remove the m-th node */
ptr2->next = ptr1->next;
ptr1 = ptr2->next;
}
printf ("Last person left standing "
"(Josephus Position) is %d ",
ptr1->data);
}
/* Driver program to test above functions */
int main()
{
int n = 14, m = 2;
getJosephusPosition(m, n);
return 0;
}
*Using ArrayDeque class as Queue/Deque to find the survivor's position.
#include<iostream.h>
template <class T>
class ex
{
private:
struct node
{
T data;
struct node *next;
};
struct node *head,*front,*rear;
public:
ex()
{
head=new node;
head->next=NULL;
front=rear=head;
}
void enqueue(T x);
T dequeue();
void print();
void move_next();
};
//////////////////Implementation file
#include "ex.h"
template <class T>
void ex<T>::enqueue(T x)
{
node *p;
p=new node;
p->data=x;
if(head->next==NULL)
{
front=rear=p;
head->next=p;
p->next=p;
}
else
{
rear->next=p;
p->next=front;
rear=rear->next;
}
}
template<class T>
T ex<T>::dequeue()
{
node *t;
T x;
t=front;
x=t->data;
front=front->next;
rear->next=front;
delete(t);
return x;
}
template<class T>
void ex<T>::print()
{
node *p=front;
do
{
cout<<p->data<<endl;
p=p->next;
}while(p!=rear->next);
}
template<class T>
void ex<T>::move_next()
{
front=front->next;
rear=rear->next;
}
/////////////////Application file
#include "ex.cpp"
void main()
{
ex<int> e;
int m,n,i,d;
cout<<"Enter the number of people
";
cin>>n;
cout<<"Enter the number of passes
";
cin>>m;
for(i=1;i<=n;i++)
e.enqueue(i);
cout<<"The players are
";
e.print();
cout<<"Eliminated in order
";
while(n>1)
{
for(i=1;i<=m;i++)
e.move_next();
d=e.dequeue();
cout<<d<<endl;
n--;
}
d=e.dequeue();
cout<<"Winning player: "<<d<<endl;
}
Time Complexity: O(n)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.