软件编程
位置：首页>> 软件编程>> java编程>> Java通过索引值实现约瑟夫环算法

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

作者：Mr-Rao　　发布时间：2021-09-28 22:33:48　

标签：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通过索引值实现约瑟夫环详解整合网站的支持！

来源：https://blog.csdn.net/Mr_Rao/article/details/89817172

0
投稿

猜你喜欢

手机版 软件编程 asp之家 www.aspxhome.com