C++语言用顺序表实现约瑟夫环,N个人围成一圈,从第一个开始报数,第M个将被杀掉,最后剩下一个,其余人都将被杀掉。例如N=6,M=5,被杀掉的顺序是:5,4,6,2,3。编程输出每次被杀掉的人的序号和最后的幸存者。
时间: 2024-09-13 17:18:50 浏览: 34
VC++编写的顺序表实现约瑟夫环
5星 · 资源好评率100%
在C++中,可以使用顺序表(也称为数组或vector)来实现约瑟夫环的问题。首先,我们需要创建一个动态大小的数组来存储人的编号,并初始化为1到N。然后按照规则依次遍历数组,每当遇到M的倍数时,就删除该位置的人并调整后续元素的位置。
以下是一个简单的示例代码:
```cpp
#include <iostream>
#include <vector>
std::vector<int> josephusRing(int N, int M) {
std::vector<int> survivors(N + 1, 0);
for (int i = 1; i <= N; ++i) {
survivors[i] = i;
}
int current = 1;
while (survivors.size() > 1) {
if (current % M == 0) { // 如果当前是M的倍数,删除该人
survivors.erase(survivors.begin() + current);
} else {
current++; // 否则继续计数
}
}
// 输出最后剩余的那个人
std::cout << "幸存者: " << survivors.front() << std::endl;
return survivors;
}
int main() {
int N = 6;
int M = 5;
josephusRing(N, M);
//
阅读全文