The example in this article describes how Java uses a circular linked list structure to solve Joseph's problem. Share it with everyone for your reference. The specific analysis is as follows:
This is the first Java exam question. For students who have never seen a linked list, they will not know how to do it. Looking back now, it is really not difficult.
Joseph question:
There are n people, whose numbers are 1, 2, 3,..., n. These n people are arranged in a circle in order. Now given s and d, start counting from 1 in order from the sth person, and the person who counts to d will come out of the queue, and then start counting from the next person and start from 1 in order, and the person who counts to d will come out of the queue again. This cycle continues until everyone finally comes out. It is required to define a node class and use a circular linked list structure to solve Joseph's problem.
The following java version of the answer:
Copy the code as follows: import java.util.Scanner;
public class LinkNode { //Node class of one-way linked list
public int data; //Storage node value
public LinkNode next; //Storage reference of node value
public LinkNode(int k){ //Construction method, node with value k
data = k;
next= null;
}
}
class Josephus{
public static void printJosephus(int n,int s,int d){
int i=1; //Create a circular list of length n
LinkNode q,tail;
LinkNode head = new LinkNode(i);
head.next = head;
tail = head; //The first node, the tail and the head are together
while(i<n){
i++;
q = new LinkNode(i); //Add a new node
q.next = head; //The reference of the node points to the head
tail.next = q; //The reference of the last element points to q
tail = q; //Then the last element is q
}
int j= 0; //Start counting from s and output the number of the queuer in sequence.
LinkNode p = head; //Counting starting point
while(j<s-1){
j++;
p = p.next;
}
while(p.next != p){
j = 1;
while(j<d-1) //Starting point of counting
{
j++;
p = p.next;
}
System.out.print(p.next.data + " "); // Output the dequeued node number
p.next = p.next.next;
p = p.next; //Continuously point to the next node
}
System.out.print(p.data);
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt();
int a = input.nextInt();
int b = input.nextInt();
Josephus.printJosephus(n, a, b);
}
}
I hope this article will be helpful to everyone’s Java programming.