问题描述
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)。
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
