PTA（顺序表）2-13 约瑟夫环

2-13 约瑟夫环

分数 9

作者 李廷元

单位 中国民用航空飞行学院

N个人围成一圈顺序编号，从1号开始按1、2、3……顺序报数，报p者退出圈外，其余的人再从1、2、3开始报数，报p的人再退出圈外，以此类推。
请按退出顺序输出每个退出人的原序号。

输入格式:

输入只有一行，包括一个整数N(1<=N<=3000)及一个整数p(1<=p<=5000)。

输出格式:

按退出顺序输出每个退出人的原序号，数据间以一个空格分隔，但行尾无空格。

输入样例:

在这里给出一组输入。例如：

1
7 3

输出样例:

1
3 6 2 7 5 1 4

我卡住的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
using namespace std;

// 定义顺序表结构
typedef struct {
    int *data;
    int length;
} sqList;

// 初始化顺序表
void initList(sqList &L, int N) {
    L.data = new int[N];
    L.length = 0;
    // 将所有数据先置为1
    for (int i = 0; i < N; ++i) {
        L.data[i] = 1;
        L.length++;
    }
}

int main() {
    int N, p;
    cin >> N >> p;
    sqList L;
    initList(L, N);

    int countPeople = 0; // 定义一个计数器，用于看是否所有人退出圈外
    int countNum = 0; // 报数计数器
    while (countPeople != N) {
        //这里
        countNum++;
        if (countNum == p) {

        }
    }
}

我的超时代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
using namespace std;

// 定义顺序表结构
typedef struct {
    int *data;
    int length;
} sqList;

// 初始化顺序表
void initList(sqList &L, int N) {
    L.data = new int[N];
    L.length = 0;
    // 将所有数据先置为1
    for (int i = 0; i < N; ++i) {
        L.data[i] = 1;
        L.length++;
    }
}

int main() {
    int N, p;
    cin >> N >> p;
    sqList L;
    initList(L, N);

    int countPeople = 0; // 已退出人数，用于看是否所有人退出圈外
    int countNum = 0; // 报数计数器
    int current = 0; // 当前报数的位置（下标）
    int firstOutput = 1; // 控制输出格式（是否为第一个输出）

    while (countPeople != N) {
        while (L.data[current] == 0) {
            // 不能只是current++
            current = (current + 1) % N; // 循环移动到下一个位置
        }
        // 报数
        countNum++;
        if (countNum == p) {
            // 当前报数的人退出，将当前current的位置记为0
            if (firstOutput) {
                cout << current + 1; // current是下标，要输出第几个
                firstOutput = 0;
            } else {
                cout << " " << current + 1;
            }
            L.data[current] = 0; // 标记为退出
            countPeople++;       // 退出人数+1
            countNum = 0;        // 重置报数计数器
        }
        // 移动到下一个位置
        current = (current + 1) % N;
    }
}

每次找 “下一个在圈中的人” 都要循环跳过已退出者，时间复杂度太高（O (N²)）

正确代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
using namespace std;

int main() {
    int N, p;
    cin >> N >> p;
    
    // 存储每个人的原始序号（1~N）
    int* people = new int[N];
    for (int i = 0; i < N; ++i) {
        people[i] = i + 1;
    }
    
    int count = 0;          // 已退出的人数
    int current = 0;        // 当前报数的位置索引
    int remaining = N;      // 剩余人数（关键优化：记录有效人数）
    int firstOutput = 1;    // 控制输出格式
    
    while (count < N) {
        // 计算下一个要退出的位置：当前位置 + (p-1) 步，对剩余人数取模
        current = (current + p - 1) % remaining;
        
        // 输出退出者的序号
        if (firstOutput) {
            cout << people[current];
            firstOutput = 0;
        } else {
            cout << " " << people[current];
        }
        
        // 将退出者移除（用后面的元素覆盖当前位置）
        for (int i = current; i < remaining - 1; ++i) {
            people[i] = people[i + 1];
        }
        
        count++;
        remaining--;  // 剩余人数减1
    }
    
    delete[] people;
    return 0;
}

