changed 4 years ago  
Published Linked with GitHub

約瑟夫問題

方法1.用list模擬
可能會TLE




























#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


(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,由此可寫成一個遞迴式





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就好了

遞迴寫法












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

迴圈寫法














#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人

N=3的編號0剛好就是第3次爆炸後的第一個人,所以可由此回推3次到N=6














#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;
}
Select a repo