递归实现Josephus问题的解释

递归实现Josephus问题的解释

使该解决方案对我有意义的关键见解如下：

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。幸存者在4人环中的1索引位置由给出

josephus(n - 1,2)

。因此

josephus(n - 1, 2) - 1

，我们可以向前走，并在必要时绕环圈到达最终位置。换句话说，幸存者的位置

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

但是，以上公式存在问题。如果我们确实在使用单索引，那么如果最后的幸存者位于位置n，会发生什么？在这种情况下，我们会意外地返回位置0作为答案，但我们确实需要位置n。为了解决这个问题，我们将使用技巧使用mod来环绕一个索引：我们将获取内部数量（一个索引位置），然后减去1以获得零索引位置。我们将该数量修改为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

加以向前移动适当的量，然后相减一并最后相加一以进行正确的环绕 *** 作。

希望这可以帮助！