java uses linked list to realize Joseph ring

  • 2021-07-24 10:56:05
  • OfStack

Joseph's ring is a mathematical application problem: people known as n (denoted by numbers 1, 2, 3... n respectively) sit around a round table. Start counting from the person numbered k, and the person who counts to m is listed; His next person started counting from 1, and the person who counted to m went out again; Repeat this rule until all the people around the round table are out of line. Find the queue sequence.

Using linked list, node data is the number.


package com.dm.test;
 
public class Test2
{
 public static void main(String[] args)
 {
 // Head node 
 Node root = new Node(1);
 int[] order = build(root,9,5);
 for(int i =0;i<order.length;i++)
 {
 System.out.print(order[i]+" ");
 }
 }
 // Build Joseph Ring 1 Linked list 
 public static int[] build(Node root,int n, int m)
 {
 Node current = root;
 for(int i = 2; i<=n; i++)
 {
 Node node = new Node(i);
 current.next = node;
 current = node;
 }
 current.next = root;
 int[] order = come(root,n,m);
 return order;
 }
 // Out of queue 
 // End condition: Only 1 Node, the of this node next Is itself 
 // Put the number out in 1 Of the arrays, the traversal array is the queue sequence 
 public static int[] come(Node root,int n, int m)
 {
 int[] order = new int[n];
 int j = 0;
 Node p = root;
 while(p.next!=p)
 {
 int i = 1;
 while(i<m-1)
 {
 p=p.next;
 i++;
 }
 if(i==m-1)
 {
 order[j]=p.next.data;
 j++;
 p.next = p.next.next;
 p=p.next;
 }
 }
 order[j]=p.data;
 return order;
 }
}
class Node
{
 int data;
 Node next;
 public Node(int data)
 {
 this.data = data;
 next= null;
 }
}

Related articles: