java - 约瑟夫序列

Question

说明: 有人围成一圈等待处决。计数从圆圈中的某个点开始，并沿固定方向围绕圆圈进行。在每个步骤中，都会跳过一定数量的人并执行下一个人。消除围绕圆圈进行(随着被处决的人被移除，圆圈变得越来越小)，直到只剩下最后一个人，他被赋予了自由。

我在谷歌上搜索了这个“约瑟夫斯问题”，维基百科的命中给了我一个动态编程解决方案:f(n,k)=((f(n-1,k)+k-1) mod n) +1，f(1,k)=1，但这只会产生最后一个幸存者。我怎样才能得到执行的人的顺序？比如说，p(5, 3) = {3,1,5,2,4}。

另外，是否有 O(nlogn) 解决方案而不是 O(nk) 解决方案？

Answer 1

要获得被处决者和最后幸存者的序列，您只需要从头开始模拟整个过程。鉴于程序的描述，这将是一项非常容易的任务。您提出的公式只是检查谁将幸存并快速获得答案的捷径。

关于如何使用范围树在 O(n log n) 中执行此操作的说明如下: http://pl.scribd.com/doc/3567390/Rank-Trees

更详细的分析可以在这里找到: http://www.imt.ro/romjist/Volum12/Number12_1/pdf/02-MCosulschi.pdf