//看了帖子后觉得有趣就实现了一把递归的约瑟夫算法
package test;
/**
* 500个小孩围成一圈，从第一个开始报数：1，2，3，1,2,3,1,2,3,……每次报3的小孩退出
问最后剩下的那个小孩，在以前500人里是第几个？？？
*/
public class Test {
/**
* 约瑟夫标准循环非递归解法
* @param n
* @param m
* @return
*/
public static int f2(int n, int m){
int index = 0;
for (int i = 2; i <= n; i++) {
index = (index + m) % i;
}
return index +1;
}
/**
* 约瑟夫递归算法
* @param n
* @param m
* @return 返回的结果+1 = 最终结果
*/
public static int f(int n,int m){
int t = 0;
if(n==1){
return t;
}else{
t = ( f(n-1, m) + m)%n;
}
return t;
}
public static void main(String[] args) {
//
int n = 500;
int m = 3;
//约瑟夫标准循环非递归解法
System.out.println(f2(n, m));//此方法来自帖子
/*
(函数)index表示(变量)n个人玩游戏报(常量)m退出最后胜利者的编号.则有递推公式：
index(1) = 0;
index(n) = (index(n-1) + m)%n; (n>1)
这个公式不是只考虑一种场景得出的结果，而是抽象出普遍的n得出的结论，
*/
/*
*f(1) = 0;//第0个
*f(2) = 1;//第1个
*f(3) = 1;//第2个
* */
//参考上面的提示写了下约瑟夫的递归算法
System.out.println(f(n, m)+1);
}
}
今天看到一个LinkedList版本的，测试了，结果一样，补充上：
public static int removeNM(int n, int m) {
LinkedList ll = new LinkedList();
for (int i = 0; i < n; i++)
ll.add(new Integer(i + 1));
int removed = -1;
while (ll.size() > 1) {
removed = (removed + m) % ll.size();
System.out.println("出列："+(ll.get(removed)));
ll.remove(removed--);
}
return ((Integer) ll.get(0)).intValue();
}
打印结果：
436
436