约瑟夫斯问题:最后生还者

有这么一个古老的问题:一群死刑犯排成圆圈,每隔一人枪毙一个,转完一圈后从头开始继续枪毙,直到剩下最后一个人,这个幸运儿会被释放。

问:一开始站在哪个位置才能活下来?

这就是著名的约瑟夫斯问题,排成的圆圈叫做约瑟夫斯环。

(当然,隔一人只是个特殊情况,约瑟夫斯问题包含了间隔任何人数的计算方法)

在上面维基百科的链接以及知乎的答案里已经有了通用的计算方法,这里就不必讲什么公式和证明了,而是直接用图形来演示:

用法很简单:在最上面输入准备枪毙的总人数(最多500人)和间隔人数(最少1个,最多不超过总人数);如果勾选了“连续运行”,它每一轮跑完之后就会增加人数自动开始下一轮。

需要浏览器支持HTML5才能显示。

8 comments

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注