C++ 循环数组模拟约瑟夫环问题：无需 Vector 的解决方案

您想了解如何使用 C++ 中的循环数组解决约瑟夫环问题吗？您来对地方了！本文将提供一个不使用 vector 的解决方案，并附带详细的代码解释。

问题描述

约瑟夫环问题是一个经典的算法问题，描述如下：

n 个人围成一圈，从第 k 个人开始报数，数到 m 的人出列，然后从出列的下一个人重新开始报数，数到 m 的人再次出列，以此类推，直到所有人出列为止。要求输出最后剩下的人的编号。

解决方案

以下是不使用 vector 的 C++ 代码实现：cpp#include

using namespace std;

int main(){ int n = 0, k = 0, m = 0; cin >> n >> k >> m;

int circle[100]; // 使用固定大小的数组    for (int i = 0; i < n; i++) {        circle[i] = i;    }

int idx = k - 1;    while (n > 1) {        int count = 0;        while (count < m) {            if (circle[idx] >= 0) {                count++;            }            idx = (idx + 1) % n;        }        circle[(idx - 1 + n) % n] = -1; // 标记出局者        n--; // 剩余人数减少    }

for (int i = 0; i < n; i++) {        if (circle[i] >= 0) {            cout << circle[i] << endl;            break;        }    }

return 0;}

代码解释:

我们使用一个大小为 100 的 circle 数组来存储人员信息，并初始化数组元素为其索引值，代表每个人的初始编号。2. idx 变量用于跟踪当前报数的人的位置。3. 外层 while 循环模拟整个游戏过程，直到只剩下一个人。4. 内层 while 循环模拟报数过程，找到下一个要出局的人。5. 我们使用 -1 标记已经出局的人，并在每次循环迭代后减少剩余人数 n。6. 最后，我们遍历 circle 数组，找到唯一一个未被标记为 -1 的元素，即为最后剩下的人的编号。

总结

本文介绍了如何使用 C++ 中的循环数组解决约瑟夫环问题。通过使用固定大小的数组，我们可以避免使用 vector，从而提供一个更简洁的解决方案。

希望这篇文章对您有所帮助！如果您有任何问题，请随时在下方留言。