Tag: josephus

约瑟夫斯序列

描述：有人站在一个圆圈等待处决。 计数从圆圈中的某个点开始，并以固定方向围绕圆圈前进。 在每个步骤中，跳过一定数量的人并执行下一个人。 消除在圆圈周围进行（随着被执行的人被移除而变得越来越小），直到只剩下最后一个人，给予自由。 我用Google搜索了这个’约瑟夫斯问题’并且维基百科命中给我一个动态编程解决方案： 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)解决方案？