约瑟夫斯序列

Question

描述：有很多人站在一个圆圈里等待被执行。计数从圆中的某个点开始，并沿着一个固定的方向绕着圆圈进行。在每个步骤中，跳过一定数量的人，然后执行下一个人。消灭在圆圈周围进行(随着被处决的人被移走而变得越来越小)，直到只有最后一个人被给予自由。

我搜索了这个‘约瑟夫斯问题’，维基百科的点击给了我一个动态编程的解决方案：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)解决方案？

Answer 1

要获得被执行人员和最后幸存者的序列，只需从一开始就模拟整个过程。给出程序的描述，这将是相当容易的任务。你给出的公式只是检查谁能活下来并迅速得到答案的捷径。

关于如何在O(n log n)中使用范围树进行此操作的说明如下：http://pl.scribd.com/doc/3567390/Rank-Trees

更详细的分析可以在这里找到：1/pdf/02-MCosulschi.pdf

Answer 2

表示人的最自然的数据结构是一个循环缓冲区。我的解决方案创建一个链接列表，将列表的尾部绑定回头部，然后在缓冲区周围重复计数到要执行的下一个人，将该人从缓冲区中移除，并一直持续到缓冲区的尾部指向自身。

(define (cycle xs)
  (set-cdr! (last-pair xs) xs) xs)

(define (josephus n m)
  (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运行该程序。

Answer 3

人员将被存储在大小为n的数组中。如果索引i处的人员现在被执行，那么下一个人将由(i+k)%m给出，其中m是剩余的人数。每次迭代之后，数组大小将减少1，其余元素将相应移动。

输入:People0.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