用c++完成以下问题。问题描述 : 设计并实现一个解决约瑟夫环问题的类Joseph。当需要解决一个n个人间隔为m的约瑟夫环问题,可以构建一个对象Joseph obj(n, m),然后调用obj.simulate()输出模拟删除过程。 【输入形式】 输入为三个正整数n和m和k,空格分隔,分别代表编号长度和间隔长度和起始位置,编号长度n<=50。 【输出形式】 输出为n个整数,空格分隔。
时间: 2024-03-18 21:38:28 浏览: 94
用vector解决约瑟夫环.txt
好的,以下是C++的实现:
```c++
#include <iostream>
#include <vector>
using namespace std;
class Joseph {
private:
int n, m;
vector<int> lst;
public:
Joseph(int n, int m) {
this->n = n;
this->m = m;
for (int i = 1; i <= n; i++) {
lst.push_back(i);
}
}
vector<int> simulate(int k) {
k -= 1;
int i = k;
vector<int> res;
while (lst.size() > 1) {
i = (i + m - 1) % lst.size();
res.push_back(lst[i]);
lst.erase(lst.begin() + i);
}
res.push_back(lst[0]);
return res;
}
};
int main() {
int n, m, k;
cin >> n >> m >> k;
Joseph obj(n, m);
vector<int> res = obj.simulate(k);
for (int i = 0; i < res.size(); i++) {
cout << res[i] << " ";
}
return 0;
}
```
在这个类中,我们使用了一个向量(vector)来存储所有参与游戏的人的编号。simulate(k)方法模拟了约瑟夫环的过程,其中k是起始位置。在每一轮中,我们用公式(i + m - 1) % lst.size()来计算要删除的人的索引。每次删除一个人后,我们将其编号添加到结果向量(res)中。最后,向量(lst)中仅剩一个元素,即为胜利者。最后,将结果向量(res)输出即可。
阅读全文