# 约瑟夫问题

> source: 文章/josephus/index.md

# 约瑟夫问题

经典动态规划问题

<!-- more -->

## 问题描述

$0,1,\cdots, n-1,n$个数排成一个圈，从数字$0$开始，每次从这个圈里删除第$m$个数字，求最后剩下的数字是哪个

![Josepuh](https://mdstore.oss-cn-beijing.aliyuncs.com/markdown/Josepuh.png)

现在假设我们取走的是$2$，也就是第$3$个数，$m=3$，那么取走的数就是$m-1$

则下一次从当前的第$5$个数开始，即$m+1$，第$m+1$个数将成为下一轮的第$1$个数

## 数学表达

对于这个问题，最重要的是我们需要找到用数学语言表达上面操作的方法，更一般的情况，我们可以设取走的数为$k$
$$
k = (m-1)\bmod n
$$
并设这个操作为函数$f(n,m)$

接下来我们看看这个操作在数学上还做了什么
$$
\left.
\begin{align}
k+1 \to 0 \\
k+2 \to 1 \\
\cdots \\
n-1 \to n-k-2
\end{align}
\right\}
\Longrightarrow p(x) = x - k -1 ,k+1 \le x \le n-1
$$

$$
\left.
\begin{align}
0 \to n-k-1 \\
1 \to n-k \\
\cdots \\
k \to n-2 \\
\end{align}
\right\}
\Longrightarrow p(x) = x + n - k -1 ,0 \le x \le k-1
$$


根据特殊情况入手，对左右两边加减不难得到这两段递推式，现在我们就得到了一个分段函数，这其实就是上一轮取走数字后，对下一轮数字顺序的映射

事实上我们还可以对上面这个分段函数作简化
$$
p(x) = (x+n-k-1)\bmod n
$$
我们想使用$f(n,m)$这个函数不停做递归操作，来得到我们想要的结果，但是现在的问题是，一开始我们的数字和数字的序号是能够对应上的，差值为$1$，但是经过一轮以后，这个序号被改变了，按照上面的映射函数改变

对于这个已经改变的队列，我们设为$a(n-1,m)$因为它只有$n-1$个数了，于是现在我们就有了关系
$$
f(n,m) = a(n-1,m)
$$
对于$a(n-1,m)$，我们其实只要将它看作一个顺序不同的数列就可以，到这里我们发现貌似有希望建立递归关系了，因为$n$与$n-1$之间已经建立了某种映射关系

而我们知道，对于$f(n-1,m)$，我们按照$p(x)$的方式进行重排映射，得到的结果其实就是$a(n-1,m)$，也就是
$$
f(n-1,m) = p(a(n-1,m))
$$
因此
$$
a(n-1,m) = p^{-1}(f(n-1,m))
$$
我们需要得到$p(x)$的反函数
$$
p(x) = (x+n-k-1)\bmod n = x+n-k-1+(T-1)n = x-k-1+Tn
$$

$$
x= p^{-1}(x)-k-1+Tn \Longrightarrow p^{-1}(x) = x+k+1-Tn = (x+k+1) \bmod n
$$

因此
$$
\begin{align}
a(n-1,m) &= (f(n-1,m)+k+1)\bmod n \\\\
  &= (f(n-1,m)+((m-1)\bmod n)+1)\bmod n \\\\
  &= ((f(n-1,m)+1)\bmod n+((m-1)\bmod n))\bmod n \\\\
  &= (f(n-1,m)+1+m-1)\bmod n \\\\
  &= (f(n-1,m)+m)\bmod n 
\end{align}
$$
这里用到了模运算的性质
$$
(a+b)\bmod p = (a\bmod p + b\bmod p)\bmod p
$$
而$0<f(n-1)<n-2$，因此$1<f(n-1)+1<n-1$，模运算可以自由添加

于是我们就可以得到一个递推公式
$$
f(x) = 
\left\{
\begin{align}
0\qquad\qquad,n=1\\
(f(n-1,m)+m)\bmod n , n>1
\end{align}
\right.
$$

## 算法实现



## References

1. [算法精解：约瑟夫（Josephus）问题](https://zhuanlan.zhihu.com/p/35487124)
2. [这或许是你能找到的最详细约瑟夫环数学推导！](https://www.zhihu.com/tardis/zm/art/121159246?source_id=1003)
3. [约瑟夫问题 OI Wiki](https://oi-wiki.org/misc/josephus/)
