math - Josephus p‌r‌o‌b‌l‌l‌m 中的递归关系

Question

约瑟夫斯问题可以通过以下递归来解决：

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

这种递归关系是如何得出的？

Answer 1

约瑟夫斯(n, k) = (约瑟夫斯(n - 1, k) + k-1) % n + 1 ...... (1)

用简单的话来说——从公式中的“+1”开始。这意味着重复的 1 次迭代已经完成。现在，我们将剩下 n-1 个人/元素。我们需要以 k 的间隔递归处理 n-1 个元素。但是，现在，由于要删除的最后一个元素位于第 k 个位置，我们将从那里继续。因此，添加了 k-1。此外，这种添加可能会扰乱数组的索引。因此 %n 完成了将数组索引保持在范围内的操作。希望它足够清晰和详尽:)。

Answer 2

这一段从维基百科就足够了..

当索引从 1 开始时，则 s 处的人从第一个人移动到位置 ((s-1)\bmod n)+1，其中 n 是总人数。令 f(n,k) 表示幸存者的位置。在第 k 个人被杀死后，我们剩下一个 n-1 的圈子，我们从原始问题中编号为 (k\bmod n)+1 的人开始下一次计数。如果我们从 1 开始计数，则幸存者在剩余圆圈中的位置将为 f(n-1,k)；将其转移以考虑我们从 (k\bmod n)+1 开始的事实会产生递归

f(n,k)=((f(n-1,k)+k-1) \bmod n)+1,\text{ with }f(1,k)=1\,,