有人能解释一下这段代码中模数的用法吗？
我知道模数给出了余数，这段代码将给出约瑟夫斯问题的幸存者。我注意到一种模式，当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
回答 2
Stack Overflow用户
发布于 2014-02-12 12:11:26
这个答案既是对约瑟夫斯问题的总结，也是对你的以下问题的回答：
josephus(n-1,k)指的是什么？- 模数算符是用来做什么的？
当调用josephus(n-1,k)时，这意味着您已经执行了每一个kth人员，总共执行了n-1次。(改为与乔治·汤姆森的评论相匹配)
递归一直进行，直到有一个人站着，当函数返回到顶部时，它将返回你必须在其中生存的位置。模数运算符被用来帮助在圆圈内停留(正如GuyGreer在注释中解释的那样)。以下是一幅有助于解释的图片：
1 2
6 3
5 4让n=6和k=2(圆圈中每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当我们在n处检查从josephus返回的值时，我们得到以下值：
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这表明约瑟夫斯(n-1，k)指的是最后一个幸存者的位置。(1)
如果我们去掉了模算子，你会看到它会返回第11位，但是这里只有6，所以模算子帮助将计数保持在圆的范围内。(2)
Stack Overflow用户
发布于 2014-02-12 12:38:19
你的第一个问题已经在上面的评论中得到了回答。
要回答你的第二个问题，它指的是最后一个幸存者的位置。
考虑j(4,2)。
用该算法给出
j(4,2)=(j(3,2)+1)%4)+1
j(3,2)=(j(2,2)+1)%3)+1
j(2,2)=(j(1,2)+1)%2)+1
j(1,2)=1 所以
j(2,2)=((1+1)%2)+1=1
j(3,2)=((1+1)%3)+1=3
j(4,2)=((3+1)%4)+1=1 现在j(2,2)的表是
1 2
1 x所以j(2,2)确实是1。
对于j(3,2)，我们有
1 2 3
1 x 3
x x 3 因此j(3,2)按要求为3。
最后，j(4,2)是
1 2 3 4
1 x 3 4
1 x 3 x
1 x x x 它告诉我们，j(4,2)=1。
https://stackoverflow.com/questions/21737771
复制
腾讯云开发者
