约瑟夫环问题

约瑟夫环问题

$n$ 个人围成一圈，从第一个开始报数，数到第 $m$ 个的人会被杀掉，直到剩下一个人，求解最后存活的是哪一个人。

抽象描述

$0,1,2,…,n-1$ 这些数字围成一圈，从第 $0$ 个数字开始，每次删除第 $m$ 个数字，求最后剩下的那个数字。

解法

Definition 1: $f(n,m)$

$f(n,m)$：表示 $n$ 个数字围成一圈，从第 $0$ 个数字开始，每次删除第 $m$ 个数字，最后剩下的那个数字。

$0,1,2,…,n-1$ 这 $n$ 个数字中，被删除的是数字 $(m-1)%n$，令 $k=(m-1)%n$，则第一次删除后剩下的数字为 $0,1,2,…,k-1,k+1,…,n-1$，下一次删除是从 $k+1$ 开始数，于是我们可以把该序列改写为 $k+1,…,n-1,0,1,…,k-1$。

Definition 2: $g(n-1,m)$

$g(n-1,m)$：表示从 $k+1,…,n-1,0,1,…,k-1$ 这 $n-1$ 个数字中，从 $k+1$ 开始，每次删除第 $m$ 个数字，最后剩下的那个数字。

显然，$f(n,m)=g(n-1,m)$。（因为最后剩下的数字是同一个）

Definition 3: $h(x)$

$h(x)$：一个从 $f(n-1,m)$ 到 $g(n-1,m)$ 的映射。

下面求解这个 $h(x)$，观察如下映射规则：
$0\rightarrow k+1$

$1\rightarrow k+2$
$…$
$n-3\rightarrow k-2$
$n-2\rightarrow k-1$
可得：$h(x)=(x+k+1)%n$，因此有:

$$\begin{array}{rl}f(n,m)& =g(n-1,m)\\ & =h(f(n-1,m))\\ & =(f(n-1,m)+k+1)\mathrm{\%}n\\ & =(f(n-1,m)+(m-1)\mathrm{\%}n+1)\mathrm{\%}n\\ & \stackrel{①}{=}((f(n-1,m)+1)\mathrm{\%}n+(m-1)\mathrm{\%}n)\mathrm{\%}n\\ & \stackrel{②}{=}((f(n-1,m)+1)+(m-1))\mathrm{\%}n\\ & =(f(n-1,m)+m)\mathrm{\%}n\end{array}$$

其中$①：0\leq f(n-1,m)\leq n-2$，$1\leq f(n-1,m)+1\leq n-1$，因此 $(f(n-1,m)+1)%n= f(n-1,m)+1$

$②:distributive\ law:(a+b)%p=(a%p+b%p)%p$

最终我们有递推公式：

$$f(n,m)=\{\begin{array}{cl}0& n=0\\ (f(n-1,m)+m)\mathrm{\%}n& n>1\end{array}$$

代码实现

递归

int josephus(int n, int m) {
    if (1 == n) {
        return 0;
    }
    return josephus(n - 1, m) % n;
}

动态规划

int josephus(int n, int m) {
    int dp = 0;
    for (int i = 2; i <= n; ++i) {
        dp = (dp + m) % i;
    }
    return dp;
}