CDT*_*CDT 12 c c++ java algorithm josephus
描述: 有人站在一个圆圈等待处决.计数从圆圈中的某个点开始,并以固定方向围绕圆圈前进.在每个步骤中,跳过一定数量的人并执行下一个人.消除在圆圈周围进行(随着执行的人被移除而变得越来越小),直到只剩下最后一个人,给予自由.
我用谷歌搜索了这个'约瑟夫斯问题',维基百科的命中率给了我一个动态编程解决方案: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