And Then There Was One （约瑟夫环（裸0.0））

题目来源：https://vjudge.net/problem/POJ-3517

【题意】

简单的约瑟夫环模板。

从数字m开始，往后数k个数字，删除，直到剩下一个数字，输出。

【思路】

用vector容器装下1~n所有数，每循环一次便删去一个，直到容器内只剩一个元素，输出。

为什么要让k-1呢？因为你想啊，当把一个数字从vector删掉以后，比如第一次删去的是数字3，并且数字下标是3，删去之后，下标3依旧存在，只不过数字变成了4，往后推了一位，所以，k要减一，因为已经移动一位了。

至于vi=(pre+k-1)%n+1;为什么这样写，因为这样可以保证vi可以等于n，比如，pre+k==7，且n==7，而我现在要的vi也是7，所以只好先减去1，取余后再加上一就可以了。

然后。。。就没然后了。。。

好吧，又发现另外一种很简洁的数学推导公式，O（n）的时间复杂度。

原序列是这样的：（假设总共有8个数，每次跳5个人）

序号：1 2 3 4 5 6 7 8

数字：1 2 3 4 5 6 7 8

经过第一次删除：（并且重新从1开始报数）（删去了5）

序号：4 5 6 7 1 2 3

数字：1 2 3 4 6 7 8

整理得：

序号：1 2 3 4 5 6 7

数字：6 7 8 1 2 3 4

然后重复上面的操作，删去第五个数。。并整理得：

序号：1 2 3 4 5 6

数字：3 4 6 7 8 1

就这样，直到最后只剩一个数：

用函数表示： F（1）=0；这里的0是最后一个数的编号。

当有2个人的时候（N=2），报道（M-1）的人自杀，最后自杀的人是谁？应该是在只有一个人时，报数时得到的最后自杀的序号加上M，因为报到M-1的人已经自杀，只剩下2个人，另一个自杀者就是最后自杀者，用函数表示：

F(2)=F(1)+M

可以得到递推公式：

F(i)=F(i-1)+M

因为可能会超出总人数范围，所以要求模

F(i)=(F(i-1)+M)%i

参考博客：http://blog.csdn.net/kangroger/article/details/39254619#comments

【代码1】

#include<set>
#include<map>
#include<stack>
#include<cmath>
#include<queue>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<limits.h>
#include<algorithm>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int mod=+;
typedef unsigned long long ll;
typedef long long LL;
vector<int> v;
int main()
{
    int n,k,m;
    while(~scanf("%d%d%d",&n,&k,&m))
    {
        v.clear();
        if(!n&&!k&&!m)
            break;
        for(int i=; i<=n; i++)
            v.push_back(i);
        v.erase(v.begin()+m);
        int pre=m,vi;
        k--;
        n--;
        while(n!=)
        {
            vi=(pre+k-)%n+;
            v.erase(v.begin()+vi);
            pre=vi;
            n--;
        }
        printf("%d\n",v[]);
    }
}
           

【代码2】

#include <stdio.h>    
#include <string.h>    
int n, k, m;    
int main() {    
    while (~scanf("%d%d%d", &n, &k, &m) && n + k + m) {    
        int ans = ;    
        for (int i = ; i <= n - ; i++)    
            ans = (ans + k) % i;    
        printf("%d\n", (ans + m) % n + );    
    }    
    return ;    
}