首页 > Java > 高级篇 > 约瑟夫环问题Java求解 核心代码仅4行
2014
06-15

约瑟夫环问题Java求解 核心代码仅4行

问题:有100个人围成一个圈,从1开始报数,报到14的这个人就要退出。然后其他人重新开始,从1报数,到14退出。问:最后剩下的是100人中的第几个人?

这个题目是自己在做黑马程序员入学测试时遇到的,想了一个多小时,终于想到了自己的解决方法,网上的过程很繁杂,其实真正的核心代码也就4行,上代码:

public class Test10 {
	public static void main(String[] args) {
		/*
		 * 先说说我做这题的思路:
		 * 1、创建一个含有100个元素的集合,元素从1到100。(分别对应这100个人)
		 * 2、从1数到14算一圈,则相当于走了99个圈,每走一圈从集合里删除一个元素。
		 * 3、走完这99圈以后,集合里剩下的那个元素就是最后剩下的人
		 *
		 * 这里最关键的就是求每次从集合里删除的那个元素的下标。
		 */
		//创建一个集合all,集合中的元素为1,2,3,……,100,代表所有人
		List<Integer> all = new LinkedList<Integer>();
		for(int i = 1;i <= 100;i++){
			all.add(i);
		}

		//下面的代码表示循环99次,每次从集合里删除一个元素,代表退出的那个人的编号
		//i表示退出的那个人在all集合中的下标
		int i = 0;
		//循环99次
		for(int n = 1;n < 100;n++){
			//每次循环时,求得将要退出的人在集合中的下标
			i = (i + 13) % all.size();
			//将集合中代表该人的元素删除
			all.remove(i);
		}

		//循环99次,删除99个人,剩下的最后一个,就是你了
		System.out.println("最后剩下的是第 " + all.get(0) + " 个人");

		/*
		 * 不难看出,本题最核心的还是求每次循环时需要删除的那个元素的下标。
		 */

	}
}

代码虽少,但不代表时间复杂度就降低了,只是更便于理解了。有兴趣的童鞋可以对比下本代码和网上代码的执行速度


约瑟夫环问题Java求解 核心代码仅4行》有 3 条评论

  1. 李中原 说:

    您这个算法自己测试过吗?

  2. 抬头苦干 说:

    学习了!最关键的部分在于index = (index+length-1) % length

留下一个回复

你的email不会被公开。