c➕➕面向对象解决josephus问题
时间: 2023-10-05 21:11:28 浏览: 45
Josephus问题是一个经典的数学问题,有多种解法。下面是一个使用C++面向对象的解法:
```cpp
#include <iostream>
#include <vector>
class Josephus {
public:
Josephus(int n, int k) : n_(n), k_(k) {}
int solve() {
std::vector<int> people(n_);
for (int i = 0; i < n_; ++i) {
people[i] = i + 1;
}
int index = 0;
while (people.size() > 1) {
index = (index + k_ - 1) % people.size();
people.erase(people.begin() + index);
}
return people[0];
}
private:
int n_;
int k_;
};
int main() {
int n, k;
std::cout << "Enter the number of people (n): ";
std::cin >> n;
std::cout << "Enter the step size (k): ";
std::cin >> k;
Josephus j(n, k);
int survivor = j.solve();
std::cout << "The survivor is person " << survivor << std::endl;
return 0;
}
```
在这个解法中,我们定义了一个`Josephus`类,它有两个私有成员变量`n_`和`k_`,分别表示人数和步长。`solve`方法是解决Josephus问题的核心算法,它首先创建一个人数为`n_`的向量`people`,然后在每一轮中找到要删除的人的索引,然后将其从向量中删除,直到只剩下最后一个人。
在`main`函数中,我们首先从标准输入读取人数和步长,然后创建一个`Josephus`对象并调用其`solve`方法,最后输出幸存者的编号。