【约瑟夫问题——队列】

【模拟和队列】

题目连接

P1996 约瑟夫问题

回顾知识

（1）队列实现约瑟夫环

（2）在队头进行删除数，边删除边输出。

（3）循环判断队头元素，将不需要删除的队头放在队尾，进行下次遍历。

解题思路

  （1）方法一：数据很少，直接模拟，详细见代码
  （2）方法二：队列 【STL常见用法】
  （3）方法三：运用链表，我觉得链表挺复杂的， 这个题，一般人都不用链表吧，直接pass

代码详解

方 法 一： 模拟

#include 

using namespace std;
const int N = 110;
bool visit[N] = {0};
int main()
{
    int n, m, s = 0;
    cin >> n >> m;
    for(int i = 0; i < n; i++) {     //i代表删除的次数
        for(int k = 0; k < m; k++) {
            if(++s>n) s = 1;         //指针s如果遍历到结尾就置1
            if(visit[s]) k--;
        }                            //如果已经删除就k--该数不进行再次删除
        cout << s << " ";
        visit[s] = true;
    }
    cout << endl;
    return 0;
}

方 法 二： 队列

#include 

using namespace std;
queue<int> a;
int main()
{
    int n, m, k = 1;
    cin >> n >>m;
    for (int i = 1; i <= n ;i++)
    {
        a.push(i);
    }
    while(!a.empty())
    {
        if(k == m)
        {
            cout<<a.front()<<" ";
            a.pop();
            k = 1;
        }else if(k != m)
        {
            k++;
            a.push(a.front());   //将不进行删除的数放在队尾进行下一轮
            a.pop();              //将放在队尾的队头元素删除
        }
    }
    return 0;
}

【过啦】！