约瑟夫环问题

输入描述:

输入一行包含三个整数n,k,m
1<=n<=100,1<=k<=n-1,1<=m<=100

输出描述:

输出一个整数

5 1 2

3

n=2时，2没了，剩下1
n=4时，第一次去掉2,4，剩下1,3，接下来去掉了3，剩下1
n=8时，第一次去掉2,4,6,8,剩下1，3，5，7，第二次去掉3,7，剩下1,5，第三次去掉5，剩下1
F(n) = 2^k – 2^k-1 = 2^k-1     				n=2^k
F(n) = 2^k-1 – 2^k-2 = 2^k-2    			        n=2^k-1
......
F(2^2) = 2^2 – 2^1 = 2^1 					n=2^2
相当于，每次淘汰的时候，都会去掉一半人，所以从1开始的，最后肯定剩下了1。
结论：假如从x开始的，F(2^k)=x

    2.当人数n不为 时，例如：3，5，7，9......

这时候，新的约瑟夫环的1号位置，是旧约瑟夫环的3号，就成了一个人数为的，首位置为3号的新约瑟夫环。
F(8) = F(2^3) = 1，也就是说这里的1代表的就是上一个问题中的3号。所以F(9) = 3。

同理可知，
假设n = + T，T可以随意取，比如1，2，3…….
假设n = 11，这时候n =  + 3，也就是说T=3，所以要先剔除3个元素。
我们在剔除了3个元素之后（分别是2,4,6），此时我们定格在2T+1（7）处，并且将2T+1（7）作为新的一号，而且这时候的约瑟夫环只剩下，也就是F( + 3) = 2*3 + 1 = 7，答案为7
总结一下这个规律：
F( +T) = 2T+1。

<2>当q≠2时，

        递归公式：F(n+1) = ( F(n) + q ) / (n+1)      即     F(n+1)=

0 1 2 3 4 5 ......  n-1       总共n人
设第q个人也就是下标为q-1的人被淘汰：
剩下n-1个人，如下：
分为两段（就是除去q-1这位兄台的剩余n-1人）：
一段是：0  1  2   ......  q-2
另一段是：q q+1 q+2 ...... n-2  n-1 
这时，又来重复我们的老套路：将被淘汰的后一个人作为新的0号，于是新的如下：
0  1  2   ......     ..........     ........  n-2
从q开始，到最大数n-1，每个数都减去q,q之前的为负数，值为-1的就是最后一个数

粘贴一个队列题解：

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