The Josephus Game
Josephus Flavius was a famous Jewish historian of the first century at the time of the Second Temple destruction. During the Jewish-Roman war he got trapped in a cave with a group of 39 soldiers surrounded by romans. The legend has it that preferring suicide to capture, the Jews decided to form a circle and, proceeding clockwise around it, to kill every seventh person until only one was left, who must then commit suicide. Josephus, an accomplished mathematician, quickly found the safe spot in the circle (24th) to be the last to go. But when the time came, instead of killing himself he joined the Roman side.
The problem rightfully raises the question of how someone might be able to quickly compute the correct place to stand.
In this lab you are to simulate the Josephus problem. In the main driver
Josephus.java you choose two integer parameters. The first
number is the amount of soldiers in the problem (which will be ≥ 1), and the second
number is an elimination order - the amount you rotate the list to remove the next
soldier (it can be positive or negative integer or zero).
You remove nodes from the list according to the elimination order, for example, if
that number is 2 than you need to remove each second person. You always start with the
first node (labeled "1") and go to the end of the list removing nodes as it is specified.
When you remove a node you continue the process moving to the next node. Once you reach
the end you wrap around to the begining of the list. You repeat these steps until only
one node is left. The following example demonstrates the sequence of steps:
size = 5; <- number of people rotation = 2; <- elimination order : 1 2 3 4 5 <- starting sequence 1st step: 1 3 4 5 2nd step: 1 3 5 <- wrap around 3rd step: 3 5 : 3 <- survivor
size = 5; <- number of people rotation = -3; <- elimination order : 1 2 3 4 5 <- starting sequence 1st step: 1 2 3 5 <- to arrive at this result, count "1, 5, 4" 2nd step: 2 3 5 <- count "3, 2, 1" 3rd step: 3 5 : 3 <- survivor
You are to implement
DoublyCircularLL class and then solve the Josephus problem.
This class implements
ListInterface which shows which methods that you are expected to complete.
After the class is properly implemented you can finish the
josephusDCLL() method in the Josephus class.
(size, rotation) = answer (5,2) = 3 (5,-10) = 3 (5,1) = 5 (5,-5) = 5 (1, 5) = 1 (13,1) = 13 (40,7) = 24 (40,-7) = 18 (100,-2) = 29 (66,1) = 66 (66,100) = 7 (66,-100) = 61 (1000,123) = 2 (1000,-123) = 1000 (1000,1000) = 609 (1000,-1000) = 393 (-3,2) = exception (3,0) = exception
Do not submit anything else like zip files, folders, desktops, class files. Failure to do so will result in 10 points penalty.
Your assignment will be graded first by compiling and testing it. After that, we will read your code to determine whether appropriate method/classes were used, as well as judge the overall style and modularity of your code. Points will be deducted for poor design decisions and un-commented, or un- readable code..