[已解决]约瑟夫环

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:10:45

要解决这个问题，我们可以使用一个循环来模拟约瑟夫环的过程。以下是一个使用C++实现该问题的简单示例代码：

#include <iostream>
#include <vector>

void solveJosephus(int n, const std::vector<int>& passwords) {
    std::vector<int> people(n);
    for (int i = 0; i < n; ++i) {
        people[i] = i + 1; // 初始化人的编号
    }

    int currentIndex = 0;
    int currentM = 6; // 初始的报数上限值
    
    while (!people.empty()) {
        currentIndex = (currentIndex + currentM - 1) % people.size();
        std::cout << people[currentIndex] << " "; // 输出出列人的编号
        currentM = passwords[people[currentIndex] - 1]; // 更新报数上限
        people.erase(people.begin() + currentIndex); // 移除已出列的人
    }
    std::cout << std::endl;
}

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]; // 输入每个人的密码
        }

        solveJosephus(n, passwords); // 解决约瑟夫环问题
    }

    return 0;
}

### 代码解释

1. **数据输入与初始化**：首先，我们输入测试数据的组数T。对于每一组测试数据，我们输入人数n和每个人的密码，并初始化人员编号从1到n存储在一个向量`people`中。

2. **模拟过程**：
    - 从`currentIndex`开始报数，找到第`currentM`个出列的人的位置。
    - 输出该人的编号后，更新currentM为该人对应的密码。
    - 从人员向量中删除该出列者，并继续从该位置顺时针方向（即下一个位置）开始新的报数循环。

3. **循环结束**：当所有人都出列时，向量为空，结束循环。

这个程序能够按要求输出人员出列的顺序，并且灵活处理不同的测试用例。

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

跳转到最佳答案楼层

FishC

要解决这个问题，我们可以使用一个循环来模拟约瑟夫环的过程。以下是一个使用C++实现该问题的简单示例代码：

#include <iostream>
#include <vector>

void solveJosephus(int n, const std::vector<int>& passwords) {
    std::vector<int> people(n);
    for (int i = 0; i < n; ++i) {
        people[i] = i + 1; // 初始化人的编号
    }

    int currentIndex = 0;
    int currentM = 6; // 初始的报数上限值
    
    while (!people.empty()) {
        currentIndex = (currentIndex + currentM - 1) % people.size();
        std::cout << people[currentIndex] << " "; // 输出出列人的编号
        currentM = passwords[people[currentIndex] - 1]; // 更新报数上限
        people.erase(people.begin() + currentIndex); // 移除已出列的人
    }
    std::cout << std::endl;
}

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]; // 输入每个人的密码
        }

        solveJosephus(n, passwords); // 解决约瑟夫环问题
    }

    return 0;
}

### 代码解释

1. **数据输入与初始化**：首先，我们输入测试数据的组数T。对于每一组测试数据，我们输入人数n和每个人的密码，并初始化人员编号从1到n存储在一个向量`people`中。

2. **模拟过程**：
    - 从`currentIndex`开始报数，找到第`currentM`个出列的人的位置。
    - 输出该人的编号后，更新currentM为该人对应的密码。
    - 从人员向量中删除该出列者，并继续从该位置顺时针方向（即下一个位置）开始新的报数循环。

3. **循环结束**：当所有人都出列时，向量为空，结束循环。

这个程序能够按要求输出人员出列的顺序，并且灵活处理不同的测试用例。

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