约瑟夫环

问题描述

$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 $$

1
2
3
4
5


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

1
2
3
4
5


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