[已解决]约瑟夫环

yangzhixiaohuli

编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始以6作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，再从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。

输入格式:
首先输入一个整数T，表示测试数据的组数，然后是T组测试数据。每组测试数据第一行输入n，第二行输入n个不超过20的正整数，依次表示这n个人所持有的密码。

输出格式:
对于每组测试，按照出列的顺序输出各人的编号。每两个编号之间留一个空格。

输入样例:
2
7
3 1 7 2 4 8 4
15
3 4 8 10 6 5 5 1 2 12 13 4 2 3 7
输出样例:
6 1 4 7 2 3 5
6 11 10 9 13 15 8 12 3 5 7 14 4 2 1

这题用C++怎么做

最佳答案

月排行榜 / 总排行榜

FishC

2024-10-18 18:07:01

下面是一个用C++实现约瑟夫环问题的代码示例。通过模拟出列的过程，根据每个人的密码更新报数上限值 `m`。请确保您对输入和输出的格式要求已正确理解：

#include <iostream>
#include <vector>

int main() {
    int T;
    std::cin >> T; // 输入测试数据的组数
    while (T--) {
        int n;
        std::cin >> n; // 每组的人的数量
        std::vector<int> passwords(n);
        // 输入持有的密码
        for (int i = 0; i < n; ++i) {
            std::cin >> passwords[i];
        }

        std::vector<int> order; // 用于存放出列的顺序
        int m = 6; // 初始报数上限值
        int currentIndex = 0; // 从第一个人开始报数

        while (!passwords.empty()) {
            // 计算出当前需要出列的人
            currentIndex = (currentIndex + m - 1) % passwords.size();
            
            // 将该人编号添加到出列顺序中
            order.push_back(currentIndex + 1); // 加1是因为编号从1开始

            // 更新m为当前出列人的密码值
            m = passwords[currentIndex];

            // 删除该人（出列）
            passwords.erase(passwords.begin() + currentIndex);
        }

        // 输出结果
        for (size_t i = 0; i < order.size(); ++i) {
            std::cout << order[i];
            if (i < order.size() - 1) {
                std::cout << " ";
            }
        }
        std::cout << std::endl;
    }
    return 0;
}

### 代码说明：
1. **输入处理**：
   - 首先读取测试数据的组数 `T`。
   - 对于每组测试数据，先读取人数 `n`，然后依次读取每个人的密码。

2. **逻辑处理**：
   - 设置初始报数上限 `m = 6`。
   - 使用 `currentIndex` 指示当前报数开始的位置。
   - 使用一个循环不断模拟出列过程，直到所有人都出列。
   - `currentIndex = (currentIndex + m - 1) % passwords.size();` 用来确定当报数到 `m` 时的应出列人。

3. **输出处理**：
   - 记录出列的顺序并输出，保证每组输出结果编号之间有一个空格。

这段代码较简洁地模拟了约瑟夫环过程，满足了题目要求的功能和格式。请记得提供正确地输入数据进行测试。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

跳转到最佳答案楼层

FishC

下面是一个用C++实现约瑟夫环问题的代码示例。通过模拟出列的过程，根据每个人的密码更新报数上限值 `m`。请确保您对输入和输出的格式要求已正确理解：

#include <iostream>
#include <vector>

int main() {
    int T;
    std::cin >> T; // 输入测试数据的组数
    while (T--) {
        int n;
        std::cin >> n; // 每组的人的数量
        std::vector<int> passwords(n);
        // 输入持有的密码
        for (int i = 0; i < n; ++i) {
            std::cin >> passwords[i];
        }

        std::vector<int> order; // 用于存放出列的顺序
        int m = 6; // 初始报数上限值
        int currentIndex = 0; // 从第一个人开始报数

        while (!passwords.empty()) {
            // 计算出当前需要出列的人
            currentIndex = (currentIndex + m - 1) % passwords.size();
            
            // 将该人编号添加到出列顺序中
            order.push_back(currentIndex + 1); // 加1是因为编号从1开始

            // 更新m为当前出列人的密码值
            m = passwords[currentIndex];

            // 删除该人（出列）
            passwords.erase(passwords.begin() + currentIndex);
        }

        // 输出结果
        for (size_t i = 0; i < order.size(); ++i) {
            std::cout << order[i];
            if (i < order.size() - 1) {
                std::cout << " ";
            }
        }
        std::cout << std::endl;
    }
    return 0;
}

### 代码说明：
1. **输入处理**：
   - 首先读取测试数据的组数 `T`。
   - 对于每组测试数据，先读取人数 `n`，然后依次读取每个人的密码。

2. **逻辑处理**：
   - 设置初始报数上限 `m = 6`。
   - 使用 `currentIndex` 指示当前报数开始的位置。
   - 使用一个循环不断模拟出列过程，直到所有人都出列。
   - `currentIndex = (currentIndex + m - 1) % passwords.size();` 用来确定当报数到 `m` 时的应出列人。

3. **输出处理**：
   - 记录出列的顺序并输出，保证每组输出结果编号之间有一个空格。

这段代码较简洁地模拟了约瑟夫环过程，满足了题目要求的功能和格式。请记得提供正确地输入数据进行测试。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。