约瑟夫环

$n$ 个人围成一圈,编号按顺序从 $0$ 到 $n-1$,从第一个人开始报数,数到 $m$ 的人出列,再由下一个人重新从 $1$ 开始报数,数到 $m$ 的人再出圈,……依次类推,直到所有的人都出圈,请输出最后一个出圈的人的编号。


今天稍微学习了一下这个玩意儿,感觉还挺神奇的。

第一种做法:暴力模拟

这个我在这就不讲了,很容易就能写出来。

第二种做法:递推

我们先考虑第一个出圈的人。

  • $m < n$

那么这个人的编号即为 $m - 1$

  • $m \ge n$

那么这个人的编号即为 $(m - 1) \bmod n$

综合一下,第一个出圈的人的编号绝对为 $(m - 1) \bmod n$

方便起见,我们设 $k - 1 = (m - 1) \bmod n$ 。

于是这个圈就变成了这样:

$k \quad k+1 \quad k+2 \quad ... \quad n-2 \quad n-1 \quad 0 \quad 1 \quad 2 \quad ... \quad k-3 \quad k-2$

这个时候我们将这个圈转换一下,变成:

$0 \quad 1 \quad 2 \quad ... \quad n - 3 \quad n - 2$

可以发现其实这个问题变成了 $n-1$ 个人报数的子问题。

所以我们只要将子问题的答案转换回去,就能知道最后那个人原来的编号。

稍微观察一下如何转换回去:

$0 \Rightarrow k$

$1 \Rightarrow k + 1$

$...$

$n - k - 1 \Rightarrow n - 1$

$n - k \Rightarrow 0$

$n - k + 1 \Rightarrow 1$

$...$

$n - 3\Rightarrow k - 3$

$n - 2 \Rightarrow k - 2$

不难发现 $x$ 转换回去后就变成了 $(x + k) \bmod n$

我们设 $f[n]$ 表示 $n$ 个人报 $m$ 最后出圈人的编号。

显然,$f[1]=0$

而根据我们刚才推的公式:

$$f[n]=(f[n - 1]+k) \bmod n = (f[n - 1]+m \bmod n) \bmod n = (f[n - 1]+m ) \bmod n$$

于是就可以愉快的递推了~

代码

1
2
3
4
5
6
7
int Josephus(int n, int m)
{
int res = 0;
for (int i = 2; i <= n; i ++)
res = (res + m) % i;
return res;
}