说明：有个人站在了一圈等待被执行。 计数出开始于在一个固定的方向上的圆，并进入周围的圆一些点。 在每个步骤中的一定的人数被跳过并执行下一个人。 绕了一圈消除收入（这是越来越小，因为执行的人将被删除），直到只剩下最后一个人仍然存在，谁被赋予的自由。
我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 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 。
人们将存储在大小为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（n）〕，同时寻求O（nlogn）时间复杂度在同一时间。 因为你必须输出要执行的每一个人，这是O（n）。
kkonrad的参考量程树木产生一个很好的O（nlogn）的解决方案。 正如其他人所指出的那样，循环链表是这个问题的一个有效的数据结构。 我找到代码审查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
