约瑟夫斯序列
有些人围成一圈等待执行。计数从圆的某个点开始，然后沿固定的方向围绕圆进行。在每个步骤中，将跳过一定数量的人，然后执行下一个人。消灭围绕圈（随着被处决的人被撤离而变得越来越小）进行，直到只有最后一个剩下的人被赋予自由。
我用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)呢？
回答：
为了获得被处决者和最后一个幸存者的序列，您只需要从一开始就模拟整个过程。给定过程的描述，这将是非常容易的任务。您提供的公式只是检查谁将生存并快速获得答案的捷径。
有关如何使用范围树在O（n log n）中执行此操作的说明，位于：http : //pl.scribd.com/doc/3567390/Rank-
Trees
可以在这里找到更详细的分析：http
:
//www.imt.ro/romjist/Volum12/Number12_1/pdf/02-MCosulschi.pdf
以上是 约瑟夫斯序列 的全部内容， 来源链接： utcz.com/qa/410311.html
