首页 > 编程 > Java > 正文

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

2019-11-26 09:02:18
字体:
来源:转载
供稿:网友

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

发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表