Java通过索引值实现约瑟夫环算法
问题描述:N个人围成一圈,从第一个人开始报数,报到m的人出圈,
剩下的人继续从1开始报数,报到m的人出圈;如此往复,直到所有人出圈
很多实现是使用链表结构,让元素构成一个圈,而我使用底层是数组的ArrayList集合实现,并且不需要遍历搜索,依靠数组特性:索引值,通过数学计算,让索引值构成一个圈,每次算出来的索引值,对应的那个元素一定是下一个出局的元素
这样的话,有n个元素,就只需要计算n次,删除n次,无需搜索,最大程度优化了程序的时间
importjava.util.ArrayList; importjava.util.Scanner; publicclass约瑟夫环3{ publicstaticvoidmain(String[]args){ /*问题描述:N个人围成一圈,从第一个人开始报数,报到m的人出圈, 剩下的人继续从1开始报数,报到m的人出圈;如此往复,直到所有人出圈*/ Scannersc=newScanner(System.in); intn=sc.nextInt();//n个人 intm=sc.nextInt();//m号出列 intcount=m; ArrayListlist=newArrayList (); for(inti=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() 以上所述是小编给大家介绍的Java通过索引值实现约瑟夫环详解整合,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对毛票票网站的支持!