约瑟夫环及其变体

1.问题描述

q1.已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。

q2.已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；原先编号为n的数是第几个出列的。

2.编程实现

q1 solution:

#include <iostream>
#include <queue>
using namespace std;
int main()
{
    int n,m,k;
    cin >>n>>m>>k;
    queue<int> q;
    for(int i=k;i<=n;i++)
        q.push(i);
    for(int i=1;i<k;i++)
        q.push(i);
    while(q.size()>1)
    {
        for(int i=0;i<m-1;i++)
        {
            q.push(q.front());
            q.pop();
        }
        q.pop();
    }
    cout<<q.front()<<endl;
    return 0;
}

q2 solution:

#include <iostream>
#include <queue>
using namespace std;
int main()
{
    int n,m,k;
    int res=0;
    cin >>n>>m>>k;
    queue<int> q;
    for(int i=k;i<=n;i++)
        q.push(i);
    for(int i=1;i<k;i++)
        q.push(i);
    while(q.size()>1)
    {
        for(int i=0;i<m-1;i++)
        {
            q.push(q.front());
            q.pop();//删除第一个元素
        }
        res++;
        if(q.front()==n)
            break;
        else
            q.pop();
    }
    cout<<res<<endl;
    return 0;
}