圆圈中最后剩下的数字

推荐阅读约瑟夫环实例（1）

题目：0，1，...，n-1这n个数字排成一个圆圈，从数字0开始每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。

注意要点:

• 所说的第几个数字是从第一个数字开始的，这与我们常识一致，请不要纠结有无第0个数字------没有！

• 在着手解题以前，取余运算的一些性质需要熟悉：一、某数取余多次与取一次相等，例如5%2=1，而5%2%2%2=1；二、取余运算满足结合律，例如a%n - 1=(a-1)%n (n > 1)；三、如果对于一个明显不在[0, n-1]区间的数x，在该区间的同余数有且只有1个。例如x = -2，-2%n=n-2。

 思路一：分析每次被删除数字的规律直接计算出圆圈中最后剩下的数字。

函数原型int LastRemaining(int n, int m)       //n为总人数，m为第m个数字需要删除

先假设n，m的取值都是合乎规范的。将守护代码放在最后进行讨论。第一次被剔除的数字是(m-1)%n。令k=(m-1)%n，剩下n-1个数字，分别是0,1,...,k-1,k+1,...,n-1。调整顺序，作出如下处理。

图  1

设隐函数f(n,m)为在n个数字中每次删除第m个数字最后剩下的数字。观察图1的右边一列，套用定义，最后剩下的数字是f(n-1,m)。还需要用它的值反解出真实的数字（逆映射）。

Y->X: x = (y+k+1)%n        //对照图1找规律就可以了，没有任何技巧 

故而f(n,m)=[f(n-1,m)+k+1]%n，其中k=(m-1)%n，代入得f(n,m)=[f(n-1,m)+m]%n（如果觉得哪里费解的话，想一想开篇提到的注意要点）。差不多已经能够看出这是递推公式了，但是出于严谨，应该往下再看一步。

图2

如图2，将被剔除的数字是(m-1)%(n-1)  n-1是一个整体，不要理解错了，其意义为当前数字个数。令j = (m-1)%(n-1)。如法炮制。

图  3

图3右边一列又可以套用定义，最后剩下的数字是f(n-2,m)。

 Y->X: x=(y+j+1)%(n-1)        //对照图3找规律就可以了，没有任何技巧 

故而f(n-1)=[f(n-2)+j+1]%(n-1)，其中j=(m-1)%(n-1)，代入得到f(n-1)=[f(n-2)+m]%(n-1)。这下我们就可以很放心地给出递推公式：

图  4

可以用递归或迭代（循环）来实现。

class Solution {
public:
    int LastRemaining_Solution(int n, int m)
    {
        if(n < 1 || m < 1)        //守卫代码
            return -1;
        if(n == 1)
            return 0;
        return (LastRemaining_Solution(n-1, m) + m) % n;
    }
};

图  5递归版本

class Solution {
public:
    int LastRemaining_Solution(int n, int m)
    {
        if(n < 1 || m < 1)        //守卫代码
            return -1;
        int last = 0;
        for(int i = 2; i <= n; ++i)
            last = (last + m) % i;
        return last;
    }
};

图6  迭代版本