约瑟夫环 模拟与递推解法

约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知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;
}

模拟链表模拟代码

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

二、递推求解

时间复杂度为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;
}

Azure99

底层码农,休闲音游玩家,偶尔写写代码

看看这些?

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注