约瑟夫斯序列
描述：有人站在一个圆圈等待处决。 计数从圆圈中的某个点开始，并以固定方向围绕圆圈前进。 在每个步骤中，跳过一定数量的人并执行下一个人。 消除在圆圈周围进行（随着被执行的人被移除而变得越来越小），直到只剩下最后一个人，给予自由。
我用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)解决方案？
要获得已执行人员和最后幸存者的序列，您只需要从头开始模拟整个过程。 鉴于程序的描述，这将是非常容易的任务。 您提供的公式只是检查谁将存活并快速获得答案的捷径。
有关如何使用范围树在O（n log n）中执行此操作的说明，请访问： http ： //pl.scribd.com/doc/3567390/Rank-Trees
更详细的分析可以在这里找到： http ： //www.imt.ro/romjist/Volum12/Number12_1/pdf/02-MCosulschi.pdf
表示人的最自然的数据结构是循环缓冲区。 我的解决方案创建一个链表，将列表的尾部重新绑定到头部，然后重复计数缓冲区到下一个要执行的人，从缓冲区中删除该人，并继续直到缓冲区的尾部指向自身。
(define (cycle xs) (set-cdr! (last-pair xs) xs) xs) (define (josephus nm) (let loop ((k (- m 1)) (alive (cycle (range 0 n))) (dead '())) (cond ((= (car alive) (cadr alive)) (reverse (cons (car alive) dead))) ((= k 1) (let ((dead (cons (cadr alive) dead))) (set-cdr! alive (cddr alive)) (loop (- m 1) (cdr alive) dead)))
例如：
> (josephus 41 3) (2 5 8 11 14 17 20 23 26 29 32 35 38 0 4 9 13 18 22 27 31 36 40 6 12 19 25 33 39 7 16 28 37 10 24 1 21 3 34 15 30)
您可以在我的博客上阅读更全面的解释，它提供了三种不同的解决方案。 或者您可以在http://programmingpraxis.codepad.org/RMwrace2上运行该程序。
人们将被存储在大小为n的数组中。 如果索引i的人现在被执行，则下一个将由(i+k)%m ，其中m是剩余的人数。 每次迭代后，数组大小将减少1，其余元素将相应地移位。
输入：人物[0..n-1]，n，k，i（=第一人执行的索引）
伪代码将是这样的：
Print People[i] While (n > 1) do n = n - 1 for j = i to n-1 People[j] = People[j+1] i = (i+k) % n print People[i] done
为了激发程序，您可以使用包含玩家名称的结构和一个标记，如果玩家处于活动状态，该标记可以保留跟踪。 每次在新一轮中你跳过特定数量的玩家，所以使用循环和条件语句，以便忽略游戏中的所有玩家，并且只计算游戏中的玩家。 当然，添加printf语句来打印当前状态。
要回答输出执行顺序的问题，需要进行模拟。 这意味着O（nk）的复杂性。 在同时寻求O（nlogn）时间复杂度的同时，不可能得到执行序列[O（n）]。 因为你必须输出每个要执行的人，即O（n）。
kkonrad对Range Trees的引用产生了一个很好的O（nlogn）解决方案。 正如其他人所指出的，循环链表是这个问题的有效数据结构。 我发现Code Review的200_success’Java解决方案非常优雅和可读。
public class CircularGunmenIterator implements Iterator { private List list; private Iterator iter; public CircularGunmenIterator(List list) { this.list = list; this.iter = list.iterator(); } @Override public boolean hasNext() { // Continue as long as there is a shooter and a victim return this.list.size() >= 2; } @Override public T next() { if (!this.iter.hasNext()) { // Wrap around, creating the illusion of a circular buffer this.iter = this.list.iterator(); } return this.iter.next(); } @Override public void remove() { this.iter.remove(); } public static void main(String[] args) { // Create the gunmen List gunmen = new LinkedList (); for (int i = 1; i <= 100; i++) { gunmen.add(i); } // Shootout! Iterator ringIter = new CircularGunmenIterator (gunmen); while (ringIter.hasNext()) { Integer shooter = ringIter.next(); Integer victim = ringIter.next(); System.out.printf("%2d shoots %2d\n", shooter, victim); ringIter.remove(); // Bang! } System.out.println("Last one alive: " + gunmen.get(0)); } }
维基百科上有关于这个约瑟夫问题的更多细节（k = 2）。