This time you are asked to create a program that given two positive numbers: the

Question

This time you are asked to create a program that given two positive numbers: the number of people in the circle. the elimination number, for example, if this number is exactly two we eliminate every second person, determines the survivor's number. Example Suppose there are 10 people in a circle and the elimination number is 2 then we proceed as follows: Start with the list 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 and initial position at 1. 1, , 3, 4, 5, 6, 7, 8, 9, 10 1, , 3, , 5, 6, 7, 8, 9, 10 1, , 3, , 5, 6, 7, 8, 9, 10 1, , 3, , 5, , 7, , 9, 10 1, , 3, , 5, , 7, , 9, 1, , , , 5, 7, , 9, 1, , , , 5, , , 9, 1, , , , 5, , , 9, , , , , 5, , , , , then 5 survives.

Explanation / Answer

Here is the code for Node.java:

/*
* Java Program to Implement Circular Singly Linked List
*/

import java.util.Scanner;

/* Class Node */
class Node
{
protected int value;
protected Node link;


/* Constructor */
public Node(int nm, Node n)
{
value = nm;
link = n;
}
/* Function to set link to next Node */
public void setLink(Node n)
{
link = n;
}
/* Function to set name to current Node */
public void setValue(int d)
{
value = d;
}
/* Function to get link to next node */
public Node getLink()
{
return link;
}
/* Function to get name from current Node */
public int getValue()
{
return value;
}
}

Here is the code for linkedList.java:

/* Class linkedList */
class linkedList
{
protected Node start ;
protected Node end ;
public int size ;

/* Constructor */
public linkedList()
{
start = null;
end = null;
size = 0;
}
/* Function to check if list is empty */
public boolean isEmpty()
{
return start == null;
}
/* Function to get size of the list */
public int getSize()
{
return size;
}
  
/* Function to insert element at end */
public void insertAtEnd(int val)
{
Node nptr = new Node(val,null);
nptr.setLink(start);
if(start == null)
{
start = nptr;
nptr.setLink(start);
end = start;
}
else
{
end.setLink(nptr);
end = nptr;
}
size++ ;
}
  
// Function to delete element at position
public void deleteAtPos(int pos)
{
if (size == 1 && pos == 1)
{
start = null;
end = null;
size = 0;
return ;
}
if (pos == 1)
{
start = start.getLink();
end.setLink(start);
size--;
return ;
}
if (pos == size)
{
Node s = start;
Node t = start;
while (s != end)
{
t = s;
s = s.getLink();
}
end = t;
end.setLink(start);
size --;
return;
}
Node ptr = start;
pos = pos - 1 ;
//for (int i = 1; i < size - 1; i++)
int i = 1;
while(true)
{
if (i == pos)
{
Node tmp = ptr.getLink();
tmp = tmp.getLink();
ptr.setLink(tmp);
break;
}
ptr = ptr.getLink();
i++;
}
size-- ;
return;
}
// Function to display contents
public void display()
{
//System.out.print(" Circular Singly Linked List = ");
Node ptr = start;
if (size == 0)
{
System.out.print("empty ");
return;
}
for(int i = 0; i < size-1; i++)
{
System.out.print(ptr.getValue() + "->");
ptr = ptr.getLink();
}
System.out.println(ptr.getValue());
}
}

Here is the code for Josephus.java:

/* Class CircularSinglyLinkedList */
import java.io.*;
import java.util.*;
public class Josephus
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
/* Creating object of linkedList */
linkedList list = new linkedList();
System.out.print("Enter the number of people in the circle: ");
int numOfPeople = scan.nextInt();
/* Preparing the circle. */
for(int i = 1; i <= numOfPeople; i++)
list.insertAtEnd(i);
System.out.print("The initial circle is: ");
list.display();
System.out.print("Enter the elimination number: ");
int eliminationNumber = scan.nextInt();
  
//Applying Josephus technique.
int currentPosition = eliminationNumber;
do
{
list.deleteAtPos(currentPosition);
currentPosition += eliminationNumber - 1;
list.display();
}while(list.getSize() != 1);
}
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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