约瑟夫环
西方有个故事：相传著名历史学家Josephus（约瑟夫）经历了这么一段经历，在罗马人占领乔塔帕特后，40个犹太人和Josephus躲在一个山洞中。40个犹太人决定宁死也不被敌人抓到，于是决定集体自杀。大家经过讨论，决定了一个自杀方式，41个人围成一个圆圈，由第1个人开始报数，每报数到3的人就必须自杀，然后再由下一个人重新开始报数，知道所有人都自杀身亡为止。
然而Josephus并不像遵从这个规则，不想自杀。于是Josephus先假装同意该方案，然后坐到大家围成圆圈的第31个为止，最后逃过了这场死亡游戏[1]。
Josephus怎么知道坐在31号位置就能成功躲避死亡呢？
撇开故事的真实性（其实挺搞笑的，大家一起同时自杀不是更好么？），解决这个问题的方法有两种，一个是“程序员”法，即模拟游戏的进行过程，最后出列的人即为赢家（没有人监督他是否会自杀）。这种方法容易理解，但是时间开销较大O(m*n)，假设n个人，按m报数。用循环链表法很容易实现，就不再赘述。另一种方法是“数学家法”，通过数学分析，直接得出结果。数学分析比较难懂，下面就详细介绍一下。
首先，简化一下问题表述。假设有n个人围成一个圆圈，按某个方向依次从0到n-1编号。从编号为0的人开始按相同的方向从0开始依次报数，报到m-1的人出列，然后又接着从0开始报数，如此循环，直到所有的人均出列。求最后出列的人。
第一轮报数情况如下：
编号：0 1 2 ... m-1 m ... n-2 n-1
报数：0 1 2 ... m-1 0 ... xx xx
其中xx表示未知，视情况而定。由此可知，第一轮报数的一定是编号为m-1的人（假设m<=n），若m>n，则为(m-1)%n
第二轮报数从编号m开始（更确切的说从m%n）开始，情况如下(设k=m%n)：
编号：k k+1 ... n-2 n-1 0 1 .. k-2
报数：0 1 ... xx xx xx xx .. xx
映射：0 1 ... n-2-k n-1-k n-k n+1-k .. n-2
同样，xx表示未知。给编号做一个映射，可知第二轮报数可看成n-1个人按m的报数问题。
接下来，我们看看两轮报数最后一个人的编号关系。假设n个人报数中，最后一个出列的人的编号为F(n)，映射中最后一个人的编号为F(n-1),则有F(n-1)-0=F(n)-k=F(n)-m%n，推出F(n)=F(n-1)+m%n。又因为F(n)、F(n-1)不可能大于n，因此F(n)=(F(n-1)+m)%n.
若n=1，表示只有一个人，最后出列的人的编号为0，即F(1)=0.
因此，递推公式为：
F(1)=0
F(n)=(F(n-1)+m)%n.
有了这个递推公式，就能很容易求出最后一个出列的人的编号了。其时间复杂度为O(n)，大大提高了效率。
[1] 周颖, 程序员的数学思维修炼, 清华大学出版社, P144
0 条评论