一尘不染

约瑟夫斯序列

algorithm

说明:
有些人围成一圈等待执行。计数从圆的某个点开始,然后沿固定的方向围绕圆进行。在每个步骤中,将跳过一定数量的人,然后执行下一个人。消灭围绕圈(随着被处决的人被撤离而变得越来越小)进行,直到只有最后一个剩下的人被赋予自由。

我用Google搜索了这个“约瑟夫问题”,而Wikipedia命中给了我一个动态编程的解决方案:f(n,k)=((f(n-1,k)+k-1) mod n)+1, with f(1,k)=1,但这只会产生最后一个幸存者。我如何获得被处决人员的顺序?假设p(5,3)= {3,1,5,2,4}。

另外,有没有一种O(nlogn)解决方案O(nk)呢?


阅读 446

收藏
2020-07-28

共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

2020-07-28