约瑟夫环#

发布于2020-12-11

上次编辑2021-04-20

Introduction

\(n\) 个编号为 \(0\to n-1\)，从 \(0\) 数到 \(k-1\)，数到 \(k-1\) 的人淘汰，从淘汰的人之后重新开始，持续该过程，问最后剩下的人的编号。

\(n\) 个人时，淘汰的是第 \(k-1\) 个人。

剩下的人的编号为 \(0\to k-2\) 和 \(k\to n-1\)。

重新开始的编号为：

\[ \begin{aligned} k &\to 0\\ k+1 &\to 1\\ &\vdots\\ k-2 &\to n-2 \end{aligned} \]

假设原问题表示为 \(q(n,k)\)，则淘汰一个人并重新编号之后相当于 \(q(n-1,k)\)，如果得到 \(q(n-1,k)\) 的答案，然后将编号重新转换回去就可以得到 \(q(n,k)\) 的答案。

从上面的转换中可以看出：

\[ q(n,k)=[q(n-1,k)+k]\bmod n \]

Python

def josephus(n: int, k: int) -> int:
    t = 0
    for i in range(2, n + 1):
        t = (t + k) % i
    return t

C++

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

例题#