用C++求解约瑟夫环问题 编号为1,2,3,…,n的n个人围坐一圈,任选一个正整数m作为报数上限值,从第一个人开始按顺时针方向报数,报数到m时停止,报数为m的人出列。从出列人的顺时针方向的下一个人开始又从1重新报数,如此下去,直到所有人都全部出列为止。编写语言尽量简单
时间: 2023-10-21 11:03:41 浏览: 94
好的,这是一个经典的约瑟夫环问题,以下是用 C++ 编写的解决方案:
```c++
#include <iostream>
#include <vector>
using namespace std;
int josephus(int n, int m) {
vector<int> vec(n);
int i = 0, j = 0, k = -1;
while (i < n) {
k++;
if (k == n)
k = 0;
if (vec[k] == -1)
continue;
j++;
if (j == m) {
vec[k] = -1;
i++;
j = 0;
}
}
return k;
}
int main() {
int n, m;
cout << "请输入人数 n 和报数上限值 m:";
cin >> n >> m;
int ans = josephus(n, m);
cout << "最后留下的人的编号为:" << ans + 1 << endl;
return 0;
}
```
程序主要分为两个部分,第一个部分是求解约瑟夫环问题的函数 `josephus`,第二个部分是主函数 `main`。
函数 `josephus` 中,我们使用了一个 vector 来表示每个人是否还在圈中,-1 表示已经出圈。使用三个变量 i、j、k 分别表示已经出圈的人数、当前报数的人的索引、当前在圈中的人的索引。每次循环时,k 自增表示轮到下一个人报数,如果这个人已经出圈了,则跳过;否则 j 自增表示这个人报了数,如果 j 等于 m,说明这个人需要出圈,将其标记为 -1 并且 i 自增表示已经出圈的人数加一,j 重置为 0。直到 i 等于 n,也就是所有人都出圈了,此时 k 就是最后留下的人的索引。
主函数 `main` 中,我们从标准输入读入人数 n 和报数上限值 m,然后调用函数 `josephus` 求解,最后输出最后留下的人的编号即可。
希望这个代码能够对你有所帮助!
阅读全文