Josephus(约瑟夫)问题的数学方法　

  　前面的内容都是直接来来自于百度百科，后面才是我对这段话的理解

        无论是用链表实现还是用实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达O(nm)，当n，m非常大(例如上百万，上千万)的时候，几乎是没有办法在短时间内出结果的。我们注意到原问题仅仅是要求出最后的胜利者的序号，而不是要读者模拟整个过程。因此如果要追求效率，就要打破常规，实施一点数学策略。

为了讨论方便，先把问题稍微改变一下，并不影响原意： 问题描述：n个人（编号0~(n-1))，从0开始报数，报到m-1的退出 ，剩下的人继续从0开始报数。求胜利者的编号。 我们知道第一个人(编号一定是(m-1)%n) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）:

public class JOSEPHUS_Deep {

   public static void main(String[] args) {     int n, m, i, s=0;          m=5;n=6;       for (i=2; i<=n/2; i++) {//因为是从两个人开始计算，所以i=2，而不是0       s=(s+m)%i;      }      System.out.println("The winner is "+(s+1));    }   }

开始我看这段文字的时候都没怎么懂，可能是数学太差的原因吧！

   后来我就一句一句来看，结合实例：0 1 2 3 4 5  m=5.

移除4过后，的状态变成了：5 0 1 2 3.     k=m%n=5

如下表

现在我们把他们的编号做一下转换：

	k	k-5	k-4	k-3	k-2
X’	5	0	1	2	3
转换关系 ：X’=(x+k)%n（此例中：n=6）
x	0	1	2	3	4

于是呢，n个人的问题就变成了n-1个人的问题。

递推公式:

　　f[1]=0; //就是说如果只有一个人，那么最后的胜利者就是他，他的编号为0

　　f[i]=(f[i-1]+m)%i; (i>1) //如果不止一个人，有i个人，那么就需要求出i-1个人的最后胜利的结果f[i-1]，然后呢，利用递推公式x‘=(x+m)%n 就可以知道第i个的最后结果了。

例如：程序中有这样两句：s=0；s=(s+m)%i;

就是说：s=0表示只有一个人的结果。

计算第2个人的结果需要用到第1个人的结果

当i=2,m=5,得到s=1,表示2个人转圈的结果

当i=3，m=5，得到s=0，表示3个人转圈的结果。

最后，由于我们选择6个人转圈编号一般习惯为1 2 3 4 5 6 ，并不是0 1 2 3 4 5 6

所以输出结果需要s+1。

我现在想不懂的是，怎么来确定第i个人的出列编号……它列出是的最后的人！