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

josephus(n，k) = (josephus(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\,,