Write the code with java using Circular Linked List: The Josephus Problem is a f

Question

Write the code with java using Circular Linked List:

The Josephus Problem is a famous mathematical puzzle that goes back to ancient times. There are many stories to go with the puzzle. One is that Josephus was one of a group of Jews who were about to be captured by the Romans. Rather than be enslaved, they chose to commit suicide.

They arranged themselves in a circle and, starting at a certain person, started counting off around the circle. Every nth person had to leave the circle and commit suicide. Josephus decided he didn%u2019t want to die, so he arranged the rules so he would be the last person left. If there were (say) 20 people, and he was the seventh person from the start of the circle, what number should he tell them to use for counting off? The problem is made much more complicated because the circle shrinks as the counting continues.

Create an application to model this problem.

Inputs are:

%u2022 number of people in the circle,

%u2022 number used for counting off, and

%u2022 number of the person where counting starts (usually 1).

The output is the list of persons being eliminated.

When a person drops out of the circle, counting starts again from the person who was on his left (assuming you go around clockwise).

Here%u2019s an example test scenario:

There are seven people numbered 1 through 7, and you start at 1 and count off by threes. People will be eliminated in the order 4, 1, 6, 5, 7, 3. Number 2 will be left.

Test your code with the test scenario above to make sure that the output is correct. Provide other 4 test scenarios.

Calculate and print the memory used in bytes and CPU time for each test scenario you will provide. Discuss the findings in your documentation. HINT: You can use System.currentTimeMillis() to find the current time of the system in milliseconds%u2026.

Explanation / Answer

import java.util.Collection; import java.util.LinkedList; import java.util.ArrayList; import java.util.Iterator; import weiss.nonstandard.BinarySearchTreeWithRank; public final class Josephus { /** * Return the winner in the Josephus problem. * Linked list implementation. * (Can replace with ArrayList or TreeSet). */ public static int jos1( int people, int passes ) { Collection theList = new LinkedList( ); // Construct the list for( int i = 1; i

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.