問題描述
Josephus問題是一個非常古老的問題，它的范型描述為N個人（0到N-1）圍成一圈報數，報道M的人會被剔除，直到最后一個人，
要求找出最后一個人的位置或這N個人被剔除的順序，
解決思路
我們可以用一個佇列來表示N個人，然后回圈出隊，注意，此時的出隊只是一種“偽出隊”，只有輪到M位的數才真正出隊，其他偽出隊的數在隊尾重新入隊，以此來模擬問題的剔除方式，每次真出隊的陣列成的序列就是出隊順序，序列的最后一個數為最后一個人的位置，
具體代碼
#include<iostream>
#include<queue>
using namespace std;
int main() {
unsigned N, M;
cin >> N >> M;
queue<unsigned> all_of_people;
for (unsigned i = 0; i < N; ++i) {
all_of_people.push(i);
}
while (!all_of_people.empty()) {
for (unsigned i = 0; i < M - 1; ++i) {
all_of_people.push(all_of_people.front());
all_of_people.pop();
}
cout << all_of_people.front() << ' ';
all_of_people.pop();
}
return 0;
}
復雜度分析
因為是模擬剔除方式，每M次操作剔除一個元素，所以時間復雜度為M*N，所以元素只存在一個佇列里，空間復雜度為O(N)，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/281148.html
標籤：其他
上一篇：線索二叉樹的原理及創建