Flavius Josephus was a famous historian of the first century, but apparently, he would not have lived to become famous without the exercise of his computational and mathematical abilities. A legend says that during the Jewish-Roman war he was part of a band of 41 rebels trapped in a cave by the Romans. To avoid capture, the rebels decided to form a circle and proceeded to kill every third remaining person until no one was left. However, Josephus quickly calculated where he and a friend should stand to avoid all this non-sense.
Write a program IN JAVA that given two positive numbers: a) the number of people in the circle, b) the elimination number, for example, if this number is exactly two, we eliminate every second person as in the original problem, determines the survivor’s position. Populate a (circular) linked list representing the band of rebels and repeatedly delete elements from it until only one remains.
source code:
package HomeworkLib;
public class GFG1 {
// Node class to store data
static class Node
{
public int data
;
public Node
next;
public Node( int
data )
{
this.data = data;
}
}
/* Function to find the only person
left
after one in every m-th node is
killed
in a circle of n nodes */
static void getJosephusPosition(int
m, int n)
{
// Create a
circular linked list of
// size N.
Node head = new
Node(1);
Node prev =
head;
for(int i = 2; i
<= n; i++)
{
prev.next = new Node(i);
prev = prev.next;
}
// Connect last
node to first
prev.next =
head;
/* 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;
}
System.out.println ("Last person left standing " +
"(Josephus Position) is " +
ptr1.data);
}
/* Driver program to test above
functions */
public static void main(String
args[])
{
int n = 14, m =
2;
getJosephusPosition(m, n);
}
}
if you have any doubts ask me..
Flavius Josephus was a famous historian of the first century, but apparently, he would not have...