Question

In an ancient land, the beautiful princess Eve (or handsome prince Val) had many suitors. Being royalty, it was decided that a special process must be used to determine which suitor would win the hand of the prince/princess. First, all of the suitors would be lined up one after the other and assigned numbers. The first suitor would be number 1, the second number 2, and so on up to the last suitor, number n. Starting at 4 the suitor in the first position, she/he would then count three suitors down the line (because of the three letters in his/her name) and that suitor would be eliminated and removed from the line. The prince/princess would then continue, counting three more suitors, and eliminate every third suitor. When the end of the line is reached, counting would continue from the beginning. For example, if there were 6 suitors, the elimination process would proceed as follows:_____.

12456 Suitor 3 eliminated; continue counting from 4.
1245 Suitor 6 eliminated; continue counting from 1.
125 Suitor 4 eliminated; continue counting from 5.
15 Suitor 2 eliminated; continue counting from 5.
1 Suitor 5 eliminated; 1 is the lucky winner.
Write a program that creates a circular linked list of nodes to determine which position you should stand in to marry the princess if there are n suitors. Your program should simulate the elimination process by deleting the node that corresponds to the suitor that is eliminated for each step in the process.

Answer 1

Step-by-step explanation:

public class CircularLinkedListTest

{

private Node head;

private int size;

private class Node

{

private int num;

private Node next;

public Node(int n)

{

num = n;

next = null;

}

public int getNum()

{

return num;

}

public void setNext(Node n)

{

this.next = n;

}

public Node getNext()

{

return next;

}

}

public CircularLinkedListTest ()

{

head = null;

int numNodes = 0;

}

public void add(int num)

{

int numNodes = 0;

if(head == null)

{

head = new Node(num);

head.setNext(head);

numNodes++;

}

else

{

Node temp = head;

while(temp.getNext() != head)

temp = temp.getNext();

temp.setNext(new Node(num));

temp.getNext().setNext(head);

numNodes++;

}

}

public int size()

{

int numNodes = 0;

return numNodes;

}

public int get(int index)

{

Node t = head;

for(int i = 0; i < index; i++)

t= t.getNext();

return t.getNum();

}

public int remove(int index)

{

if(index < 0 || index >= size)

{

System.out.println("Error, index out of Qbounds.");

System.exit(0);

}

Node temp = head;

if(index == 0)

{

while(temp.getNext() != head)

temp = temp.getNext();

int value = head.getNum();

if(size > 1)

{

head = head.getNext();

temp.setNext(head);

}

else

head = null;

size--;

return value;

}

else

{

for(int i = 0; i < index - 1; i++)

temp = temp.getNext();

int answer = temp.getNext().getNum();

temp.setNext(temp.getNext().getNext());

size--;

return answer;

}

}

public static void main(String args[])

{

CircularLinkedListTest suitors = new CircularLinkedListTest ();

for(int i = 1; i <= 6; i++)

suitors.add(i);

int currentIndex = 0;

while(suitors.size() != 1)

{

for(int i = 1; i <= 2; i++)

{

currentIndex++;

if(currentIndex == suitors.size())

currentIndex = 0;

}

suitors.remove(currentIndex);

if(currentIndex == suitors.size())

currentIndex = 0;

for(int i = 0; i < suitors.size(); i++)

System.out.print(suitors.get(i) + " ");

System.out.println();

}

}

}