问约瑟夫斯问题递归实现的解释

EN

对我来说，让这个解决方案有意义的关键洞察力是：josephus(n, k)的结果最好不要被认为是约瑟夫斯幸存者的数字，而是作为约瑟夫斯幸存者的数字的索引。例如，打电话给josephus(5, 2)会告诉你五个人中的一个人的索引，这个人最终幸存了下来。

考虑到这种直觉，让我们看看约瑟夫斯问题是如何工作的，通过一个具体的例子。假设我们想知道josephus(n, 2)。你可以想象我们有像这样排队的人：

1 2 3 4 5 ... n

发生的第一件事是，person 1杀死2个人，如下所示：

1 X 3 4 5 ... n

现在，我们有一个子问题，形式如下:还有n个人还活着，每个其他人都会被杀，第一个被刺伤的人是3个人。换句话说，我们剩下一个像这样形状的人环：

3 4 5 ... n 1

现在，假设我们对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)。在这种情况下，person 1会刺伤person k，留给我们这样一个数组：

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

我们现在基本上需要解决一个子问题，即person 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以向前移动适当的数量，然后减去一个，在末尾再加上一个以完成正确的概括。

希望这能有所帮助！

我们需要调整k-1的位置，因为在kth被移除后，开始位置已经被k移动(第一个k-1被旋转到末端)。也就是说，初始位置pos变成pos。如果k= 3，(n-1，k)返回pos = 2，则原始位置应为pos +k= 5。

我们在公式中用k-1代替k，因为我们必须用mod(n)：k= (k-1) %n+1。