约瑟夫斯问题

来自计算思维百科
跳转至: 导航搜索

约瑟夫斯问题是个有名的问题。著名犹太历史学家 Josephus讲述了以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是约瑟夫斯建议每个人应轮流杀死旁边的人,而这个顺序是由抽签决定的。问题是,一开始要站在什么地方才能避免被处决?Josephus有预谋地抓到了最后一签,逃过了这场死亡游戏。

解决方法

我们先来讨论人数较少的情况:

(1)当有6个人时,6个人围成圈,从一号开始游戏,每次杀死第二个人直到只剩一个人;(红色表示被杀死)

第一轮:如下,2,4,6都被杀死

第二轮:如下,1,3都被杀死。

游戏结束,5号胜利。

约瑟夫斯问题1.png

(2)当有7个人时;(红色表示被杀死)

第一轮:2,4,6都被杀死,然后轮到1,所以一轮下来,杀死的是1,2,4,6;

第二轮:如下,3,5都被杀死;

游戏结束,7号胜利。

约瑟夫斯问题2.png

我们再讨论一般情况,即有n个人时,分为偶数和奇数的情况。

情况1:n为偶数,设n=2k。

我们知道第一轮之后,杀掉的人编号一定是m%2(m是人的编号),剩下的k个人组成了一个新的约瑟夫环,这些人的编号是2i+1,i=0,1,…,k-1,即

  1  3  5  7 ... 2k-1

现在从1开始报,我们把他们的编号做一下转换:

1     --> 1

3     --> 2

5     --> 3

...

2k-1   --> k

变换后就完完全全成为了新的报数的子问题,假如我们知道这个子问题的解,即k个人时报数的胜利者是J(k),那么根据上面这个表可以看出来,如果k个人的报数问题的解是J(k),他对应在初始问题中的位置是2J(k)-1,这样,就可以得到新问题与初始问题的解关系为,J(2k)=2J(k)-1。这显然就是一个递推问题!

 

情况2:n为:奇数,设n=2k+1,经过一轮后,杀掉的人编号一定是m%2(m是人的编号),还有一个杀掉的是1号,剩下的k个人组成了一个新的约瑟夫环,这些人的编号是2i+1,i=1,…,k-1,现在从1开始报,我们把他们的编号做一下转换:

3     --> 1

5     --> 2

...

2k-1   --> k

按照偶数的情况,如果k个人的报数问题的解是J(k),他对应在初始问题中的位置是2J(k)+1,这样就可以得到递推式J(2k+1)=2J(k)+1。

在知道这两种情况下的递推关系后,我们知道只有一个人的时候,J(1)=1,如果现在是6个人,J(6)=2J(3)-1=2(2J(1)+1)-1=5,那就是5号是最后的胜利者。

可以体现的计算思维

从上面的分析我们容易看出,每一轮的解都可以由规模减半后的问题的解得到,即它可以被分解成规模小的等价子问题,依次分解至最小规模,再向上可以依次解出父问题的解,体现了计算思维中的规约思想。