剑指offer编程题—圆圈中最后剩下的数

题目描述
每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)

如果没有小朋友，请返回-1

解题思路
都放在代码注释了，不想写了:(
顺便复习一下上一篇约瑟夫问题求解。

/*题目描述
每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。
HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,
让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。
每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且
不再回到圈中,从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩
下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限
哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)
如果没有小朋友，请返回-1
*/
#include<iostream>
#include<list>
using namespace std;

//使用list容器循环,时间负责都比较高
class Solution {
public:
    int LastRemaining_Solution(int n, int m)
    {
        if(n<1) return -1;
        list<int> childs;
        for(int i=0;i<n;++i){
            childs.push_back(i);
        }
        auto it=childs.begin();
        while(childs.size()>1){
            for(int j=0;j<m-1;++j){
                ++it;
                if(it==childs.end()){
                    it=childs.begin();
                }
            }
            it=childs.erase(it);
            if(it==childs.end()) it=childs.begin();
            
        }
        return childs.front();
    }
};

/*迭代法
假设f(n, m) 表示最终留下元素的序号，例如f(6,2)=4；
又假设已知有n-1个小朋友玩游戏的答案为x，即f(n-1,m)=x；
则当n个小朋友一起玩游戏时，首先出列的是编号为m%n的小朋友，然后剩下n-1个小朋友，
又f(n-1,m)=x，所以有：f(n,m)=(m%n+x)%n=(m+x)%n,根据公式推理可以得到：
f(1)=0;
f(2)=(f(1)+m)%2=0;
f(3)=(f(2)+m)%3=2;
....
f(n)=(f(n-1)+m)%n;

*/
class Solution1 {
public:
    int LastRemaining_Solution(int n, int m)
    {
        if(n<1) return -1;
        int f=0;
        for(int i=2;i<=n;++i){
            f=(f+m)%i;
        }
        return f;
    }
};

int main(int argc,char **argv)
{
    Solution sol;
    int res=sol.LastRemaining_Solution(6,2);
    cout<<res<<endl;
    return 0;
}