约瑟夫问题

Description

实现一个循环链表,并解决约瑟夫问题:

n 个人围成一个圆圈，首先第1个人从1开始一个人一个人顺时针报数, 报到第m个人，令其出列。然后再从下一个人开始，从1顺时针报数，报到第m个人，再令其出列，…，如此下去, 直到圆圈中只剩一个人为止。此人即为优胜者

Input

输入约瑟夫问题中的n和m;

输入要插入循环队列的n个元素的值;

Output

按顺序输出所有被踢出队列的元素的值;

输出最终的优胜者;

#include<bits/stdc++.h>
using namespace std;
vector<int> yuesefeng(int n,int m);
int main()
{
    int n,m;
    cin>>n>>m;
    vector<int> out;
    out=yuesefeng(n,m);
    int i,len=out.size();
    for(i=0;i<len-1;i++)
        cout<<out[i]<<" ";
    cout<<endl;
    cout<<out[i]<<endl;
  
}
vector<int> yuesefeng(int n,int m)//n代表初始人数，m代表初始号码
{
    vector<int> out;
    list<int> in;
    list<int>::iterator pos;
    int elem;
    for (int i = 1; i <= n; i++)
    {
        cin>>elem;
        in.push_back(elem);
    }
    pos = in.begin();
    int cnt = m;
    while (!in.empty()) {
        if (cnt != 1) {
            pos++;
            cnt--;
            if (pos == in.end())//注意要判断是否到尾部了，到尾部就指向头部
                pos = in.begin();
        } else {
            cnt=m;
            out.push_back(*pos);//到数了，点到的人保存到输出
            pos = in.erase(pos);
            //将此人从列表中删除，注意erase返回的是下个人的指针
            if (pos == in.end())
                pos = in.begin();

        }
    }
    return out;
}