约瑟夫问题（有时也称为约瑟夫斯置换），是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。

人们站在一个等待被处决的圈子里。计数从圆圈中的指定点开始，并沿指定方向围绕圆圈进行。在跳过指定数量的人之后，执行下一个人。对剩下的人重复该过程，从下一个人开始，朝同一方向跳过相同数量的人，直到只剩下一个人，并被释放。

问题即，给定人数、起点、方向和要跳过的数字，选择初始圆圈中的位置以避免被处决。

约瑟夫问题

历史

这个问题是以弗拉维奥·约瑟夫命名的，他是1世纪的一名犹太历史学家。他在自己的日记中写道，他和他的40个战友被罗马军队包围在洞中。他们讨论是自杀还是被俘，最终决定自杀，并以抽签的方式决定谁杀掉谁。约瑟夫斯和另外一个人是最后两个留下的人。约瑟夫斯说服了那个人，他们将向罗马军队投降，不再自杀。约瑟夫斯把他的存活归因于运气或天意，他不知道是哪一个。

wizlyk

分析

这个问题的背景还是挺沉重的，但我们现在关心的是怎么解决这个问题。

约瑟夫环问题可以有很多种问法，比如找到一定次数后不会被出列的位置、给出出列的顺序、判断最后剩下的人的位置等等，接下来我们将对这些问题给出一个统一的解决方案。

问题：假设队列中一共有n个人，每次找到第m个人出列，然后从第m+1个人开始数，再找第m个人出列，直到队列里空无一人。求每次出列的人在原队列中的位置。

首先，直接从模拟操作入手，可以用链表或数组，每次移动一定的位置并做好标记（链表可以删除节点，数组可以做标记），然后每次输出找到的位置就行。对于链表，移动的总步数在 O(n*m)的量级，对于数组，移动的总步数在O(n^2)的量级。

上面的做法，判断最后一个剩下的人的位置需要O(n*m)的时间。但由于问题的规则已经非常清楚了，每一步操作后，下一步的状态已经确定，那么有没有O(n)的办法直接得到最后一个人的位置呢？

答案当然是有的。

要做到O(n)，首先要考虑每一步和其上一步的关系，只有能在O(1)的时间内得到转移的方式，才能实现O(n)的总体时间复杂度。

假设在倒数第i步，未出列的共i个人，第一个报数的人编号记为0（记为1也行，但在稍后的求余操作中会多出减1和加1的操作，不够简洁）。考虑在第m个人出列后，倒数第(i-1)步的编号变化。见下表。

倒数第i步的编号	倒数第(i-1)步的编号
0	i - m
1	i - m + 1
2	i - m +２
...	...
m - 2	i - 2
m - 1 (出列位置)	- (无)
m	0
...	...
i - 1	i - m - 1

若记倒数第i步的第k个位置标号为 \(f(i, k)\),则有

\[f(i,k) = \big(f(i-1,k)+m\big) \mod i\]

这个公式告诉我们，当我们知道后面出列的人在其队列中的编号，我们可以推出他在出列前的编号。比如我们知道最后一个人出列时他的编号只能为0（因为队伍只有一个人），那么就可以一直推出最后出列的人在初始队列中的编号。

举个例子，n=4，m=3，求最后一次出列的人在队列中的编号。

倒数第i次（剩下i个人）	编号	计算公式
1	0	-
2	1	(0 + 3) % 2
3	1	(1 + 3) % 3
4	0	(1 + 3) % 4

则可知最后一次出列的人编号为0。

那么如果我们想知道第k个出列的人是谁怎么办呢？可以知道，第k个出列的人出列前，队伍里剩下(n-k+1)个人，而他现在在队伍里的编号是 \((m-1) \mod (n-k+1)\)。因此，我们可以用递归来求：

// 求第k次出列的人的编号
int JosephusProblem(int n, int m, int k) {
  if (k == 1) return (m - 1) % n;
  return (JosephusProblem(n - 1, m, k - 1) + m) % n ;
}

用上递归后，程序非常的简洁。由于是尾递归，可以很容易地写成迭代的方式：

int ans = -1;
for (int i = 1; i <= k; ++i) {
    ans = (ans + m) % (n - k + i);
}

要求最后一个出列的人，只需要调用JosephusProblem(n, m, n) 就可以了。

有意思的是，虽然可以在O(k)的时间内找到第k个出列的人，但要用这种方法打印出整个出列序列，还是需要\(1+2 + ... +n = O(n^2)\) 的时间复杂度。

留下的问题：

能在 O(n) 的时间复杂度下打印出整个出列序列么？
或是说，是否存在 O(1) 的时间复杂度的算法，即一个数学公式，来求出第 k 个出列的人的编号？