🟠 约瑟夫问题\#
经典动态规划问题
问题描述\#
\(0,1,\cdots, n-1,n\)个数排成一个圈，从数字\(0\)开始，每次从这个圈里删除第\(m\)个数字，求最后剩下的数字是哪个
现在假设我们取走的是\(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 $$
根据特殊情况入手，对左右两边加减不难得到这两段递推式，现在我们就得到了一个分段函数，这其实就是上一轮取走数字后，对下一轮数字顺序的映射
事实上我们还可以对上面这个分段函数作简化 $$ 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 $$
因此 $$ \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. $$