[已解决]约瑟夫环

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`。请确保您对输入和输出的格式要求已正确理解：

1. #include <iostream>
   
2. #include <vector>
   
3. 
   
4. int main() {
   
5.     int T;
   
6.     std::cin >> T; // 输入测试数据的组数
   
7.     while (T--) {
   
8.         int n;
   
9.         std::cin >> n; // 每组的人的数量
   
10.         std::vector<int> passwords(n);
    
11.         // 输入持有的密码
    
12.         for (int i = 0; i < n; ++i) {
    
13.             std::cin >> passwords[i];
    
14.         }
    
15. 
    
16.         std::vector<int> order; // 用于存放出列的顺序
    
17.         int m = 6; // 初始报数上限值
    
18.         int currentIndex = 0; // 从第一个人开始报数
    
19. 
    
20.         while (!passwords.empty()) {
    
21.             // 计算出当前需要出列的人
    
22.             currentIndex = (currentIndex + m - 1) % passwords.size();
    
23.             
    
24.             // 将该人编号添加到出列顺序中
    
25.             order.push_back(currentIndex + 1); // 加1是因为编号从1开始
    
26. 
    
27.             // 更新m为当前出列人的密码值
    
28.             m = passwords[currentIndex];
    
29. 
    
30.             // 删除该人（出列）
    
31.             passwords.erase(passwords.begin() + currentIndex);
    
32.         }
    
33. 
    
34.         // 输出结果
    
35.         for (size_t i = 0; i < order.size(); ++i) {
    
36.             std::cout << order[i];
    
37.             if (i < order.size() - 1) {
    
38.                 std::cout << " ";
    
39.             }
    
40.         }
    
41.         std::cout << std::endl;
    
42.     }
    
43.     return 0;
    
44. }

复制代码

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

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

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

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

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

跳转到最佳答案楼层

FishC

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

1. #include <iostream>
   
2. #include <vector>
   
3. 
   
4. int main() {
   
5.     int T;
   
6.     std::cin >> T; // 输入测试数据的组数
   
7.     while (T--) {
   
8.         int n;
   
9.         std::cin >> n; // 每组的人的数量
   
10.         std::vector<int> passwords(n);
    
11.         // 输入持有的密码
    
12.         for (int i = 0; i < n; ++i) {
    
13.             std::cin >> passwords[i];
    
14.         }
    
15. 
    
16.         std::vector<int> order; // 用于存放出列的顺序
    
17.         int m = 6; // 初始报数上限值
    
18.         int currentIndex = 0; // 从第一个人开始报数
    
19. 
    
20.         while (!passwords.empty()) {
    
21.             // 计算出当前需要出列的人
    
22.             currentIndex = (currentIndex + m - 1) % passwords.size();
    
23.             
    
24.             // 将该人编号添加到出列顺序中
    
25.             order.push_back(currentIndex + 1); // 加1是因为编号从1开始
    
26. 
    
27.             // 更新m为当前出列人的密码值
    
28.             m = passwords[currentIndex];
    
29. 
    
30.             // 删除该人（出列）
    
31.             passwords.erase(passwords.begin() + currentIndex);
    
32.         }
    
33. 
    
34.         // 输出结果
    
35.         for (size_t i = 0; i < order.size(); ++i) {
    
36.             std::cout << order[i];
    
37.             if (i < order.size() - 1) {
    
38.                 std::cout << " ";
    
39.             }
    
40.         }
    
41.         std::cout << std::endl;
    
42.     }
    
43.     return 0;
    
44. }

复制代码

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

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

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

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

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