# Josephus Problem

有n個人圍成一個圈，一個一個處決，最後剩下的一個人會被放走。
假設每m個人殺一次，請問誰會被放走?
例如有5個人，編號1~5，每隔2人殺一個，處決順序會是2、4、1、5，最後放走3
那給定n跟m，如何決定幾號可以存活?

**想法1**
可以想到每次處刑人都是一圈一圈的繞來決定要殺誰
本來n人，每走完一圈會剩下n-floor(n/m)人
將每個人重新從1編號到n-floor(n/m)
可以想像本來問題是$T(n,m)$，可以有以下關系
$T(n,m)=T(n-floor(n/m),m)$
至於怎麼幫每個人重新編號呢?
由於在每一圈最後一個被殺的人的下一位會是下一圈的1號
可以歸納出以下的關係，目前這一圈的位置為$pos$，下一圈為$Newpos$
$Newpos=pos-m*floor(n/m)$ ，由於$Newpos$一定要大於0，如果此結果不是正整數，那$Newpos=pos-m*floor(n/m)+n-floor(pos/m)$

其實不難理解，$m*floor(n/m)$就是這圈最後一個被殺的人的編號，只需要將這圈一開始的人重新編號就可以，一開始是1~n，將第$m*floor(n/m)$編號為0，本來$m*floor(n/m)+1$是新的1號，原本的$pos$會變成$pos+n-m*floor(n/m)$號
而把這圈該殺的人殺完後$pos$前面的人被殺了$floor(pos/m)$個
所以結果就是$Newpos=pos-m*floor(n/m)+n-floor(pos/m)$

值得注意的是如果n<m該怎麼處理?
n<m代表每次只會有一個人被殺(原本編號加上m後能被m整除的那個人)，然後再重新編號，比這個被殺的人編號大的人編號減一，比它小的人不用變化。

依照以下的code可以對每個編號做檢查，如果此編號的人最後一圈能活下來就完成此題目。
時間複雜度$O(nm)$

#include <iostream>
#include <string>
#include <cstring>

using namespace std;

#define SIZE 101

bool Joseph_Problem(int n,int m,int pos){
    if(pos%m==0)
        return false;
    if(n==1)
        return true;
    if(n<m){
        if((pos+n)%m==0)
            return false;
        else if(pos+n-m<0)
            return Joseph_Problem(n-1,m,pos);
        else
            return Joseph_Problem(n-1,m,pos+n-m);
    }
    
    int new_size=n-(n/m),new_pos;
    if(pos-(m*(n/m))>0)
        new_pos=pos-(m*(n/m));
    else
        new_pos=pos-(m*(n/m))+n-(pos/m);
    return Joseph_Problem(new_size,m,new_pos);
}


int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    bool Turn_off[SIZE],Done;

    int N,m,i,count;
    cin>>N>>m;
    for(int i=1;i<=N;i++){
        if(Joseph_Problem(N,m,i))
            cout<<i<<" Survive\n";
        else
            cout<<i<<" Killed\n";
    }
    return 0;
}

**想法2**
從上面的思考可以發現，這個問題就是先將整體的人找到正確的編號，再不斷轉換問題大小
所以問題大小n的時候可以思考為先殺一個人(編號m的人)變成n-1人再轉換所有人編號
轉的方式如下，假設原本n人的時候在位置i的人，轉換過後會是
$i=i-m$ if $i-m>0$
$i=i+(n-1)-m$ if $i-m<0$
而我們知道最後會活下來的人就是在1個人的時候編號1的那個人
透過上述可以得到以下遞迴式
$T(n,m)=(T(n-1,m)+(m-1))\%(n)+1$
**第j個位置的人往回推要先加(m-1)人，因為先前有一人被殺，所以少一個，之後mod n，得到的位置0的人其實是位置1的，所以再加1**

並且要從$T(1,m)=1$的人往回推
所以可以寫成以下的code
時間複雜度是$O(n)$

#include <iostream>
#include <string>
#include <cstring>

using namespace std;

#define SIZE 101

int Joseph_Problem(int n,int m){
    if(n==1)
        return 1;
    else
        return ((Joseph_Problem(n-1,m)+m-1)%n) + 1;
}


int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    bool Turn_off[SIZE],Done;

    int N,m,i,count;
    N=7,m=3;
    cout<<Joseph_Problem(N,m)<<endl;
    return 0;
}

**想法3**
有遞迴式，那就可以用dp解
建立一個大小n+1的array，使用1到n的位置，arrary[i]代表總人數i的時候的編號
時間複雜度和遞迴實作一樣是$O(n)$，但沒有遞迴的overhead，在實作上更優。
**初始值:** $Array[1]=1$
**遞迴式:** $Arrary[i]=(Array[i-1]+m-1)\%i + 1$
**解答:** $Array[n]$
**code:**

#include <iostream>
#include <string>
#include <cstring>

using namespace std;

#define SIZE 101

int Joseph_Problem_DP(const int n,int& m){
    int Pos[n+1];
    Pos[1]=1;
    for(int i=2;i<=n;i++)
        Pos[i]=(Pos[i-1]+(m-1))%i + 1;

    return Pos[n];
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    bool Turn_off[SIZE],Done;

    int N,m,i,count;
    N=7,m=3;
    cout<<Joseph_Problem_DP(N,m)<<endl;
    return 0;
}