逆天太妙了

这段代码是约瑟夫环问题的高效实现，核心思路是通过直接计算退出位置 + 动态调整数组来模拟 “报数 - 退出” 过程，避免了大量无效判断，时间效率很高。我们分步骤解析逻辑：

一、初始化：用数组存储所有人的序号

1
2
3
4
int* people = new int[N];
for (int i = 0; i < N; ++i) {
    people[i] = i + 1;  // 存储1~N的序号（比如N=7时，数组为[1,2,3,4,5,6,7]）
}
  • 数组people的作用：实时记录当前 “在圈中” 的人的原始序号（随着有人退出，数组会动态缩减有效长度）。
  • 变量定义：
    • count：已退出的人数（初始 0，最终达到 N 时结束）。
    • current：当前要退出的人的位置索引（在数组有效范围内）。
    • remaining：当前还在圈中的人数（初始 N，每退出 1 人减 1）。

二、核心循环：每轮处理 1 个退出者，共执行 N 轮

循环条件count < N：直到所有人都退出为止。

步骤 1：计算 “下一个要退出的位置”

1
current = (current + p - 1) % remaining;

这是最关键的一步，用数学计算直接定位退出者，避免逐个报数：

  • 原理：从当前位置开始，数p个有效人（在圈中），第p个人就是退出者。
  • 举例：假设当前remaining=5（还剩 5 人），p=3，current=0：
    • 计算：(0 + 3 - 1) % 5 = 2 % 5 = 2 → 退出者是数组中索引为 2 的人。
    • 对应逻辑：从当前位置（0）开始数 3 个有效人，分别是 0→1→2，第 3 个就是索引 2。
  • 取模% remaining的作用：适配 “环形” 逻辑，当p超过剩余人数时自动循环（比如p=10，remaining=5，等价于数10%5=0→实际数 5 个）。

步骤 2：输出退出者的序号

1
2
3
4
5
6
if (firstOutput) {
    cout << people[current];  // 第一个输出不加空格
    firstOutput = 0;
} else {
    cout << " " << people[current];  // 后续输出前加空格（保证行尾无空格）
}
  • 直接输出数组中current索引对应的序号（因为数组只保留 “在圈中” 的人，所以索引直接对应有效位置）。

步骤 3：移除退出者，调整数组作用：将退出者从 “有效圈” 中移除，后续报数不再考虑他。

  • 举例：原数组

    1
    [1,2,3,4,5]

    ，退出者是索引 2（值 3）：

    • 循环后数组变为[1,2,4,5,5]（最后一个元素无效，但remaining会减 1，后续不再访问）。
    • 实际有效部分是前remaining-1个元素（即[1,2,4,5]）。

步骤 4：更新计数，准备下一轮

1
2
count++;       // 已退出人数+1
remaining--;   // 剩余人数-1（有效数组长度减1）

三、举例验证（输入 N=7, p=3）

模拟过程：

  1. 初始数组：[1,2,3,4,5,6,7]，remaining=7，current=0
  2. 第 1 轮：
    • current=(0+3-1)%7=2 → 输出people[2]=3
    • 移除后数组有效部分：[1,2,4,5,6,7]，remaining=6
  3. 第 2 轮：
    • current=(2+3-1)%6=4%6=4 → 输出people[4]=6
    • 移除后数组有效部分：[1,2,4,5,7]，remaining=5
  4. 后续轮次以此类推，最终输出3 6 2 7 5 1 4，与示例一致。

核心优势

  • 高效性：通过数学计算直接定位退出位置，避免逐个检查 “是否在圈中”，时间复杂度 O (N²)（主要是移除元素时的数组移动），但实际执行效率远高于顺序表标记法。
  • 直观性：数组始终存储当前 “在圈中” 的人，索引直接对应位置，无需处理无效标记（如 0）。