数组练习2

现在游戏规则如下：

500个小孩首尾相连拉成一个圆圈，从第0个小孩起，依次报数，每当数到3，该小孩退出圈，下一个小孩接着从1开始报数。如此下去圈中的小孩越来越少，求最后一个小孩是哪一个。

代码采用两种方法解决这个问题。

代码如下：

class Children {
	public static void main(String[] args) {
		play2();
		play1();
	}
	
	public static void play1() {	//算法一
		boolean[] a = new boolean[500]; //false表示在圈子里面
		int count = 0; //数数计数器
		int pos = 0; //下标计数器
		int total = a.length; //人数

		while(total != 0) {
			if(!a[pos]) count++;	//如果小孩在圈内，则数数计数器增加
			if(count == 3) {	//如果到3
				a[pos] = true;	//小孩出去
				count = 0;	//数数技术器归0
				total--;	//总人数--
			}
			pos++;	//下标右移
			pos %= a.length;	//处理越界问题
		}
		System.out.println(--pos == -1? a.length - 1:pos);
	}
	public static void play2() {	//算法2
		//初始化小孩数组，每个小孩指向下一个小孩坐标
		int[] a = new int[500];		
		for(int i=0; i<a.length; i++) a[i] = (i+1)%a.length; 

		int current = 0;	//记载当前位置
		int previous = a.length-1;	//	//记载前一个位置
		int count = 1;	//计数器
		while(previous != current) { //前一个小孩和当前小孩是同一个的时候结束循环
			//向后面数数
			previous = current;	
			current = a[current];
			//如果数到3的倍数,则将前一个小孩指向当前小孩的下一个小孩下标位置
			if(++count%3 == 0) a[previous] = a[current]; 
		}
		System.out.println(current);
	}
}

 

评论

1 楼 run_xiao 2008-08-06  

约瑟夫环问题，我记得在哪里看到过有个超简单的算法解这个问题的，不过需要做一次数学的变化，不过具体怎么做的不记得了