CSDN链接 

    问题描述：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。求最后剩下的人的初始编号。

    可以把问题转换成：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。则所得的解加1即为原问题的解；

      一般我们采用一个循环队列来模拟约瑟夫环的求解过程，但是如果n比较大的时候，采用模拟的方式求解，需要大量的时间来模拟退出的过程，而且由于需要占用大量的内存空间来模拟队列中的n个人，并不是一个很好的解法。
在大部分情况下，我们仅仅需要知道最后那个人的编号，而不是要来模拟一个这样的过程，在这种情况下，可以考虑是否存在着一种数学公式能够直接求出最后那个人的编号。

    我们知道第一个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）:
我们先看第一个人出列后的情况，显而易见，第一个出列的人的编号一定是m%n-1,这个人出列后，剩下的n-1个人组成了一个新的约瑟夫环，这个约瑟夫环的第一个人在最开始的环中的编号是k=m%n（就是第一个出列的人的下一个）
k  k+1  k+2  ... n-2, n-1, 0, 1, 2, ... k-2并且从k开始报0。
    事实上，第一个出列的人的编号 m%n-1==k-1,在他被出列后，剩下的人又映射成为一个新的环：

   原编号   新编号
    k   ---   0
    k+1 ---   1
    k+2 ---   2
     ...  ....

   n-1  --- n-k-1

    0   ---  n-k

    1   --- n-k+1

        ...  ...

   k-3 ---   n-3

   k-2 ---  n-2

  (k-1已经被出列)

--------------------------------------------------一个循环

    可以看出，这就是原问题中把n替换成n-1的情况，设最终胜利的那个人在这种编号环境里（已经出列一个元素，编号范围为0 ------- n-2）的编号为x，则我们可以求出这个人在原编号环境（初始编号范围 0----n-1）下的编号（x+k）%n.

    我们用f(n)表示n个人的情况(编号环境)下的胜利者的编号，则我们要求的为f(n);

    那么如何知道n-1个人下面的这个x呢，yes，就是n-2个人情况下得到的x‘倒推回去，那么如何知道n-2情况下的x‘呢，当然是求n-3个人，这就是一个递归的过程  f(n) = (f(n-1)+m)%n.

    当最后剩下一个人（最新编号为0）的时候，无论m为几，这个人总是胜利者，即f(1)=0;

    根据以上推理可以得到递推式
        f(1) = 0
        f(n) = (f(n-1)+m)%n
    那么我们要求f(n)，就从f(1)倒推回去即可.

（注意，我们这个算法是把编号为1---n 用 0----n-1替换的，所以最后求出来的编号+1才是最初问题的解，即f(n)+1）.

[cpp] view plaincopyprint?

 

1.  int f(int n, int m)  
2.    {  
3.        int r = 0;//即f(1)=0;  
4.        for(int i = 2; i <= n; i++)  
5.            r = (r + m) % i;//即f(i)=[f(i-1)+m]%n;  
6.        return r + 1; //即f(n)=1；  
7.     }</span>  

       这种方法比模拟的方法快多了，我们在碰到问题的时候，可以想一想是否有数学公式来求解 。

       参考出处：Jackie`s blog