约瑟夫环 模拟与递推解法

约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。

约瑟夫环问题通常使用两类解决方法：

一、暴力模拟求解

时间复杂度为O(n*m)，空间复杂度为O(n)，可以求得最后出局的人与整个过程中人员出局的顺序。

当然，模拟也有很多种方式，

1.用数组模拟（使用一个大小为n的数组记录人员是否出局）。

2.用单循环链表模拟（每个Node就是一个人，保存了下一个人的地址）。

3.通过模拟链表来模拟（使用三个数组，一个记录人员出局情况，两个记录此人前后的人的编号，时空开销都略优于用单循环链表模拟）。

more…

数组模拟代码

#include <iostream>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    bool que[n + 1]; // 记录此编号的人是否在队里
    // 初始化所有人都在队里
    for (int i = 0; i < n + 1; i++) {
        que[i] = true;
    }

    int inQue = n; // 在队里的人数
    int cnt = 0; // 当前报号
    int pos = 1; // 当前位置

    // 如果队里还有人
    while (inQue > 0) {
        // 如果当前报号为m
        if (++cnt == m) {
            inQue--;
            cnt = 0; // 重新计次
            que[pos] = false;
            cout << pos << endl;
        }

        // 查找下一个有人的位置
        while (pos++ && inQue > 0) {
            // 如果到了最后一个人
            if (pos == n + 1) {
                pos = 1; // 返回队首
            }
            // 如果此编号的人还未出局
            if (que[pos]) {
                break; // 找到，停止查找
            }
        }
    }

    return 0;
}
</iostream>
Code language: PHP (php)

模拟链表模拟代码

#include <iostream>

using namespace std;

int main() {
    int n, m;

    cin >> n >> m;
    int inQue = n; // 在队中的人数

    bool que[n + 1]; // 保存此编号是否在队中
    int up[n + 1]; // 此编号人员的上一个人员的编号
    int down[n + 1]; // 此编号人员的下一个人员的编号

    // 初始化
    for (int i = 1; i <= n; i++) {
        que[i] = true;
        up[i] = i - 1;
        down[i] = i + 1;
    }
    up[1] = n; // 跳到队尾
    down[n] = 1; // 跳到队首

    int cnt = 0; // 当前报号
    int pos = 1; // 当前位置
    while (inQue > 0) {
        if (++cnt == m) {
            inQue--;
            cnt = 0;
            cout << pos << endl;

            up[down[pos]] = up[pos]; // 更新此编号的上一个人员
            down[up[pos]] = down[pos]; // 更新此编号的下一个人员
        }

        pos = down[pos]; // 跳到下一个位置
    }

    return 0;
}
</iostream>
Code language: PHP (php)

二、递推求解

时间复杂度为O(n)，空间复杂度为O(1)，但是仅可以求得最后出局的人。
详细递推过程

队里有n个人，我们对其编号：
0, 1, 2, ..., n-1

然后进行一轮淘汰，因为报到m的人出队，所以第一次出队的人必为(m - 1) % n(环尾下一个为环首)
现在队伍的情况为：
0, 1, 2, ..., m-2, m-1, m, ..., n-1

将m-1标记为@，已经出队。
0, 1, 2, ..., m-2,  @ , m, ..., n-1。

对其重新编号，让m为0，则有：
n-m, n-m+1, ..., n-2, 0, 1, ..., n-1-m

抛开现在的结果不看，假设我们现在要解决共有n-1人的情况，对其编号，
0, 1, 2, ..., n-2。

不难发现，这种情况与n人出队一次之后的情况非常相似，只是编号相差了m。

我们可以一直推下去：有n-2人，有n-3人, ..., 有1人。
这样就得到了递推式：
res[n] = (res[n-1] + m) % n;
当然，只有1人的时候res[1] = 0;

我们求解只需要从res[1]推到res[n]即可。

代码

#include <iostream>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    int res = 0; // 1人时必定是编号为0的人出队
    for (int i = 2; i <= n; i++) {
        res = (res + m) % i;
    }

    cout << res + 1;
    return 0;
}
</iostream>
Code language: PHP (php)