Java通过索引值实现约瑟夫环算法

问题描述：n个人围成一圈，从第一个人开始报数，报到m的人出圈，
剩下的人继续从1开始报数，报到m的人出圈；如此往复，直到所有人出圈

很多实现是使用链表结构，让元素构成一个圈，而我使用底层是数组的arraylist集合实现，并且不需要遍历搜索，依靠数组特性：索引值，通过数学计算，让索引值构成一个圈，每次算出来的索引值，对应的那个元素一定是下一个出局的元素

这样的话，有n个元素，就只需要计算n次，删除n次，无需搜索，最大程度优化了程序的时间

import java.util.arraylist;
import java.util.scanner;
public class 约瑟夫环3 {
	public static void main(string[] args) {
		/*问题描述：n个人围成一圈，从第一个人开始报数，报到m的人出圈，
		剩下的人继续从1开始报数，报到m的人出圈；如此往复，直到所有人出圈*/
		scanner sc = new scanner(system.in);
		int n = sc.nextint();//n个人
		int m = sc.nextint();//m号出列
		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();
				}
			}
	}
}

以上所述是小编给大家介绍的java通过索引值实现约瑟夫环详解整合，希望对大家有所帮助