有这么一个古老的问题:一群死刑犯排成圆圈,每隔一人枪毙一个,转完一圈后从头开始继续枪毙,直到剩下最后一个人,这个幸运儿会被释放。
问:一开始站在哪个位置才能活下来?
这就是著名的约瑟夫斯问题,排成的圆圈叫做约瑟夫斯环。
(当然,隔一人只是个特殊情况,约瑟夫斯问题包含了间隔任何人数的计算方法)
在上面维基百科的链接以及知乎的答案里已经有了通用的计算方法,这里就不必讲什么公式和证明了,而是直接用图形来演示:
这是我在知乎专栏发表的那篇知乎用户排行榜生成器0.2版的源码,为增强专栏的可读性所以在那边只放了压缩版的。这里是完整版,有兴趣者可以自行调试修改。
这段脚本需要登录知乎网站后在浏览器控制台运行,更详细的用法请点上面链接查看。 [阅读全文]