有人可以解释一下这段代码中模数的使用吗？

Question

我知道模数给出了余数，而这段代码将给出约瑟夫斯问题的幸存者。我注意到一种模式，当 n mod k = 0 时，起始计数点开始于圆圈的最开头，当 n mod k = 1 时，紧挨着圆圈开头的人在整个圆圈的执行过程中幸存下来.

我只是不明白这个递归如何使用模数来找到最后一个站立的人以及 josephus(n-1,k) 实际上指的是什么。它是指最后一个被处决的人还是特定回合中最后一个幸存者？

 def josephus( n, k):
  if n ==1:
    return 1
  else:
    return ((josephus(n-1,k)+k-1) % n)+1

Answer 1

这个答案既是约瑟夫斯问题的总结，也是对您以下问题的回答：

1. 什么是josephus(n-1,k)指什么？
2. 模数运算符的用途是什么？

调用时josephus(n-1,k)，这意味着您已经执行了每第 k 个人，最多执行 n-1 次。（已更改以匹配 George Tomlinson 的评论）

递归一直进行，直到有 1 个人站立，当函数返回到顶部时，它将返回您必须处于生存的位置。模数运算符用于帮助保持在圆圈内（就像 GuyGreer 在评论中解释的那样）。这是一张图片来帮助解释：

 1 2
6   3
 5 4

让 n = 6 和 k = 2（执行圈中的每第二个人）。首先运行一次该函数并且您已经执行了第二个人，圆圈变为：

 1 X
6   3
 5 4

继续递归直到最后一个人留下将导致以下序列：

 1 2      1 X      1 X      1 X      1 X      X X
6   3 -> 6   3 -> 6   3 -> X   3 -> X   X -> X   X
 5 4      5 4      5 X      5 X      5 X      5 X

当我们检查 josephus 在 n 处返回的值时，我们得到以下值：

n = 1 return 1
n = 2 return (1 + 2 - 1) % 2 + 1 = 1
n = 3 return (1 + 2 - 1) % 3 + 1 = 3
n = 4 return (3 + 2 - 1) % 4 + 1 = 1
n = 5 return (1 + 2 - 1) % 5 + 1 = 3
n = 6 return (3 + 2 - 1) % 6 + 1 = 5

这表明 josephus(n-1,k) 指的是最后一个幸存者的位置。(1)

如果我们删除了模数运算符，那么您将看到这将返回第 11 个位置，但这里只有 6 个，因此模数运算符有助于将计数保持在圆的边界内。(2)