约瑟夫环详解

约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。

那么第一个死的是（m-1）%n号，现在只剩下来n-1人，从m%n开始报数。

m%n是n-1人的时候、编号为0的人的旧坐标，那么编号为i的人旧坐标为(m+i)%n,设第二次杀的人编号是x,那么他在旧坐标的位置为(m+x)%n。第二次的编号一定和第一次相同，所以有x'=(x+k)%n;

新编号中x的坐标就等于旧坐标中x'的坐标，所以坐标转换得到：x'=(x+k)%n;

得到了递推公式。f[i]=(f[i-1]+m)%i;

因此，可以得到:

class Solution {

public:

    int lastRemaining(int n, int m) {

        int f[n+1];

        f[1]=0;

        for(int i=2;i<=n;i++)

        {

            f[i]=(f[i-1]+m)%i;

        }

        return f[n];

    }

进一步简化：

class Solution {

public:

    int lastRemaining(int n, int m) {

        int res=0;

        for(int i=2;i<=n;i++)

        {

           res=(res+m)%i;

        }

        return res;

    }

};