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

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

问题QiIEACXa描述：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号出列QiIEACXa

int count = mhttp://;

ArrayList list = new ArrayList();

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通过索引值实现约瑟夫环详解整合，希望对大家有所帮助，如果大家有任何疑问请给我留言，会及时回复大家的。在此也非常感谢大家对我们网站的支持！

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。