每日算法-约瑟夫环问题

-- Pageviews

josephring

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

约瑟夫问题

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

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

举例说明

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

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

josephring

从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 的排列了!

josephring

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

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

公式导出

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

写出代码

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

1
2
3
4
5
6
7
8
9
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;
}
}