Do problem 5.5 on pages 248-249 using Java (one file only--multiple classes ok).

Question

Do problem 5.5 on pages 248-249 using Java (one file only--multiple classes ok).

Problem - 5.5:

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’t 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 that uses a circular linked list (like that in Programming Project 5.3) to model this problem. Inputs are the number of people in the circle, the number used for counting off, and the 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’s an example. 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.

Programming Project 5.3:

A circular list is a linked list in which the last link points back to the first link. There are many ways to design a circular list. Sometimes there is a pointer to the “start” of the list. However, this makes the list less like a real circle and more like an ordinary list that has its end attached to its beginning. Make a class for a singly linked circular list that has no end and no beginning. The only access to the list is a single reference, current, that can point to any link on the list. This reference can move around the list as needed. (See Programming Project 5.5 for a situation in which such a circular list is ideally suited.) Your list should handle insertion, searching, and deletion. You may find it convenient if these operations take place one link downstream of the link pointed to by current. (Because the upstream link is singly linked, you can’t get at it without going all the way around the circle.) You should also be able to display the list (although you’ll need to break the circle at some arbi- trary point to print it on the screen). A step() method that moves currentalong to the next link might come in handy too.

Explanation / Answer

import java.io.;
import java.util.;
import java.text.*;

public class ProgramTwo{
public static void main(String[] args) {

Scanner input = new Scanner(System.in);
int numberOfNums = 0;
int startingPoint = 0;
int passing = 0;

String end = "start";
String userInput;

while (end == "start"){

System.out.println("Please enter three numbers (Enter "stop" to quit): ");

if(input.hasNext()){
if(input.hasNextInt()){
numberOfNums = input.nextInt();
startingPoint = input.nextInt();
passing = input.nextInt();

System.out.println(numberOfNums + " and " + startingPoint + " and " + passing);

LinkList newList = new LinkList();
ListIterator iter = newList.getIterator();

int x = 1;
for(int i = 0; i < numberOfNums; i++){
iter.insert(x);
x++;
}
newList.displayList();

iter.beginningPoint(startingPoint);
iter.delete(passing, numberOfNums);

}else if(input.hasNext()){
userInput = input.next();
boolean x = false;
while(x == false){
if(userInput.equals("stop")){
end = "stop";
System.out.println("END PROGRAM");
x = true;
}else{
System.out.println("Please enter a proper command: ");
userInput = input.next();
}
}
}
}
}
}
}

class Link{

public int dData;
public Link next;

public Link(int data){
dData = data;
}

public void displayLink(){
System.out.print(dData + " ");
}

}

class LinkList{

private Link first;

public LinkList(){
first = null;
}

public Link getFirst(){
return first;
}

public void setFirst(Link f){
first = f;
}

public boolean isEmpty(){
return first == null;
}

public ListIterator getIterator(){
return new ListIterator(this);
}

public void displayList(){
Link current = first;
while(current != null){
current.displayLink();
current = current.next;
}
System.out.println("");
}

}

class ListIterator{

private Link current;
private Link previous;
private LinkList ourList;

public ListIterator(LinkList list){
ourList = list;
reset();
}

public void reset(){
current = ourList.getFirst();
previous = null;
}

public boolean atEnd(){
return(current.next == null);
}

public boolean atEndPrevious(){
return(previous.next == null);
}

public Link getCurrent(){
return current;
}

public void nextLink(){
previous = current;
current = current.next;
}

public void insert(int value){
Link newLink = new Link(value);
if(ourList.isEmpty() == true){
ourList.setFirst(newLink);
current = newLink;
}else{
newLink.next = current.next;
current.next = newLink;
nextLink();
}
}

public void beginningPoint(int begin){
if(begin == 1){
current = ourList.getFirst();
previous = null;
// System.out.println("Current Location: " + current.dData);
}else if(begin != 1){
current = ourList.getFirst();
previous = null;
for(int i = 1; i < begin; i++){
nextLink();
// System.out.println("Current Location: " + current.dData);
}
}
}

public void delete (int skips, int length){

while(current != previous){
for(int i = 0; i < skips; i++){
if(atEnd() == true){
previous = current;
current = ourList.getFirst();
}else{
previous = current;
current = current.next;
}
}
if(atEnd() == true){
System.out.println("Value removed: " + current.dData);
previous.next = current.next;
current = ourList.getFirst();
ourList.displayList();
}else{
if(current == ourList.getFirst()){
System.out.println("Value removed: " + current.dData);
previous.next = null;
ourList.setFirst(current.next);
current = ourList.getFirst();
ourList.displayList();
}else{
System.out.println("Value removed: " + current.dData);
previous.next = current.next;
current = current.next;
ourList.displayList();
}
}
}
}
}

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

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