约瑟夫斯问题（Josephus Problem）是一个经典的数学与电脑科学问题。
传说中，有 41 个人 被敌军包围。为了避免被俘，他们决定围成一圈，按照固定规则逐一淘汰自己。
问题是：
如果每次从固定位置开始数，每数到第 3 个人就淘汰他，最后一个留下的人应该站在哪个位置？
这就是著名的约瑟夫斯问题。
41 人与位置 19
在经典版本中，41 个人围成一圈，每数到第 3 个人就淘汰一人。
如果将位置从 1 到 41 编号，按照这个规则不断淘汰，最后留下的位置是：
位置 31
这个结果可以透过数学递回直接计算，而不需要真的逐个模拟淘汰过程。
需要注意的是，不同版本的问题可能采用不同的起点、编号方式与淘汰规则，因此最后的位置也会不同。
为什么这个故事与电脑科学有关？
约瑟夫斯问题看起来像是一个古老的数学谜题，但它其实揭示了一个非常重要的电脑科学概念：
如何有效处理循环结构中的元素删除。
如果直接模拟整个过程，就必须：
- 建立一个循环。
- 按照规则找到下一个要淘汰的位置。
- 删除该元素。
- 重新计算下一个位置。
- 不断重复，直到只剩下一个元素。
这种方法直观，但当人数非常大时，模拟过程可能会变得昂贵。
递回解法
约瑟夫斯问题最漂亮的地方，在于它可以透过递回关系解决。
如果有 n 个人，每次淘汰第 k 个人，令 J(n,k) 表示最后留下的位置，则：
J(1,k) = 0
J(n,k) = (J(n-1,k) + k) mod n
这里使用的是从 0 开始编号。
最后，如果需要转换成从 1 开始的位置，只需要：
J(n,k) + 1
function josephus(n, k):
result = 0
for i = 2 to n:
result = (result + k) mod i
return result
时间复杂度为：
O
而且不需要建立整个人员列表。
这就是演算法思维的核心之一：
不要只想着如何一步一步完成问题，也要寻找问题背后的结构。
一句话记住
约瑟夫斯问题表面上是在问「谁最后留下」，实际上是在研究「如何追踪一个不断缩小的循环结构」。
从 41 个人围成一圈，到今天的递回公式与电脑演算法，这个两千年前的数学问题至今仍然是资料结构与演算法中非常经典的一个案例。