2

我知道模数给出了余数，而这段代码将给出约瑟夫斯问题的幸存者。我注意到一种模式，当 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
4

2 回答 2

5

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

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

调用时josephus(n-1,k)，这意味着您已经执行了每个第 k 个人，总共执行了 n-1 次。（更改为匹配乔治汤姆林森的评论）

递归继续进行，直到有 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

当我们检查 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)

于 2014-02-12T20:11:26.030 回答
2

您的第一个问题已在评论中得到回答。

要回答你的第二个问题，它指的是最后一个幸存者的位置。

考虑 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 根据需要。

于 2014-02-12T20:38:19.307 回答