大家看看我写的约瑟夫环(O(N))算法有没有问题

约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人会被杀死；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到剩下一个人生存。

?

　　n = 9,k = 1,m = 5　　【解答】

　　出局人的顺序为5,1,7,4,3,6,9,2,8。

?

题目引用了 百度百科??http://baike.baidu.com/view/717633.htm

?

当然，我们最关心的是最后的那个输出——不死的位置

?

这个题目我自己先做出了一个O（N^2)的，相信许多人都能直接地想到

?

?

package algorithm;import java.util.LinkedList;public class FastJosephus {public static int f(int n, int m){int[] res = new int[n+1];res[1] = 0;for(int i=2;i<=n;i++){int firstKilledPos = (m-1)%i;int livePos = res[i-1];res[i] = ((firstKilledPos+1)+livePos)%i;}return res[n];}public static int f2(int n, int m){int[] res = new int[n+1];res[1] = 0;for(int i=2;i<=n;i++){res[i] = (res[i-1]+m)%i;}return res[n];}public static int g(int n,int k ,int m ){return (f(n,m)+(k-1))%n + 1;}public static int g2(int n,int k ,int m ){return (f2(n,m)+(k-1))%n + 1;}public static void main(String[] args){System.out.println(g(7,1,4));System.out.println(g2(7,1,4));}}