杰哥私房题──约瑟夫问题

http://hi.baidu.com/wuxyy/blog/item/464471f03802fcafa40f523c.html
这里有解答

哈哈，这个算法我研究过，很多人讨论过这个无比经典的算法，真的是纯数学的脑子才想的出来的……
这里不知允不允许贴链接：
http://topic.csdn.net/u/20070916/15/11a62d59-3d7a-4aa6-81be-b1bef25ac404.html
这里提供了两种数学思路，第一种太复杂了，实在是不敢看下去…………
第二种我的理解是这样的，基于这个链接里的说法，不过这个说法我也看得一知半解……
f(i)表示从i个猴子中数到第m个退出的最后剩下的猴子编号，于是本问题要求的也就是f(n)。如果可以的话我们可以画一个n个猴子围成圈的图，方便理解。
于是：
假设从某个位置开始，我们标注1，然后不停的找，找到第一个m的位置，然后将它踢出去，从第m+1个位置接着找。一直到最后找到了f(n)，也就是问题的解。
注意了！这个意思也就是说，我们从n个猴子中从第1个开始找起和n-1个猴子中从第m+1个（相对于n个猴子中的m）找起的结果是一样的！这样我们就有了一个递归的思路……
那么这个问题现在我们这样思考，从n-1个猴子中从第m+1找起和第1个位置（上面定义的那个第1个位置）找起有什么关系呢？
我们不妨将m+1先简单想成2，n-1个猴子，从第1个位置找起和从第二个位置找起结果f(n-1)有什么不同？？？
一定是相差1！没有证明，但是想想那-1个猴子围成的圈就好像一个齿轮一样，它的找法都是一样的，所以就是一个错一个嘛，从第1个位置找起是f(n-1)，从第2个位置找起结果一定是f(n-1)+1嘛！！为了确保正确，应该是（f(n-1)+1)%n，也就是加个取模操作，注意此时长度是n-1,所以取模用n……
所以从第m+1个位置找起，一定就是（f(n-1)+m）%n嘛！
也就是说，n-1个猴子，从第m+1个找起的结果是（f(n-1)+m）%n。而上面说了，它又是和从n个猴子中从第1个找起是等价的，也就是f(n).
于是这个结论就出来了：f(n)=（f(n-1)+m）%n
同时初始条件f(1)=1.这样就可以用递归很简洁的写出来了………………

哎呀呀，用文字写确实麻烦多了，可是我觉得思路很明白，那些数学公式看着太头疼了，我觉得这样写出来反而明白。
看公式看不懂的不妨看看我的啊……哈哈，欢迎指教

学学小学奥数，有这个题。

用递归写了个

	private void josephus(int n, int m) {
		List list = new ArrayList();
		for (int i = 1; i <= n; i++) {
			list.add(i);
		}
		f(m, m - 1, list);
	}
	
	private void f(int m, int increase, List list) {
		
		if (list == null || list.size() == 0) return;
		if (list.size() == 1) {
			System.out.println(list.get(0));
			return;
		}
		
		m = checkSize(m, list.size());
		
		list.remove(m - 1);
		
		m = m + increase;
		f(m, increase, list);
	}
	
	private int checkSize(int m, int size) {
		if (m > size) {
			m = m - size;
		}
		
		if (m > size) {
			return checkSize(m, size);
		} 
		return m;
	}