In: Statistics and Probability
language C++
i need output, Pleases
The Josephus problem is named after the historian Flavius Josephus, who lived between
the years 37 and 100 CE. Josephus was a reluctant leader of the Jewish revolt against
the Roman Empire. When it appeared that Josephus and his band were to be captured,
they resolved to kill themselves. Josephus persuaded the group by saying, “Let us commit
our mutual deaths to determination by lot. He to whom the first lot falls, let him be
killed by him that hath the second lot, and thus fortune shall make its progress through
us all; nor shall any of us perish by his own right hand, for it would be unfair if, when
the rest are gone, somebody should repent and save himself” (Flavius Josephus, The
Wars of the Jews, Book III, Chapter 8, Verse 7, tr. William Whiston, 1737). Yet that is
exactly what happened; Josephus was left for last, and he and the person he was to kill
surrendered to the Romans. Although Josephus does not describe how the lots were
assigned, the following approach is generally believed to be the way it was done. People
form a circle and count around the circle some predetermined number. When this number
is reached, that person receives a lot and leaves the circle. The count starts over with
the next person. Using the circular linked list developed in Exercise 6, simulate this problem.
Your program should take two parameters: n, the number of people that start, and
m, the number of counts. For example, try n = 20 and m = 12. Where does Josephus need
to be in the original list so that he is the last one chosen?
class Node
{
public int iData;
public Node next;
public Node(int x) {
iData = x;
}
public void displayNode() {
System.out.print(iData + " ");
}
}
class CircularList
{
private Node first;
private Node last;
private Node current;
private int count; // total items in the list
public CircularList getCurrent;
public CircularList() {
first = null;
last = null;
current = null;
count = 0;
}
public boolean isEmpty() {
return first == null;
}
public void step() {
current = current.next;
}
public Node getCurrent() {
return current;
}
public Node getFirst() {
return first;
}
public void insert(int x) {
Node newNode = new Node(x);
if (isEmpty()) {
first = newNode;
current = first;
} else {
current.next = newNode;
}
newNode.next = first;
last = newNode;
step();
count++;
}
public boolean search(int x) {
Node search = first;
int y = 0;
while (search.iData != x && y < count) {
search = search.next;
y++;
}
if (search.iData == x) {
System.out.println("Found the value: " + search.iData);
return true;
} else {
System.out.println("Value not found in list");
return false;
}
}
public void delete(int x) {
Node prev = first;
Node curr = first.next;
while (curr.iData != x) {
prev = curr;
curr = curr.next;
}
if (count == 1) {
first = null;
count--;
} else if (curr == first) {
prev.next = curr.next;
first = curr.next;
count--;
} else {
prev.next = curr.next;
count--;
}
}
public void displayList() {
int x = 0;
Node printer = first;
while (x < count) {
printer.displayNode();
printer = printer.next;
x++;
}
System.out.println("");
}
}
class Josephus
{
private int numOfPeople; // number of people in a circle
private int countNum; // number used for counting off
private Node head;
private Node tail;
CircularList circle;
public Josephus() {
circle = new CircularList();
numOfPeople = 0;
countNum = 0;
}
public void setNumOfPeople(int x) {
numOfPeople = x;
}
public int getNumOfPeople() {
return numOfPeople;
}
public void setCountNum(int x) {
countNum = x;
}
public int getCountNum() {
return countNum;
}
public void addPeople() {
for (int i = 1; i < numOfPeople; i++) {
circle.insert(i);
}
}
public void move() {
for (int i = 0; i < countNum; i++) {
tail = head;
head = head.next;
}
System.out.println("KILLED : " + head.iData);
}
public void execute() {
tail = null;
head = circle.getFirst();
while (numOfPeople != 2) {
move();
circle.delete(head.iData);
tail = tail.next;
head = head.next;
numOfPeople--;
display();
}
}
public void display() {
System.out.print("Alive: ");
circle.displayList();
}
}
public class Test
{
public static void main(String[] args) {
Josephus suicide = new Josephus();
suicide.setNumOfPeople(20);
suicide.addPeople();
suicide.display();
suicide.setCountNum(12);
suicide.execute();
}
}
NOTE:: I HOPE YOUR HAPPY WITH MY ANSWER.....***PLEASE SUPPORT ME WITH YOUR RATING.....THANK YOU....