每日算法-约瑟夫环问题

最近开始在做算法题，不全是为了找工作，为了面试，旨在不断思考，锻炼思维，同时查阅别人的解题方法，开拓自己的思路。在遇到实际问题时，可以有料参考，有迹可循。

约瑟夫问题

这个问题是以弗拉维奥·约瑟夫命名的，他是1世纪的一名犹太历史学家。他在自己的日记中写道，他和他的40个战友被罗马军队包围在洞中。
他们讨论是自杀还是被俘，最终决定自杀，并以抽签的方式决定谁杀掉谁。约瑟夫斯和另外一个人是最后两个留下的人。约瑟夫斯说服了那个人，他们将向罗马军队投降，不再自杀。
约瑟夫斯把他的存活归因于运气或天意，他不知道是哪一个。 —— 【约瑟夫问题】维基百科

解题秘诀：只关心最终活着那个人的序号变化

举例说明

我们也给每个人一个编号（索引值），单个人用字母代替，下面这个例子是N=8 m=3的例子

定义F(n,m)表示最后剩下那个人的索引号，因此只关心最后剩下来这个人的索引号的变化情况即可

从8个人开始，每次杀掉一个人，去掉被杀的人，然后把杀掉那个人之后的第一个人作为开头重新编号

• 第一次C被杀掉，人数变成7，D作为开头，（最终活下来的G的编号从6变成3）
• 第二次F被杀掉，人数变成6，G作为开头，（最终活下来的G的编号从3变成0）
• 第三次A被杀掉，人数变成5，B作为开头，（最终活下来的G的编号从0变成3）
• 以此类推，当只剩一个人时，他的编号必定为0！（重点！）

反推过程

从N = 7 到N = 8 的过程

如何才能将N = 7 的排列变回到N = 8 呢？

我们先把被杀掉的C补充回来，然后右移m个人，发现溢出了，再把溢出的补充在最前面

神奇了 经过这个操作就恢复了N = 8 的排列了！

因此我们可以推出递推公式 $ f(8,3) = [f(7, 3) + 3] \% 8 $

进行推广泛化，即 $ f(n,m) = [f(n-1, m) + m] \% n $

公式导出

再把n=1这个最初的情况加上，就得到递推公式

$$f(n，m)=\begin{cases}0,&\text{n=1}\\ [f(n-1, m)+m]\%n,&\text{n>1}\end{cases}$$

写出代码

照着递推公式写即可，也可写成递归的形式

class Solution {
    public int lastRemaining(int n, int m) {
        int pos = 0;
        for(int i = 2; i<=n; i++){
          pos = (pos + m) % i;
        }
        return pos;
    }
}