14

描述： 有人围成一圈等待被处决。计数从圆圈中的某个点开始，并沿固定方向围绕圆圈进行。在每个步骤中，都会跳过一定数量的人并执行下一个人。消除围绕圆圈进行（随着被处决的人被移除，圆圈变得越来越小），直到只剩下最后一个人，他被赋予了自由。

我用谷歌搜索了这个“约瑟夫斯问题”，维基百科的热门文章给了我一个动态编程解决方案：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)吗？

4

5 回答 5

8

要获得被处决者和最后幸存者的序列，您只需要从一开始就模拟整个过程。鉴于程序的描述，这将是一项非常容易的任务。您提出的公式只是检查谁将生存并快速获得答案的捷径。

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

更详细的分析可以在这里找到： http ://www.imt.ro/romjist/Volum12/Number12_1/pdf/02-MCosulschi.pdf

于 2013-03-09T13:20:01.220 回答
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运行该程序。

于 2013-03-09T13:56:42.717 回答
1

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

输入： People[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
于 2013-03-09T13:25:18.123 回答
1

为了激发程序，您可以使用一个结构，其中包含玩家的名称和一个标签，该标签在玩家是否处于活动状态时保持跟踪。每次在新一轮中，您都会跳过特定数量的玩家，因此请使用循环和条件语句，以便忽略所有不在游戏中的玩家，只计算游戏中的玩家。当然，添加 printf 语句来打印当前状态。

于 2013-03-09T13:32:31.930 回答
1

要回答输出执行顺序的问题，需要进行模拟。这意味着 O(nk) 复杂度。在寻求 O(nlogn) 时间复杂度的同时，不可能获得执行顺序 [即 O(n)]。因为你必须输出每个被执行的人，也就是 O(n)。

kkonrad 对范围树的引用产生了一个很好的 O(nlogn) 解决方案。正如其他人指出的那样，循环链表是解决此问题的有效数据结构。我发现 Code Review 中的 200_success 的 Java 解决方案非常优雅且易读。

public class CircularGunmenIterator<T> implements Iterator<T> {

  private List<T> list;
  private Iterator<T> iter;

  public CircularGunmenIterator(List<T> 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<Integer> gunmen = new LinkedList<Integer>();
    for (int i = 1; i <= 100; i++) {
      gunmen.add(i);
    }

    // Shootout!
    Iterator<Integer> ringIter = new CircularGunmenIterator<Integer>(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），维基百科有更多详细信息。

http://en.wikipedia.org/wiki/Josephus_problem

于 2014-07-31T01:27:52.310 回答