c➕➕使用类完成josephus问题
时间: 2024-03-09 08:49:59 浏览: 19
好的,下面是使用C++实现Josephus问题的类代码:
```c++
#include <iostream>
#include <vector>
class Josephus {
private:
int n; // 总人数
int m; // 报数到m的人出圈
std::vector<bool> alive; // 存储每个人是否还活着
int current; // 当前正在报数的人的索引
public:
Josephus(int n, int m) : n(n), m(m), alive(n, true), current(-1) {}
void next_alive() {
int count = 0;
while (count < m) {
current = (current + 1) % n;
if (alive[current]) {
count++;
}
}
}
void run() {
for (int i = 0; i < n - 1; i++) {
next_alive();
alive[current] = false;
std::cout << "第" << current + 1 << "个人出圈了" << std::endl;
}
std::cout << "最后剩下的人是第" << alive.find(true) + 1 << "个人" << std::endl;
}
};
int main() {
int n = 10;
int m = 3;
Josephus j(n, m);
j.run();
return 0;
}
```
在这个类中,我们使用了向量(vector)容器来存储每个人是否还活着。在初始化函数中,我们创建了一个长度为n的向量,每个元素初始值为true,表示所有人都还活着。我们还创建了一个current变量,表示当前正在报数的人的索引。初始时,current为-1,表示还没有开始报数。
在next_alive函数中,我们使用一个循环来进行报数。在循环中,我们先将current加1,然后对n取模,以便在到达列表末尾时能够回到开头。如果当前这个人还活着,我们就将计数器count加1。当计数器count等于m时,表示报到了m,当前这个人就要出圈了。
在run函数中,我们首先使用一个循环来让n-1个人出圈。在循环中,我们先调用next_alive函数找到要出圈的人,然后将其在alive向量中标记为false,表示他已经死亡。最后,我们输出一条消息,告诉用户第几个人出圈了。
最后,我们输出一条消息,告诉用户最后剩下的人的编号是多少。我们使用了alive.find(true)函数来查找向量中第一个为true的元素的索引,并将其加1即为最后剩下的人的编号。
现在我们可以创建一个Josephus对象,然后调用它的run方法来运行程序:
```c++
int n = 10;
int m = 3;
Josephus j(n, m);
j.run();
```
这个程序的输出结果应该是:
```
第3个人出圈了
第6个人出圈了
第9个人出圈了
第2个人出圈了
第7个人出圈了
第1个人出圈了
第8个人出圈了
第5个人出圈了
第10个人出圈了
最后剩下的人是第4个人
```
希望这个代码可以帮助您理解如何使用C++类来完成Josephus问题。