josephus.md

约瑟夫问题由来已久，而这个问题的解法也在不断改进，只是目前仍没有一个极其高效的算法（log 以内）解决这个问题。

问题描述

n 个人标号 $0,1,\cdots, n-1$。逆时针站一圈，从 $0$ 号开始，每一次从当前的人逆时针数 $k$ 个，然后让这个人出局。问最后剩下的人是谁。

这个经典的问题由约瑟夫于公元 1 世纪提出，尽管他当时只考虑了 $k=2$ 的情况。现在我们可以用许多高效的算法解决这个问题。

朴素算法

最朴素的算法莫过于直接枚举。用一个环形链表枚举删除的过程，重复 $n-1$ 次得到答案。复杂度 $\Theta (n^2)$。

简单优化

寻找下一个人的过程可以用线段树优化。具体地，开一个 $0,1,\cdots, n-1$ 的线段树，然后记录区间内剩下的人的个数。寻找当前的人的位置以及之后的第 $k$ 个人可以在线段树上二分做。

线性算法

设 $J_{n,k}$ 表示规模分别为 $n,k$ 的约瑟夫问题的答案。我们有如下递归式

$$ J_{n,k}=(J_{n-1,k}+k)\bmod n $$

这个也很好推。你从 $0$ 开始数 $k$ 个，让第 $k-1$ 个人出局后剩下 $n-1$ 个人，你计算出在 $n-1$ 个人中选的答案后，再加一个相对位移 $k$ 得到真正的答案。这个算法的复杂度显然是 $\Theta (n)$ 的。

int josephus(int n, int k) {
    int res = 0;
    for (int i = 1; i <= n; ++i) res = (res + k) % i;
    return res;
}

对数算法

对于 $k$ 较小 $n$ 较大的情况，本题还有一种复杂度为 $\Theta (k\log n)$ 的算法。

考虑到我们每次走 $k$ 个删一个，那么在一圈以内我们可以删掉 $\left\lfloor\frac{n}{k}\right\rfloor$ 个，然后剩下了 $n-\left\lfloor\frac{n}{k}\right\rfloor$ 个人。这时我们在第 $\left\lfloor\frac{n}{k}\right\rfloor\cdot k$ 个人的位置上。而你发现这个东西它等于 $n-n\bmod k$。于是我们继续递归处理，算完后还原它的相对位置。得到如下的算法：

int josephus(int n, int k) {
    if (n == 1) return 0;
    if (k == 1) return n - 1;
    if (k > n) return (josephus(n - 1, k) + k) % n;  // 线性算法
    int res = josephus(n - n / k, k);
    res -= n % k;
    if (res < 0)
        res += n;  // mod n
    else
        res += res / (k - 1);  // 还原位置
    return res;
}

可以证明这个算法的复杂度是 $\Theta (k\log n)$ 的。我们设这个过程的递归次数是 $x$，那么每一次问题规模会大致变成 $\displaystyle n\left(1-\frac{1}{k}\right)$，于是得到

$$ n\left(1-\frac{1}{k}\right)^x=1 $$

解这个方程得到

$$ x=-\frac{\ln n}{\ln\left(1-\frac{1}{k}\right)} $$

下面我们证明该算法的复杂度是 $\Theta (k\log n)$ 的。

考虑 $\displaystyle \lim _{k \rightarrow \infty} k \log \left(1-\frac{1}{k}\right)$，我们有

$$ \begin{aligned} \lim _{k \rightarrow \infty} k \log \left(1-\frac{1}{k}\right)&=\lim _{k \rightarrow \infty} \frac{\log \left(1-\frac{1}{k}\right)}{1 / k}\\ &=\lim _{k \rightarrow \infty} \frac{\frac{\mathrm d}{\mathrm d k} \log \left(1-\frac{1}{k}\right)}{\frac{\mathrm d}{\mathrm d k}\left(\frac{1}{k}\right)}\\ &=\lim _{k \rightarrow \infty} \frac{\frac{1}{k^{2}\left(1-\frac{1}{k}\right)}}{-\frac{1}{k^{2}}}\\ &=\lim _{k \rightarrow \infty}-\frac{k}{k-1}\\ &=-\lim _{k \rightarrow \infty} \frac{1}{1-\frac{1}{k}}\\ &=-1 \end{aligned} $$

所以 $x \sim k \ln n, k\to \infty$，即 $-\dfrac{\ln n}{\ln\left(1-\frac{1}{k}\right)}= \Theta (k\log n)$

习题

[!NOTE] LeetCode LCR 187. 破冰游戏

题意: TODO

[!TIP] 思路

标准约瑟夫环

详细代码

C++

// AcWing
class Solution {
public:
    int lastRemaining(int n, int m) {
        if (n == 1)
            return 0;
        return (lastRemaining(n - 1, m) + m)% n;
    }

    int lastRemaining2(int n, int m){
        int res = 0;
        // 最后一轮剩下2个人，所以从2开始反推
        for (int i = 2; i <= n; ++ i )
            res = (res + m) % i;
        return res;
    }
};

Python

---

[!NOTE] LeetCode 390. 消除游戏

题意: TODO

[!TIP] 思路

(找规律)

题解：这道题其实是变种的约瑟夫循环问题。

我们用 f(n) 代表将 1 - n 先从左到右再从右到左遍历最后剩下来的数字

用 b(n) 代表将 1 - n 先从右到左，再从左到右遍历最后剩下来的数字。

我们可以发现其中一些规律：

• $f(1) = 1, b(1) = 1$
• $f(n) = 2 * b(n/2)$
• $f(n) + b(n) = n + 1$

规则1很好理解，是初始状态

规则2是因为，假设初始数组是 [1,2,3,4,5,6]，最终剩下来的数字是 f(6) ，经过第一轮从左到右遍历后剩下来的是 [2,4,6]，恰好是 2 * [1,2,3]，但是这时候我们开始要从右侧开始遍历了，最终剩下来的数字是 b(3)，我们可以发现 $f(6)=2*b(3)$ 。如果初始数组长度为奇数也可以得到一样的结果。

规则3是因为，假设 f(n) 最终留下来的是从左到右的第 k 个数字，那么 b(n) 和 f(n) 是对称的操作，那么最后剩下来的肯定是从右到左的第k个数字，在这一题中二者相加之和是 n+1 。

有了上面三个定理，答案就很好求解了，把公式3代入公式2可以得到：

$f(n) = 2 * b(n/2) = 2 * (n / 2 + 1 − f(n/2)) $

详细代码

C++

class Solution {
public:
    // 变种约瑟夫环
    int lastRemaining(int n) {
        if (n == 1) return 1;
        return 2 * (n / 2 + 1 - lastRemaining(n / 2));
    }
};

Python

---