//从0~n-1这n个数字构成环形，从0开始每次删除第m个数字，求最后一个剩下的数字 //要么借助环形链表数据结构
//要么通过数学建模找到规律

#include <iostream>
#include<list>
using namespace std;
//**********************方法一环形结构****************************
//std::list本身并不是一个环形结构，因此每当迭代器扫描到末尾时候，我们要把迭代器移到链表头部，
//Lists将元素按顺序储存在链表中. 与 向量(vectors)相比, 它允许快速的插入和删除，但是随机访问却比较慢.
int LastRemaining(unsigned int n,unsigned int m){
    if(n<1 || m<1)
        return -1;
    unsigned int i=0;
    list<int> numbers;
    for(i=0;i<n;i++)
        numbers.push_back(i);//0~n-1
    list<int>::iterator current=numbers.begin();
    while(numbers.size()>1){
        for(int i=1;i<m;i++){//找到第m个要删除的位置
            current++;//current指向要删除的位置
            if(current==numbers.end())
                current=numbers.begin();

        }
        list<int>::iterator next=++current;
        if(next==numbers.end())
            next=numbers.begin();
        --current;
        numbers.erase(current);
        current=next;
    }
    return *(current);
}
//**********************方法二数学建模****************************
//令f(n,m)表示从0开始删除第m个数字后的剩下的数字；第一个删除的数字是（m-1)%n，为了简单表示，我们令k=（m-1)%n。剩下的数字0,1,2，，，，k-1,k+1,k+2..n-1;
//下一次从k+1开始计数。相当于形成这样的序列：k+1,k+2...0,1...k-1。剩下的序列也是关于n,m的函数。但是这个序列的规律和最初的规律不一样。因此记为f'(n-1,m).
//最初序列剩下的数字一定是删除一个数字之后的序列最后剩下的数字，即f(n,m)=f'(n-1,m).
//定义一种映射 ，使得k+1,k+2...0,1...k-1 -》0,1.。。n-2，p(x)=(x-k-1)%n.逆映射p'(x)=(x+k+1)%n
//f(n,m)=f'(n-1,m)=p'(f(n-1,m))=[f(n-1,m)+k+1]%n=[f(n-1,m)+m]%n;
//综上，递归公式：f(n,m)=0   n=1
//                      =[f(n-1,m)+m]%n  n>1

int LastRemaining(unsigned int n,unsigned 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;
}
int main()
{
    int data[]={3,4,5,6,7,8};
    for(int i=0;i<6;i++)

        cout<<LastRemaining(data[i],3)<<" ";
    cout<<endl;

    return 0;
}