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

Question

josephus problem可以是solved通过以下递归:

 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 完成将数组索引保持在范围内。希望它足够清晰和详尽:)。