Java USES circular linked list structure to solve Joseph problem

  • 2020-04-01 03:39:06
  • OfStack

This paper illustrates the method of solving Joseph problem by using circular linked list structure in Java. Share with you for your reference. Specific analysis is as follows:

This is the first Java exam question, for those of you who haven't looked at the linked list will not do it, now looking back, it is really not difficult.

Joseph's question:
There are n individuals whose Numbers are 1,2,3... , n. The n men are arranged in a circle in order. Now, given s and d, we start at the s's and we go from one to one, and then we go from one to one, and then we go from one to one, and then we go from one to one, and then we go from one to one, and then we go from one to the other, and then we go from one to the other, and then we go from one to the other, and then we go from one to the other, and so on, and so on, and so on, and so on, and so on, and so on. It is required to define a node class and solve the Joseph problem by using the circular linked list structure.

The following Java version of the answer:

import java.util.Scanner;
public class LinkNode {              //Node class of a one-way linked list
    public int data;                 //Store node value
    public LinkNode next;            //Holds a reference to the node value
   
    public LinkNode(int k){         //Construct a 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 loop list of n
        LinkNode q,tail;
        
        LinkNode head = new LinkNode(i);
        head.next = head ;
        tail = head;             //The first node, tail and head together
       
        while(i<n){
            i++;
            q = new LinkNode(i);    //Add a new node
            q.next = head ;        //The reference to the node points to the header
            tail.next = q;            //The reference to the last element points to q
            tail = q;              //So the last element is q
        }         int j= 0;               //Count from s, and then output the serial number
        LinkNode p = head;      //Count starting point
        while(j<s-1){
            j++;
            p = p.next;
        }
        while(p.next != p){
            j = 1;
            while(j<d-1)   //The starting point of the count is
            {
                j++;
                p = p.next;
            }       
            System.out.print(p.next.data + " ");  //The node number of the output column is
            p.next = p.next.next;
            p = p.next;                                //Keeps pointing to the next node & NBSP;                     < br / >         }
        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 has been helpful to your Java programming.


Related articles: