Josephus问题递归实现的解释

Question

编辑：n 是人数。 k 是第 k 个被淘汰的人。所以对于 k=2，每第二个人就会被淘汰。

int josephus(int n, int k)
{
 if (n == 1)
  return 1;
else
   return (josephus(n - 1, k) + k-1) % n + 1;
}

代码尽可能简单。但不知何故我无法理解这个问题（老实说这有点尴尬）。

我试图理解的方式是，

josephus(n,k) 给出了人口规模为 n、步长为 k 的最终解决方案。
如果知道josephus(n-1,k)的解，就可以计算出josephus(n,k)。那就是我认为的"optimal substructure property"动态规划。
我知道我们需要做一个 MOD N，这样万一数字超过 n，它将再次从 1 开始计数。（即确保加法的行为就像我们在一个圆圈中计数一样） .但是为什么我们添加这个 "k-1"?

主要问题是，如果我们知道 josephus(n-1,k) 的正确解，我们如何计算 josephus(n,k) 的解。我们已经有效地在人口中增加了一个人，并且以某种方式添加这个 k-1 值给了我正确的解决方案（让我们暂时忽略 mod）。

任何人都可以向我解释一下最优子结构属性如何在问题的每一步保持不变？

Answer 1

使这个解决方案对我有意义的关键见解如下：josephus(n, k) 的结果最好不要被认为是 Josephus 的 number survivor，而是 Josephus 幸存者编号的 index。例如，调用 josephus(5, 2) 将告诉您最终幸存的五个人的 index。

带着这种直觉，让我们通过一个具体的例子来思考 Josephus 问题是如何工作的。假设我们想知道 josephus(n, 2)。你可以想象我们有n个人这样排队：

1 2 3 4 5 ... n

首先发生的事情是人 1 杀死了人 2，如下所示：

1 X 3 4 5 ... n

现在，我们剩下一个如下形式的子问题：剩下 n-1 个人，其他每个人都将被杀死，第一个刺伤的人是第 3 个人。换句话说，我们剩下一圈形状像这样的人：

3 4 5 ... n 1

，k = 2。现在，假设我们对 josephus(n - 1, 2) 进行递归调用，因为我们有 n - 1 个人。这将返回 n - 1 人的行中谁存活的 index。有了活下来的人的索引，也知道首发的人是谁，就可以决定留下哪个人。下面是我们将如何做到这一点。

这一行的首发人是上次被处死的人之后的人。这将是第 3 个人。幸存者在四人环中的 1 索引位置由 josephus(n - 1, 2) 给出。因此，我们可以向前走 josephus(n - 1, 2) - 1 个位置，如有必要，绕过圆环，到达我们的最终位置。换句话说，幸存者由position

给出

 (3 + josephus(n - 1, 2) - 1) % n

不过，上述公式存在问题。如果我们确实使用单索引，如果最后的幸存者在位置 n 会发生什么？在那种情况下，我们会不小心得到位置 0 作为我们的答案，但我们确实想要位置 n。作为对此的修复，我们将使用一个技巧来使用 mod 以单索引环绕：我们将获取内部数量（单索引位置）并减去 1 以获得零索引位置。我们将 mod 该数量乘以 n 以获得环绕的零索引位置。最后，我们将加回一个以获得单索引位置，环绕。看起来像这样：

(3 + josephus(n - 1, 2) - 2) % n + 1

因此这里的 -2 项来自两个独立的 -1：第一个 -1 是因为 josephus(n - 1, 2) returns 一个索引索引，所以要向前移动正确的位置数我们必须向前迈出 josephus(n - 1, 2) - 1 步。第二个 -1 是因为我们使用的是单索引而不是零索引。

让我们将其概括为适用于任意 k，而不仅仅是 k = 2。假设我们想知道 josephus(n, k)。在这种情况下，人 1 会刺伤人 k，给我们留下这样的数组：

1 2 3 ... k-1 X k+1 ... n

我们现在基本上需要解决一个第 k+1 人在前的子问题：

k+1 k+2 ... n 1 2 ... k-1

因此我们计算 josephus(n - 1, k) 以获得 n - 1 人环中的单索引幸存者，然后向前移动那么多步：

(k+1 + josephus(n - 1, k) - 1)

我们需要担心回绕的情况，所以我们需要 mod by n:

(k+1 + josephus(n - 1, k) - 1) % n

但是，我们是单索引的，所以我们需要使用内部数量减1然后在末尾加1的技巧：

(k+1 + josephus(n - 1, k) - 2) % n + 1

简化为

(k-1 + josephus(n - 1, k)) % n + 1

相当于

(josephus(n - 1, k) + k-1) % n + 1

如解决方案代码中所示。

总而言之：k-1 项来自于从位置 k+1 开始，添加 josephus(n - 1, k) - 1 以向前移动适当的量，然后减去 1 并在末尾添加 1 来做正确的环绕。

希望对您有所帮助！

Answer 2

我们需要将位置调整k-1只是因为第k个被移除后起始位置已经移动了k（并且第k-1个旋转到最后）。即，初始位置pos变为pos-k。如果k = 3，(n-1,k)返回pos = 2，原来的位置应该是pos + k = 5.

我们将公式中的k替换为k-1，因为我们要mod(n): k = (k-1) % n + 1

Josephus问题递归实现的解释

Explanation for recursive implementation of Josephus problem

algorithm

josephus