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 ;    
}