c++用vector实现约瑟夫环
时间: 2023-10-12 16:16:24 浏览: 75
约瑟夫环是一个经典的数学问题,它的描述如下:N个人围成一圈,从第一个人开始报数,第M个人出圈,然后从出圈的下一个人开始重新报数,再从第M个人出圈,直到所有人都出圈为止。现在,我们来利用vector实现约瑟夫环的求解。
具体实现如下:
```c++
#include <iostream>
#include <vector>
using namespace std;
int josephus(vector<int>& v, int m) {
int i = 0;
while (v.size() > 1) {
i = (i + m - 1) % v.size();
cout << "出圈的人是:" << v[i] << endl;
v.erase(v.begin() + i);
}
return v[0];
}
int main() {
int n, m;
vector<int> v;
cout << "请输入总人数和出圈的数字:" << endl;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
v.push_back(i);
}
int winner = josephus(v, m);
cout << "胜利者是:" << winner << endl;
return 0;
}
```
在这里,我们使用了一个vector来存储所有的人,并且在每次出圈时,利用vector的erase函数来删除出圈的人。最终,当vector中只剩下一个人时,就是胜利者了。