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();
}
}
}
}