[已解决]约瑟夫环

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++实现该问题的简单示例代码：

1. #include <iostream>
   
2. #include <vector>
   
3. 
   
4. void solveJosephus(int n, const std::vector<int>& passwords) {
   
5.     std::vector<int> people(n);
   
6.     for (int i = 0; i < n; ++i) {
   
7.         people[i] = i + 1; // 初始化人的编号
   
8.     }
   
9. 
   
10.     int currentIndex = 0;
    
11.     int currentM = 6; // 初始的报数上限值
    
12.    
    
13.     while (!people.empty()) {
    
14.         currentIndex = (currentIndex + currentM - 1) % people.size();
    
15.         std::cout << people[currentIndex] << " "; // 输出出列人的编号
    
16.         currentM = passwords[people[currentIndex] - 1]; // 更新报数上限
    
17.         people.erase(people.begin() + currentIndex); // 移除已出列的人
    
18.     }
    
19.     std::cout << std::endl;
    
20. }
    
21. 
    
22. int main() {
    
23.     int T;
    
24.     std::cin >> T; // 输入测试数据组数
    
25. 
    
26.     while (T--) {
    
27.         int n;
    
28.         std::cin >> n; // 输入每组数据的人数
    
29.         std::vector<int> passwords(n);
    
30. 
    
31.         for (int i = 0; i < n; ++i) {
    
32.             std::cin >> passwords[i]; // 输入每个人的密码
    
33.         }
    
34. 
    
35.         solveJosephus(n, passwords); // 解决约瑟夫环问题
    
36.     }
    
37. 
    
38.     return 0;
    
39. }

复制代码

### 代码解释

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

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

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

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

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

跳转到最佳答案楼层

FishC

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

1. #include <iostream>
   
2. #include <vector>
   
3. 
   
4. void solveJosephus(int n, const std::vector<int>& passwords) {
   
5.     std::vector<int> people(n);
   
6.     for (int i = 0; i < n; ++i) {
   
7.         people[i] = i + 1; // 初始化人的编号
   
8.     }
   
9. 
   
10.     int currentIndex = 0;
    
11.     int currentM = 6; // 初始的报数上限值
    
12.    
    
13.     while (!people.empty()) {
    
14.         currentIndex = (currentIndex + currentM - 1) % people.size();
    
15.         std::cout << people[currentIndex] << " "; // 输出出列人的编号
    
16.         currentM = passwords[people[currentIndex] - 1]; // 更新报数上限
    
17.         people.erase(people.begin() + currentIndex); // 移除已出列的人
    
18.     }
    
19.     std::cout << std::endl;
    
20. }
    
21. 
    
22. int main() {
    
23.     int T;
    
24.     std::cin >> T; // 输入测试数据组数
    
25. 
    
26.     while (T--) {
    
27.         int n;
    
28.         std::cin >> n; // 输入每组数据的人数
    
29.         std::vector<int> passwords(n);
    
30. 
    
31.         for (int i = 0; i < n; ++i) {
    
32.             std::cin >> passwords[i]; // 输入每个人的密码
    
33.         }
    
34. 
    
35.         solveJosephus(n, passwords); // 解决约瑟夫环问题
    
36.     }
    
37. 
    
38.     return 0;
    
39. }

复制代码

### 代码解释

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

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

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

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

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