PTA（链表）2-9 约瑟夫环

2-9 约瑟夫环

分数 8

作者 李廷元

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

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

  • 第二次见这个题目

  • 第一次写是在顺序表里面，写了一次超时了，学习了豆包的方法：直接用数组，剩余人数直接定义一个remaining的变量，学习了之后，看懂了直接上传了PTA（顺序表）2-13 约瑟夫环 | zhangzhang-blog

  • 这一次是自己手敲的，用到的是定义一个顺序表结构，用的L.length表示剩余人数

答案

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
#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;
}

int main (){
    int N, p;
    cin >> N >> p;
    sqList L;
    initList(L, N);
    // 给每个人原始序号到顺序表
    for (int i = 0; i < N; i++) {
        L.data[i] = i+1;
        L.length++;
    }

    bool firstOutPut = true;
    // 开始报数游戏
    int curr = 0; // 定义一个curr，表示当前退出的人的下标
    while (L.length != 0) {
        // 计算下一个退出的下标curr，取余剩余的人数L.length
        curr = (curr + p - 1) % L.length;

        // 将退出人的原始序号输出
        if (!firstOutPut) {
            cout << " ";
        }
        cout << L.data[curr];
        firstOutPut = false;
        // 将后续的人前移
        for (int i = curr; i < L.length-1; i++) {
            L.data[i] = L.data[i+1];
        }
        L.length--; // 剩余的人减一个
    }
}
  • 学会了就不难了