C++排队报数约瑟夫问题改版经典案例

题目描述

有n个人排成一圈，从1到n编号。从第一个人开始依次报数（第一个人报的数是1，下一个人报的数是2（当前这个人报的数字等于前面那个人报的数字加一），报数一共进行 n轮，对于第 i(1≤i≤n)轮，数到i的平方的人出列，下一个人继续从1开始报数。结束的时候所有人都会出列。请依次输出每一轮出列的人的编号。

案例代码

#include <iostream>
#include <vector>

using namespace std;

void josephus(int n) {
    vector<bool> isOut(n + 1, false);

    int current = 0;
    for (int i = 1; i <= n; ++i) {
        int count = 0;
        while (count < i) {
            current = (current + 1) % n;
            if (current == 0) current = n;
            if (!isOut[current]) {
                ++count;
            }
        }
        isOut[current] = true;
        cout << current << " ";
    }
    cout << endl;
}

int main() {
    int n;
    cout << "请输入总人数 n：";
    cin >> n;

    cout << "每一轮出列的人的编号依次为：" << endl;
    josephus(n);

    return 0;
}

这个程序中，josephus 函数模拟了约瑟夫环的过程。首先创建一个 vector<bool> 来表示每个人是否已经出列。然后使用循环依次进行每一轮报数并出列，直到所有人都出列为止。在 main 函数中，用户输入总人数，然后调用 josephus 函数进行模拟并输出结果。