20

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

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

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

我试图理解它的方式是，

  1. josephus(n,k) 给出大小为 n 且步长为 k 的种群的最终解。
  2. 如果我们知道 josephus(n-1,k) 的解，就可以计算出 josephus(n,k)。在我看来，这就是动态规划的“最佳子结构属性”。
  3. 我知道我们需要做一个 MOD N 以便在数字超过 n 的情况下，它将再次从 1 开始计数。（即确保加法的行为就像我们在一个圆圈中计数一样）。但是为什么我们要添加这个“k-1”呢？

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

谁能向我解释一下，在问题的每一步中，最优子结构属性如何保持？

4

2 回答 2

36

使该解决方案对我有意义的关键见解如下：josephus(n, k)最好不要将结果视为约瑟夫斯幸存者的数字，而是将其视为约瑟夫斯幸存者的数字的索引。例如，呼叫josephus(5, 2)将告诉您最终幸存的五个人中的人的索引。

考虑到这种直觉，让我们通过一个具体的例子来思考约瑟夫斯问题是如何工作的。假设我们想知道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 人的行中幸存者的索引。鉴于我们有幸存者的索引，并且我们也知道起始人是谁，我们可以确定留下哪个人。我们将这样做。

此行中的起始人是紧随最后被处决的人之后的人。这将是第 3 个人。幸存者在四人环中的 1 索引位置由 给出josephus(n - 1, 2)。因此，我们可以向前走josephus(n - 1, 2) - 1，必要时环绕环，到达我们的最终位置。换句话说，幸存者是由位置给定的

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

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

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

因此，这里的 -2 项来自两个独立的 -1：第一个 -1 是因为josephus(n - 1, 2)返回一个单索引索引，因此要向前走正确数量的位置，我们必须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)

我们需要担心我们环绕的情况，所以我们需要通过 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 以进行正确的环绕。

希望这可以帮助！

于 2015-08-02T20:22:24.270 回答
0

我们需要将位置调整 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

于 2021-08-18T20:12:38.700 回答