Java Realizes Joseph Ring Algorithm by Indexing Values

  • 2021-07-26 07:41:19
  • OfStack

Problem description: N people form a circle, starting from the first person to report the number, and those who report for m go out of the circle.
The rest of the people continue to report from 1, and those who report for m go out of the circle; Go back and forth until everyone is out of the circle

Many implementations are using linked list structure, so that elements constitute a circle, and I use the bottom is the array of ArrayList collection implementation, and do not need to traverse search, relying on the characteristics of the array: index value, through mathematical calculation, so that the index value constitutes a circle, each time the calculated index value, the corresponding element 1 is the next one out of the element

In this case, if there are n elements, you only need to calculate n times and delete n times without searching, which optimizes the program time to the greatest extent


import java.util.ArrayList;
import java.util.Scanner;
public class  Joseph's ring 3 {
	public static void main(String[] args) {
		/* Problem description: N Individual enclosure 1 Circle, from the first 1 Individuals start to report and report for duty m People out of the circle, 
		 The rest of the people continue from 1 Start counting and reporting m People out of the circle; Go back and forth until everyone is out of the circle */
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();//n Individual 
		int m = sc.nextInt();//m Number out of column 
		int count = m;
		ArrayList<Integer> list = new ArrayList<Integer>();
		for(int i = 1 ; i <= n ; i++){
			list.add(i);
		}
			for(; ;){
				if(list.size() == 1){
					System.out.print(list.get(0) + " ");
					return;
				}
				if(m <= list.size()){
					System.out.print(list.get(m-1) + " ");
					list.remove(m-1);
					m += count -1;
				
				}				
				if(list.size() < m){
					m = m - list.size();
				}
			}
	}
}

Related articles: