# 約瑟夫問題
方法1.用list模擬
可能會TLE
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
int N,M;
cin >> N >> M;
list<int> l;
for(int i=0;i<N;i++){
l.push_back(i); //放入編號0~N-1
}
list<int>::iterator it=l.begin();
while(N>1){ //直到剩下1人
N--;
int cnt=1;
while(cnt<M){ //找到加一個要刪除的點
cnt++;
it++;
if(it==l.end()) it=l.begin();
}
auto erase=it;
it++;
if(it==l.end()) it=l.begin();
l.erase(erase); //刪除
}
cout << *it << endl;
return 0;
}
```
方法2.公式解
如果當N=N的時候,第一個人被殺掉後,由剩下N-1個人重新圍成一個圈,而重新編號殺掉後的第一個人為0
![](https://i.imgur.com/0VO1Yaz.png)
(N=6,M=3)
由上圖可知,因為每次重新編號都向前移了M格,所以當想要知道N=N的時候可由N=N-1的答案再加上向前移動的M格,但這一個是圓環,加上M格後的答案有可能超出N,所以要mod N讓他重頭繼續跑
`f(N)=(f(N-1)+M)%N;`
當N=1時就是存活者,編號為0,可由此上圖回推N=2時的倖存者編號,回推至N=3,4,5...N的倖存者編號,就是上一個加上M在mod N,由此可寫成一個遞迴式
```cpp=
int josephus(int N,int M){
if(N==1) return 0;
return (josephus(N-1,M)+M)%N;
}
```
這題就難在要懂得她遞迴是如何運作的,以及如何回推到題目要的N,這題要注意編號從0開始,因為mod N剛好是0 ~ N-1,如果從1開始mod出來的數還會是0 ~ N-1,這樣編號就會錯亂,如果題目要求編號從1開始,把最後的答案+1就好了
遞迴寫法
```cpp=
int josephus(int N,int M){
if(N==1) return 0;
return (josephus(N-1,M)+M)%N;
}
int main(){
int N,M;
cin >> N >> M ;
cout << josephus(N,M);
return 0;
}
```
迴圈寫法
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
int N,M;
cin >> N >> M ;
int cache=0;
for(int i=2;i<=N;i++){
cache=(cache+M)%i;
}
cout << cache;
return 0;
}
```
延伸:如果題目問你爆炸K次後的第一個人編號為多少
當N=6,K=3時, 最後剩3人
![](https://i.imgur.com/EFC2Tp3.png)
N=3的編號0剛好就是第3次爆炸後的第一個人,所以可由此回推3次到N=6
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
int N,M,K;
cin >> N >> M >> K;
int ans=0;
for(int i=N-K+1;i<=N;i++){
ans=(ans+M)%i;
}
cout << ans+1;
return 0;
}
```